2.3. Гипотеза четырех красок

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

Теорема о пяти красках [13]

Каждый планарный граф можно так раскрасить, используя пять цветов, что любые две смежные вершины будут окрашены в разные цвета, т. е. если G - планарный граф, то у (G) 5.

Теорема о четырех красках (недоказанная ))

Каждый планарный граф можно так раскрасить, используя 4 цвета, что любые две смежные вершины будут окрашены в разные цвета, т. е. у (G) 4, если G - планарный граф.

Впервые примерно в 1850 г. о гипотезе четырех красок речь шла в беседах Августа де Моргана и его ученика Ф. Гутри. Затем о ней говорилось в письме де Моргана сэру Вильяму Рауэну Гамильтону, датированном 23 октября 1852 г. Поскольку тогда довольно быстро нарастал поток доказательств , контрдоказательств , гипотез и теорем, относяШсИХСя к этой тематике, то накопилась громадная литература по гипотезе четырех красок, и эта теорема стала, по-видимому, самой знаменитой нерешенной задачей в математике. Мы не будем здесь подробно обсуждать гипотезу четырех красок и интересующегося ею читателя отсылаем к замечательной работе Оре [2 ].

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

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

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

2) Гипотезу четырех красок удалось обосновать с использованием ЭВМ (см. К. Appel, W. Накеп, Every planar map is four colorable, Bull, of Amer. Math. Sac, 82, № 5 (Sept. 1976)).- Прим. ред.

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

3.1.1. Максимальные г-подграфы. Порожденный подграф {Sr [G]) графа G = {X, Г), где [G] s X, называется г-подгра-фом, если он г-хроматический. Если не существует такого множества Н, что Н z:> Sr [G) и подграф Ш) является г-хроматическим, то подграф {Sr [G]) называется максимальным г-подграфом графа G. Очевидно, что для фиксированного значения г, вообще говоря, существует много различных максимальных г-подграфов данного графа G. Подграф, у которого множество вершин совпадает с некоторым максимальным независимым множеством в G и который не имеет ребер (т. е. является вполне несвязным), есть максимальный 1-подграф графа G, поскольку в G нет 1-хрома-тического подграфа, имеющего большее множество вершин, чем у рассматриваемого подграфа.

Хроматическое число графа G можно определить как такое наименьшее число г, что [G] = X по крайней мере для одного из максимальных г-подграфов графа G.

Теорема I. Если граф G является г-хроматическим, то он может быть раскрашен с использованием г (или меньшего числа) красок с помощью следующей процедуры: сначала в один цвет окрашивается некоторое максимальное независимое множество [G], затем окрашивается в следующий цвет множество Si [{X-5i[GT>] и т. д. до тех пор, пока не будут раскрашены все вершины.

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

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

1) Алгоритм, описанный в этом разделе, можно толковать как алгоритм динамического программирования или как древовидный поиск (с приоритетом) по ширине. Недавно Вэном (/. АСМ, 21, 1974, р. 385) был предложен иной, более выгодный, алгоритм, использующий древовидный поиск по глу-

Н. Кристофидес

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

Пусть G] - семейство максимальных (г - 1)-подграфов

графа G, а [G] - множество вершин/-го подграфа из семейства Qr-i [G]. Множество [G] является тогда множеством вершин к-то максимального 1-подграфа (независимого множества) графа

= {X - iS.i [G]), образованного вершинами графа G, не попавшими в (г - 1)-подграф [G] >.

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

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

WSii[G][jSl[G], (4.9)

7 = 1,2,.. ., Qr-i и А = 1, 2, . . ., д{, где g-r-i л д{ - соответственно число (г - 1)-подграфов и число 1-подграфов.

Семейство максимальных г-подграфов содержится в семействе в множеств IP {i = 1, 2, . . ., q{-gr-i), и оно может быть получено из него исключением таких множеств семейства, которые содержатся в других множествах.

Итак, в г [G] МОЖНО описать следующим образом:

@АО] = Щ \Н'£е и WH для любого

Н^£в,]ф1}. (4.10)

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

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