Внутренняя устойчивость графа. Порождение вершинно пустых подграфов.

Множество внутренней устойчивости графа — это множество несмежных вершин.

Максимальным множеством внутренней устойчивости называется внутренне устойчивое множество, добавление любой вершины к которому, делает это множество неустойчивым.

В каждом графе без петель и кратных рёбер можно выделить семейство

Ψ = {ψ₁, ψ₂, ..., ψ_i}

всех внутренне устойчивых подмножеств. Эти подмножества различаются количеством входящих в них элементов.
Число внутренней устойчивости η(G) определяется мощностью внутренне устойчивого подмножества, содержащего наибольшее число элементов, т.е. характеризует максимальное число несмежных вершин графа:

η(G) = max | ψ_i |

Пример: граф, представленный на рис. 22, имеет:
Ψ_i = { Ψ₁, Ψ₂, Ψ₃, Ψ₄, Ψ₅}, Ψ₁ = {x₁, x₄, x₆}, Ψ₂ = {x₂, x₅}, Ψ₃ = {x₂, x₆}, Ψ₄ = {x₃, x₄, x₅}, Ψ₅ = {x₄, x₅}.
Число внутренней устойчивости η(G) = 3.

Рис. 22

Иногда по аналогии с числом внутренней устойчивости рассматривают число внутренней полноты χ(G), которое определяет максимальное число вершин графа G, образующих полный подграф. Для графа G, представленного на рис. 22, семейство внутренне полных подмножеств имеет вид:

Φ = {φ₁, φ₂, φ₃, φ₄,}, φ₁ = {x₁, x₂, x₃}, φ₂ = {x₁, x₃, x₅}, φ₃ = {x₂, x₄}, φ₄ = {x₅, x₆},

а число внутренней полноты χ(G) = max |φ_i| = 3,φ Φ.

Очевидно, что поиск максимальных внутренне устойчивых множеств путем простого перебора является неэффективной процедурой, поэтому для поиска максимальных внутренне устойчивых множеств существует специальный алгоритм — алгоритм Магу.

Алгоритм Магусостоит из следующих этапов:

1. Для графа составляется матрица смежности.

2. По таблице смежности выписываются все парные дизъюнкции.

3. Выражение приводится к ДНФ.

4. Для любой элементарной конъюнкции выписываются недостающие элементы, которые и образуют множество внутренней устойчивости.

Раскраска вершин

Раскрасить вершины графа значит сопоставить каждой вершине графа идентификатор краски таким образом, чтобы кол-во этих красок было минимальным и 2 любые вершины, покрашенные одной краской, не были бы смежные. Если по-простому, то раскраской вершин графа называется назначение цветов его вершинам. Обычно цвета - это числа (также можно использовать латинские буквы). Тогда раскраска является функцией, определенной на множестве вершин графа и принимающей значения в множестве . Раскраску можно также рассматривать как разбиение множества вершин , где - множество вершин цвета . Множества называют цветными классами. Раскраска называется правильной, если каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета. Задача о раскраске состоит в нахождении правильной раскраски данного графа в наименьшее число цветов. Это число называется хроматическим числом графа и обозначается .

В правильной раскраске полного графа все вершины должны иметь разные цвета, поэтому . Если в каком-нибудь графе имеется полный подграф с вершинами, то для раскраски этого подграфа необходимо цветов. Отсюда следует, что для любого графа выполняется неравенство

Однако хроматическое число может быть и строго больше кликового числа. (Клика — подмножество вершин графа, полностью соединённых друг с другом, то есть подграф, являющийся полным графом. Кликовое число — число (G) вершин в наибольшей клике. Другие названия — густота, плотность. Максимальная клика — клика с максимально возможным числом вершин среди клик графа.)