Дискретная математика. Громов Ю.Ю - 119 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

119
Параграф 14
1. а) Независимые множества вершин: например, {1, 4}, {1, 4, 6} и
{1, 4, 6, 7}; максимальные независимые множества вершин: {5, 7}, {2, 4, 7},
{3, 4, 6} и {1, 4, 6, 7}; наибольшее независимое множество вершин {1, 4,
6, 7}; число независимости α(G) = 4; клики: например, {1, 2}, {1, 2, 3},
{1, 2, 5} и {1, 2, 3, 5}; максимальные клики: например, {4, 5}, {2, 5, 6} и
{1, 2, 3, 5}; наибольшая клика {1, 2, 3, 5}; кликовое число ω(G) = 4; до-
полнение до полного графа
G
:
кликовое число
)(Gω
= 4; вершинные покрытия: например, {2, 3, 5},
{1, 3, 5, 6} и {1, 2, 3, 5, 6}; минимальные вершинные покрытия: {2, 3, 5},
{1, 3, 5, 6}; наименьшее вершинное покрытие {2, 3, 5}; число вершинного
покрытия β(G) = 3;
б) Независимые множества вершин: например, {1, 3}, {1, 3, 6} и
{2, 4, 7}; максимальные независимые множества вершин: {1, 3, 6}, {2, 4, 7}
и {4, 5, 7}; наибольшее независимое множество вершин: {1, 3, 6} или
{2, 4, 7} или {4, 5, 7}; число независимости α(G) = 3; клики: например,
{1, 2}, {3, 4}, {1, 2, 5} и {2, 3, 5}; максимальные клики: например, {3, 4},
{1, 2, 5}, {2, 3, 5} и {2, 5, 6}; наибольшая клика: {1, 2, 5} или {2, 3, 5} или
{2, 5, 6}; кликовое число ω(G) = 3; дополнение до полного графа
G
:
кликовое число
)(Gω
= 3; вершинные покрытия: например, {1, 2, 3, 6},
{2, 4, 5, 7}, {2, 3, 4, 5, 7} и {1, 2, 3, 5, 6, 7}; минимальные вершинные
покрытия: {1, 2, 3, 6} и {2, 4, 5, 7}; наименьшее вершинное покрытие:
{1, 2, 3, 6} или {2, 4, 5, 7}; число вершинного покрытия β(G) = 4.
Параграф 15
1. S = {s
1
, s
2
, s
3
, s
4
, s
5
, s
6
},
1/6
1/2
0
0
1/3
0
0
1/6
1/2
0
0
1/3
P =
1/3
0
1/6
1/2
0
0
.
0
1/3
0
1/6
1/2
0
0
0
1/3
0
1/6
1/2
1/2
0
0
1/3
0
1/6
Цепь эргодическая.
5
7
1
2
4
6
3
1
7
2
6
4
5
3

Страницы