*** Внешне устойчивое (доминирующее) множество ***

 

Пусть дан граф G = (X,E) без изолированных вершин.

• Определение №1: ( Доминирующее множество или Внешнеусточивое )
Подмножество вершин V графа G называется доминирующим множеством (внешнеустойчивым множеством), если любая вершина из подмножества X\V смежна по крайней мере с одной вершиной из V, где V из X, X\V.

• Определение №2: ( Минимальное )
Доминирующее множество называется минимальным, если оно не содержит никакое другое доминирующее множество графа.

• Определение №3: ( Наименьшее )
Доминирующее множество наименьшей мощности графа G называется наименьшим доминирующим множеством.

*** Ядро графа ***

• Определение: ( Ядро графа )
Доминирующее множество, являющееся одновременно и независимым множеством называется ядром графа.

-> Очевидно, что независимое множество является максимальным <=> когда оно доминирующее.

*** Клика графа ***

Пусть граф G = (X,E) произвольный, без изолированных вершин.

• Определение №1: ( Клика )
Подмножество вершин Q из X графа G называется кликой, если вершины в Q попарно смежны

• Определение №2: ( Максимальная клика )
Клика называется максимальной, если не содержится ни в одной другой клике графа.

• Определение №3: ( Наибольшая клика )
Клика называется наибольшей, если имеет наибольшую мощность среди всех клик графа.

• Определение №4: ( Плотность графа )
Мощность наибольшей клики графа называется плотностью графа.
Обозначается: "фи"(G).

• Утверждение :
Подмножество вершин графа G является кликой <=> когда оно независимо в графе дополнения `G`
=> "фи"(G) = "альфа_0"(G)

Исходя из этого равенства, и используя оценки числа независимости "альфа_0", легко получить оценки плотности графа.

• Определение №5: ( Кликовое покрытие )
 Множество клик, покрывающее множество вершин графа называется кликовым покрытием графа.

Очевидно, что множество всех клик графа и => множество всех максимальных клик графа является кликовым покрытием.

• Определение №6: ( Число кликового покрытия )
Наименьшее количество клик, покрывающих вершины графа называется числом кликового покрытия графа.
    Обозначается:  с(G).

Непосредственно из Df#6 имеем с(G) >= "альфа_0"(G)

->Пример:
C = {Q_2,Q_3,Q_4} (наименьшее кликовое покрытие)
с(G) = 3