Этюды для программистов

Раскрашивать можно двумя способами: либо предположить, что каждая вершина уже раскрашена в свой цвет и попытаться избавиться от нескольких цветов, либо предположить, что ни одна вершина еще не раскрашена, и пытаться добавлять как можно меньше цветов. Однако на любом пути мы сталкиваемся с неприятным теоретическим результатом (или с отсутствием оного): никто не знает, как раскрасить карту, не перебрав для худшего случая все возможные раскраски с минимальным числом цветов. Большинство специалистов считает, что нет более быстрого метода раскрашивания карты, чем перебор всех вариантов. Иными словами, какой бы умной ни была ваша программа и как бы быстро она ни работала в среднем, найдутся карты с n вершинами, требующие к цветов, на раскраску которых программа затратит порядка kⁿ единиц времени. Возможно, кому-нибудь посчастливится найти алгоритм, и для худшего случая оказывавшийся не столь расточительным, но теоретики считают это маловероятным. Так что давайте займемся простой быстрой программой, а не суперсложной, которая вряд ли будет лучше.[62]

Предлагаемое решение основано на наблюдении, что если некоторый подграф нельзя раскрасить в k цветов, то и весь граф, очевидно, тоже нельзя раскрасить в к цветов. На каждом шаге нашего алгоритма мы пытаемся добавить к уже раскрашенному подграфу еще одну вершину. Если сделать это не удастся, текущий раскрашенный подграф перекрашивается всеми возможными способами с использованием тех же цветов. Если новую вершину добавить все же нельзя, число цветов увеличивается на единицу» поскольку найден подграф, не раскрашиваемый выделенными цветами. В описании алгоритма предполагается, что есть вектор цвет, содержащий цвета, приписанные каждой вершине. Логическая функция связь позволяет узнать, связана ли вершина i с вершиной j.

Алгоритм раскраски графа

1. (Начальная установка.) Предположим, что в графе имеется числовершин вершин, что переменная старшийцвет содержит номер старшего из уже использованных цветов, а нуль показывает, что вершина еще не наделена цветом. Для всех вершин n установить цвет[n] равным нулю (т. е. сделать все вершины нераскрашенными). Установить старшийцвет равным нулю, а переменную равной единице.

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

3. (Подготовка одного узла.) Увеличить цвет[текущаявершина] на единицу. Установить булеву переменную флагцикла равной значению отношения цвет[текущаявершина] <= старшийцвет. Теперь рассматриваемая вершина имеет ненулевой цвет, и необходимо проверить, совместима ли текущаявершина со своими соседями. Заметьте, что впервые добавляемая вершина всегда имеет нулевой цвет. Прибавляя единицу к нулю, мы наделяем вершину допустимым цветом. Пока цикла имеет значение истина, выполнять шаги 4 и 5.

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

5. (Проверка цвета каждого соседа.) Если вершина i и текущаявершина связаны (т. е. если связь(i, текущаявершина) имеет значение «истина») и если цвет[i] и цвет[текущаявершина] равны, значит, текущаявершина имеет недопустимый цвет. В этом случае установить значение i равным текущаявершина, чтобы прервать цикл, начинающийся в шаге 4, увеличить цвет[текущаявершина] на единицу чтобы попробовать следующий цвет, и установить значение флагцикла равным значению отношения цвет[текущаявершина] <= старшийцвет. В противном случае просто увеличить i на единицу, чтобы проверить следующего соседа. Заметьте, что последнее присваивание переменной флагцикла перекроет присваивание в шаге 4, но может установить переменную флагцикла равной значению ложь. Далее, если начинающийся в шаге 4 цикл завершается нормально (т. е. без насильственного присваивания переменной текущаявершина значения i), произойдет выход из цикла, начинающегося в шаге 3. Важно, чтобы при проверке допустимости раскраски использовались лишь вершины, номера которых строго меньше, чем текущаявершина, поскольку вершины с большими номерами еще не раскрашены.