5.10. Алгоритм оптимальной раскраски графа

Минимальное число цветов, необходимое для раскраски вершин некоторого графа с использованием для пары соседних вершин различных цветов, называется хроматическим числом

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

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

Мы можем (как в задаче о восьми ферзях) сначала раскрасить одну вершину и учесть все импликации, связанные с присвоением этого значения, а затем использовать метод неявного перебора до тех пор, пока не раскрасим все вершины. Но здесь мы должны остановиться не тогда, когда исчерпаем все возможности, а гораздо раньше — как только мы сможем доказать, что не существует решения лучшего, чем известное нам оптимальное решение. Общая схема действий приведена в алгоритме 5а.

Алгоритм 5а

(см. скан)

5.10.1. Первый этап: поиск решения

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

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

а) как происходит выбор в случае равенства степеней свободы;

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

На данном этапе становится очевидным, что мы, безусловно, можем построить лучшее решение, чем то тривиальное решение, которое приписывает каждой вершине свой цвет. Для этого достаточно рассматривать только критерий, касающийся степеней вершин графа (мы ввели его при разъяснении пункта . В самом деле, ведь априори все степени свободы равны, и потому основанный на них критерий не является действенным. Но тогда мы можем построить хорошее решение, используя “жадный” алгоритм следующего вида:

Алгоритм 5б

(см. скан)

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

Мы раскрасим сначала вершину “Париж”, одну из двух, обладающих максимальной степенью:

I (Париж).

Затем мы наложим запрет на использование цвета I при раскрашивании шести соседних вершин и одновременно уменьшим на единицу степени всех этих вершин. Таким образом, мы получим вторую строку табл. 5.1. Теперь наибольшей степенью обладает вершина “Берлин”. Поскольку цвет I использовать в этом случае запрещено, мы закрасим ее цветом II:

II (Берлин).

Таблица 5.1. (см. скан) Раскрашивание географической карты

При этом степени вершин изменятся так, как указано в третьей строке табл. 5.1. Выбрав первую по счету вершину, обладающую степенью 2, мы получаем III (Брюссель), поскольку связанные с данной вершиной вершины раскрашены в цвета I и II. Теперь мы получили степени, указанные в четвертой строке табл. 5.1. Поскольку для вершины “Вена” третий цвет не запрещен, мы можем раскрасить:

III (Вена)

Теперь мы можем раскрасить все оставшиеся вершины:

Мы получили решение в четыре краски. Однако мы лишь узнали, что для данной карты у 4, но не доказали, что сделать

Таблица 5.2. (см. скан) Раскрашивание графа для задачи о конференции лучше невозможно.

Такой же результат дает теорема Аппеля и Хакена.

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

Затем, используя промежуточные результаты, приведенные в табл. 5.2, последовательно получаем

Наконец, когда все оставшиеся вершины оказываются в нулевой степени, получаем

Мы можем утверждать, что для второго графа у 5.

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