3. Точные алгоритмы раскраски

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

3.1. Метод динамического программирования

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

Хроматическое число графа можно определить как такое наименьшее число что по крайней мере для одного из максимальных -подграфов графа

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

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

Раскраску указанного в теореме вида будем называть оптимальной независимой раскраской.

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

Пусть семейство максимальных -подграфов графа множество вершин -го подграфа из семейства Множество является тогда множеством вершин максимального -подграфа (независимого множества) графа образованного вершинами графа не попавшими в -подграф

Тогда следующим образом можно описать семейство всех максимальных -подграфов графа

Строим множества

где соответственно число -подграфов и число -подграфов.

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

Итак, можно описать следующим образом:

3.1.3. Алгоритм, основанный на рассмотрении максимальных r-подграфов. В предыдущем разделе было указано, что хроматическое число графа является таким наименьшим значением при котором множество вершин некоторого максимального -подграфа — совпадает с X (множеством вершин графа Поэтому рекуррентные соотношения (4.9) и (4.10) могут быть использованы для последовательного построения максимальных -подграфов, -подграфов и т. д. и нахождения хроматического числа графа нужно просто на каждом шаге указанной процедуры проверять, не содержится ли множество вершин графа в каком-нибудь из построенных подграфов.

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

Шаг 1. Положить Найти множества вершин максимальных -подграфов графа G. (Считаем, что имеется таких множеств.) Пусть Положить

Шаг 2. Найти максимальное независимое множество графа Если такое множество существует, то перейти к шагу 3. Если все такие множества уже найдены, то перейти к шагу 6.

Шаг 3. Вычислить

Шаг 4. Если то остановиться. Число есть хроматическое число графа Подмножества, включенные в множество дают требуемую раскраску. (Эти подмножества накапливаются по мере их введения и хранятся отдельно с соответствующими отметками (маркерами)). Если то перейти к шагу 5.

Шаг 5. (i) Если для некоторого то перейти к шагу 2.

(ii) Если для некоторых то положить по всем таким из Положить и перейти к шагу 2.

(iii) Если не выполняется ни одно из условий (i) и (ii), указанных выше, то положить и перейти к шагу 2.

Шаг 6. Если то положить и перейти к шагу

Если то положить числу множеств в и перейти к шагу 2.

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

3.1.4. Пример. Рассмотрим семивершинный граф изо браженный на рис. 4.3.

Шаг 1. Множествами вершин максимальных -подграфов являются:

Следовательно,

Применяем (необходимое число раз) шаги 2—5 алгоритма:

Для

Шаг 2.

(см. скан)

(см. скан)

Таким образом, в конце первой итерации, использующей шаги

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

Действуя аналогичным образом дальше, можно построить максимальные -подграфы и т. д. В действительности уже следующее порожденное множество будет удовлетворять условию на шаге 4. Следовательно, хроматическое число графа равно 3 и оптимальная раскраска задается следующим разбиением (множества X)

Если применять алгоритм дальше, то будет получена еще одна возможная раскраска:

Все другие множества либо содержатся в двух предшествующих множествах, либо не содержат все вершины из

Заметим, что такие раскраски, как хотя и возможны, но не являются оптимальными независимыми и не порождаются описанным выше алгоритмом.