3.7. Независимые множества графа

Подмножество S множества вершин V графа G называется независимым множеством графа G, если выполняется условие S  N(S)  , т. е. любые две вершины из S не смежны. Если S – независимое множество, то любое его подмножество также является независимым. Поэтому представляет интерес задача нахождения в графе максимальных независимых множеств, т. е. таких, которые не являются собственными подмножествами никаких других независимых множеств.

Независимое множество, имеющее наибольшую мощность среди всех независимых множеств графа G, называют наибольшим независимым множеством, а его мощность называют числом независимости графа G и обозначают символом .

Примером задачи нахождения наибольшего независимого множества является другая задача о ферзях, в которой надо расставить на шахматной доске наибольшее число ферзей так, чтобы ни один из них не находился под ударом другого. Наибольшее независимое множество графа, представляющего шахматную доску, как определено выше, покажет, на какие клетки надо поставить ферзей. Наибольшее число ферзей, расставленных при указанном условии, которое в данном случае равно восьми, есть число независимости данного графа.

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

Рис. 3.6. Граф для демонстрации получения независимого множества

Действительно, в качестве первой вершины для включения в решение может быть выбрана вершина v₅. Тогда вслед за ней в решение включаются вершины v₃ и v₇. Мощность полученного таким образом множества на единицу меньше мощности наибольшего независимого множества {v₁, v₄, v₆, v₉}.

Вершинным покрытием графа G = (V, E) называется такое множество В  V, что каждое ребро из Е инцидентно хотя бы одной вершине из В. Очевидно, что если В – вершинное покрытие, то V \ B – независимое множество. Вершинное покрытие наименьшей мощности в графе G является его наименьшим вершинным покрытием . Ясно, что еслиВ – наименьшее вершинное покрытие, то V \ B – наибольшее независимое множество.

Чтобы найти наименьшее вершинное покрытие в графе G, достаточно покрыть столбцы его матрицы инцидентности минимальным количеством ее строк. Матрица инцидентности графа на рис. 3.5 имеет следующий вид:

.

Строки v₁, v₃, v₅ и v₇ составляют кратчайшее покрытие этой матрицы. Множество вершин {v₁, v₃, v₅, v₇} является наименьшим вершинным покрытием данного графа. Следовательно, {v₂, v₄, v₆} – одно из наибольших независимых множеств. Оно присутствует в решении предыдущего примера.

Подграф графа G, порождаемый его независимым множеством, является пустым подграфом, т. е. множество его ребер пусто. В графеG, который является дополнением графа G, это же множество порождает полный подграф, т. е. подграф графаG, в котором все вершины попарно смежны в графеG. Полный подграф называют еще кликой. Таким образом, задача нахождения полных подграфов, или клик, и задача нахождения независимых множеств в некотором графе являются двойственными по отношению друг к другу.