5.10.2. Второй этап: поиск оптимального решения

Поскольку мы знаем, что число вариантов, возможных для каждой вершины, ограничено числом введем векторы состоящие из компонентов каждый. Но на практике следует учитывать, что любое решение определяется только с точностью до перестановки соседних цветов (в данной задаче цвета I, II или III — всего лишь имена, служащие ориентиром). Таким образом, когда мы начали выполнять алгоритм 56, первые из присвоенных значений

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

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

Для раскрашивания клики мощностью нужно цветов.

Таким образом, в примере 1 3 у 4, поскольку вершины “Париж”, “Берлин” и “Брюссель” образуют клику мощностью

3. Кроме того, единственная вершина, которая должна быть раскрашена четвертым цветом (Люксембург), оказалась в таком положении из-за того, что сама связана с тремя этими вершинами. В действительности подграф, состоящий из вершин “Париж”, “Берлин”, “Брюссель” и “Люксембург”, образует еще одну клику мощностью 4.

Рис. 5.24.

Рис. 5.25.

Отсюда следует непосредственный вывод: в данном примере минимальное число цветов, необходимое для раскраски всех вершин, равно 4 (т. е.

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

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

Кроме того, не можем ли мы построить граф, для которого данное свойство не выполняется? Оказывается, если “поиграть” немного с группой треугольников (клика мощностью 3), мы получим контрпример, изображенный на рис. 5.24.

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

цвет III, но тогда вершина оказывается связанной с вершинами а (цвет I), (цвет II) и е (цвет III). Следовательно, предположение о возможности использования только трех цветов привело к противоречию.

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

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

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

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

Практически окончательный вариант алгоритма раскрашивания вершин приведен ниже.

Алгоритм 5в

(см. скан)

Мы получили клику мощностью С; исключить из все вершины, степени которых строго меньше С.

Начать в новом графе поиск большой клики:

(см. скан)

(см. скан)

Используя этот метод, мы теперь можем решить еще одну задачу.