Независимые множества

Независимое множество вершин – подмножество вершин графа G: SÍ V такое, что любые две вершины в нем несмежны, то есть никакая пара вершин не соединена ребром.

подграф, порожденный независимым множеством – пустой граф.

Максимальное независимое множество – не является собственным подмножеством другого независимого множества.

Наибольшее независимое множество – наибольшее по мощности среди всех независимых множеств.

Число независимости a(G) графа G – мощность наибольшего независимого множества.

Например:

Максимальные независимые множества

; ; ;

; ;

; ;

.

Наибольшее независимое множество графа G: .

Число независимости графа G: a(G) =4.

Клика

Клика – подмножество вершин графа G такое, что любая пара из этого множества является смежной.

подграф, порожденный кликой – полный граф.

Максимальная клика – не является собственным подмножеством никакой другой клики графа G.

Наибольшая клика – наибольшая по мощности среди всех остальных клик графа G.

Кликовое число или плотность j(G) графа G – мощность наибольшей клики.

Например:

S₁={a, b, с};

S₂={b, d, e};

S₃={b, c, e};

S₄={b, d, c};

S₅={c, d, e};

S₆={b, c, d, e}.

Максимальные клики: S₁={a, b, с}, S₆={b, c, d, e}.

Наибольшая клика: S₆={b, c, d, e}.

Кликовое число: j(G) =4