3.5. Разбиения вершин

Множество вершин называется независимым, если оно не содержит двух смежных вершин. В частности, изолированная вершина образует независимое множество. Иногда возникает задача нахождения наибольшего независимого множества вершин в данном графе.

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

компоненте и, объединив подкомиссии, получить решение задачи).

Для получения решения задачи можно было бы начать с одного произвольного лица и к нему добавлять последовательно другие, причем лицо, выбираемое на каждом шаге, не должно конфликтовать ни с одним из выбранных. Такой процесс даст в конечном счете максимальное независимое множество т. е. множество, которое не является подмножеством любого большего независимого множества. Однако у нас не может быть полной уверенности в том, что будет наибольшим из всех возможных независимых множеств (maximum maximorum), так как объем зависит от того, какие вершины выбираются на каждом шаге процесса.

В качестве предельного случая рассмотрим граф, показанный на рис. 3.26.

Рис. 3 26.

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

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

Рис. 3.27,

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

В обыкновенном графе вершина доминирует над собой и над вершинами, с которыми она смежна.

Следовательно, множество из вершин доминирует самое большое над вершинами. Если граф содержит вершин, то необходимым условием того, что будет внешне устойчивым множе ством, является

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

Упражнения

(см. скан)

С рассмотренными задачами тесно связан еще один класс задач, который является предметом многих исследований. Требуется разделить вершины данного графа на наименьшее число независимых множеств. Задачи подобного типа часто называются задачами раскраски и формулируются следующим образом: назначить каждой вершине цвет (или абстрактную пометку) таким образом, чтобы смежные вершины всегда имели различные цвета (пометки) и число различных используемых цветов (пометок) было как можно меньше.

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

Теорема 3.24. Каждое дерево (исключая вырожденное дерево, состоящее из одной изолированной вершины) имеет хроматическое число, равное 2.

Очень важно отметить тесную связь между хроматическим числом графа и понятием -дольного графа. Хроматическое число является просто наименьшим при котором является -дольным. В частности, теорема 3.24 утверждает, что каждое дерево является простым графом (двудольным). На рис. 3.28 два изображения одного и того же дерева.

Рис. 3.28.

При втором изображении ясно видно свойство двудольности, в то время как связность и отсутствие циклов более очевидны при первом.

Далее мы еще вернемся к задачам раскраски и, в частности, к задаче определения хроматического числа класса плоских графов, являющейся знаменитой задачей о четырех красках (так как предполагается, что хроматическое число плоских графов равно четырем).

Рис. 3.29.

Замечание. Татт предположил, что граф любого выпуклого многогранника содержит гамильтоиов цикл. Отсюда следует гипотеза о четырех красках. Ясно, что граф является скелетной схемой выпуклого многогранника тогда и только тогда, когда он плоский и -связный. Таким образом, предположение Татт эквивалентно тому, что каждый -связный плоский граф имеет гамильтоиов цикл. Татт [14] доказал, что плоский граф рис. 3.29 не содержит гамильтоиова цикла.