Раскраска графa

Задача о наибольших полных и пустых подграфах

Введение

ПУСТЫЕ И ПОЛНЫЕ ПОДГРАФЫ

Конспект лекции

по дисциплине «Дискретная математика»

Некоторые замечания о терминологии.

Пусть имеется граф G , обладающий свойством P. Будем говорить, что граф G является P-минимальным, если не существует подграфа , обладающего этим свойством. Граф G называется P-максимальным, если не существует надграфа , который обладает свойством P. Например, на данном множестве вершин дерево является минимальным связным и максимальным графом без циклов. Слова «наибольший» и «наименьший» будем использовать для обозначения части графа, обладающей свойством P и имеющей наибольшую (наименьшую) мощность.

Пусть G=(X,U) – неориентированный граф, .

Задача 1. Найти в графе G полный подграф G^’=(A,U), порожденный множеством вершин A, с наибольшим числом вершин. Это число называется плотностью графа G.

Задача 2. В графе G найти пустой подграф G^’=(B,U), порожденный множеством , с наибольшим числом вершин. Это число называется неплотностью графа G или числом внутренней устойчивости.

Полный подграф графа G называется кликой, а пустой – внутренне устойчивым множеством (ВУМ).

Пример 1. В графе G (рис.2.1) можно выделить клику , при этом кликой наибольшей мощности является A₁ и . Внутреннее устойчивые множества: и. В матрице смежности графа G внутренне устойчивому множеству будет соответствовать нулевая подматрица.

b e

d

a g

c f

Рис. 2.1. Граф G примера 1

Пример 2. При представлении игр графами внутренне устойчивое множество вершин соответствует такому множеству позиций, что ни одна из них не может быть достигнута за один ход. Пусть в задаче требуется расположить наибольшее количество ферзей на шахматной доске так, чтобы ни один из них не бил другого, т.е. требуется найти наибольшее ВУМ. Очевидно, таких ферзей не может быть больше восьми (по одному на каждой вертикали и горизонтали).

Пример 3. Пусть для передачи информации используется код, символы которого обозначим . При приеме сообщения некоторые символы из множества X=могут быть приняты по ошибке за другие. Таким образом, процесс передачи информации может быть представлен в виде графа G=(X,U), в котором ребро когда символ может быть принят при передаче символа . Поэтому при кодировании сообщения желательно выбирать символы из внутренне устойчивого множества.

Заметим, что задача 1 и задача 2 взаимосвязаны. Для этого рассмотрим понятие дополнительного графа. Граф называется дополнительным к графу G=(X,U), если . При этом каждому полному подграфу графа G будет соответствовать пустой подграф в дополнительном графе , следовательно, .

Для графов общего вида задачи 1 и 2 не имеют эффективного алгоритмического решения. Большинство алгоритмов основано на полном переборе вариантов. Поэтому для построения клики (ВУМ) вначале пытаются уменьшить размерность задачи. Рассмотрим один из таких методов.

Обозначим U(x) - множество вершин, смежных вершине x в графе G=(X,U). Будем говорить, что вершина x покрывает вершину y, если . Пусть требуется решить задачу 2 о нахождении ВУМ наибольшей мощности. Решение основано на следующем утверждении.

Теорема. Если в графе G=(X,U) существует ВУМ мощности k и в паре вершин вершина x покрывает вершину y, то в подграфе, порожденном множеством X\{x}, также существует ВУМ мощности k (без доказательства).

Теорема утверждает, что удаление покрывающей вершины не меняет числа внутренней устойчивости графа.

Алгоритм «общипывания» графа заключается в следующем:

Шаг 1. Проверяем, является ли данный граф пустым. Если да, то задача решена успешно.

Шаг 2. Ищем пару вершин, из которых одна покрывает другую. Если такая пара существует, то переходим к шагу 3, иначе алгоритм бесполезен.

Шаг 3. Вычеркиваем в найденной паре покрывающую вершину и переходим к шагу 1.

Например, для графа G, рассмотренного в примере 1 (рис. 2.1), алгоритм дает решение задачи о наибольшем ВУМ:

1) , матрица смежности имеет вид:

A=,

Граф G не пуст, и вершина a покрывает вершину c.

2) ,

A₁=,

Граф G₁ не пуст, вершина d покрывает вершину c.

3) ,

A₂=,

Граф G₂ не пуст, вершина e покрывает вершину f.

4) ,

A₃=,

Граф G₃ не пуст, вершина f покрывает вершину g.

5) ,

A₄=,

Граф , порожденный множеством вершин, пуст, - искомое ВУМ и .

Этот алгоритм не всегда дает решение задачи, но уменьшает ее размерность.

Пусть G=(X,Г) – неориентированный граф. Граф G называется p-хроматическим, если его вершины можно раскрасить p различными цветами так, что никакие две смежные вершины не будут окрашены одинаково. Это возможно сделать, если существует разбиение множества вершин X на p непересекающихся подмножеств:

; , , (3.1)

такое, что все блоки разбиения являются внутренне устойчивыми множествами. Разбиение (3.1) называется p-раскраской графа, а его блоки – цветными классами [4]. Хроматическое число графа – это наименьшее количество цветных классов. Функция f:Xназывается функцией раскраски p-хроматического графа, если для всех , . Функция раскраски, принимающая наименьшее возможное значение в каждой из вершин графа, называется функцией Гранди .

Пример 1. Построить функцию Гранди для графа G=(X,U) (рис.3.1)

X₃ X₆

X₂ X₄ X₅ X₇

X₁ X₈

Рис. 3.1 Граф G примера 1

Найдем в графе G произвольное максимальное внутренне устойчивое множество, например,. Сопоставим всем вершинам множества значение функции Гранди, равное единице. Рассмотрим подграф , порожденный множеством вершин . Найдем в подграфе максимальное внутренне устойчивое множество, например,. Сопоставим этим вершинам значение функции, равное двум. Подграф , порожденный множеством оставшихся вершин является пустым (его вершины несмежны), всем его вершинам сопоставляем число три. Таким образом, функция Гранди построена:

Граф G является 3 – хроматическим.

Приведем несколько утверждений о р-хроматических графах [2, 4].

Утверждение 3.1. Полный граф является n-хроматическим.

Действительно, т.к. все вершины полного графа смежны, то в разбиении (3.1) каждая вершина полного графа образует отдельный блок, поэтому для раскраски вершин потребуется n красок.

Утверждение 3.2. Плотность графа не превосходит его хроматического числа.

В самом деле, если в графе существует клика из k вершин, то для раскраски понадобится не менее k красок.

Утверждение 3.3. Граф является двудольным тогда и только тогда, когда он бихроматический (2-хроматический).

Утверждение 3.4. Дерево – бихроматический граф.