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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

75
множеством другой клики этого графа. Максимальная клика графа G на-
зывается наибольшей кликой графа G, если она содержит наибольшее ко-
личество вершин. Мощность наибольшей клики графа G будем называть
кликовым числом и обозначать ω(G).
Применительно к графу G на рис. 39, кликами являются множества
{1, 2}, {1, 2, 5} и {2, 3, 5, 6}; максимальными кликами − множества {1, 2, 5}
и {2, 3, 5, 6}; наибольшей кликой − множество {2, 3, 5, 6}, а кликовое
число ω(G) = 4.
Число независимости графа G связано с его кликовым числом соот-
ношением
)()( GG ω=α
, где
G
− дополнение графа G до полного графа.
На рисунке 40 изображён граф
G
, его кликовое число
)(
G
ω
= 4.
Множество вершин графа G такое, что любое ребро графа инци-
дентно хотя бы одной из вершин этого множества, называется вершин-
ным покрытием графа G. Вершинное покрытие графа G, которое являет-
ся собственным подмножеством любого другого вершинного покрытия
этого графа, называется минимальным вершинным покрытием графа G.
Минимальное вершинное покрытие графа G наименьшей мощности на-
зывается наименьшим вершинным покрытием графа G. Мощность наи-
меньшего вершинного покрытия графа G называется числом вершинного
покрытия графа G и обозначается β(G).
Для графа G на рис. 39 вершинными покрытиями являются множе-
ства {2, 5, 6}, {1, 3, 5, 6} и {1, 3, 5, 6, 7}; минимальными вершинными
покрытиями − множества {2, 5, 6} и {1, 3, 5, 6}; наименьшим вершинным
покрытием − множество {2, 5, 6}, а число вершинного покрытия β(G) = 3.
Между независимым множеством вершин графа G и вершинным
покрытием графа G существует связь, которую определяет следующее
утверждение.
Теорема. Подмножество V
′
множества V вершин графа G являет-
ся вершинным покрытием тогда и только тогда, когда
V
′
= V \ V
′
− не-
зависимое множество вершин. ■
Из этой теоремы следует, что α(G) + β(G) = n для любого графа G с
n вершинами. Для графа G на рис. 39 имеет место равенство α(G) + β(G) = 7.
Рис. 39
1
2
3
4
5
6
7
Рис. 40
6
1
3
2
4
7
5

Страницы