Задача о раскраске графа - NP-полнота и вычислительная неразрешимость

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

Задача о раскраске графа

Под раскраской графа понимается аналогичный процесс с ненаправленным графом G, в котором узлы играют роль раскрашиваемых областей, а ребра представляют соседние пары. Требуется назначить цвет каждому узлу G так, чтобы при наличии ребра (u, v) узлам u и v были назначены разные цвета; целью является выполнение этих условий с минимальным набором цветов. В более формальном варианте k-раскраской G называется такая функция f: V → {1, 2, ..., k}, что для каждого ребра (u, v) выполняется f(u) = f(v). (Таким образом, цвета обозначаются 1, 2, ..., k, а функция f представляет выбор цвета для каждого узла.) Если для G существует k-раскраска, он называется k-раскрашиваемым.

В отличие от карт на плоскости, вполне очевидно, что не существует фиксированной константы k, с которой любой граф имеет k-раскраску: например, если взять множество из n узлов и соединить каждую пару ребром, то для раскраски полученного графа потребуется n цветов. Тем не менее алгоритмическая версия задачи очень интересна:

Для заданного графа G и границы k имеет ли граф G k-раскраску?

Будем называть эту задачу задачей раскраски графа — или k-раскраски, когда мы хотим подчеркнуть конкретный выбор k.

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

♦ Допустим, имеется набор из n процессов в системе, которая позволяет выполнять несколько заданий в параллельном режиме. При этом некоторые пары заданий не могут выполняться одновременно, потому что им нужен доступ к некоторому ресурсу. Для следующих k временных квантов требуется спланировать выполнение процессов, чтобы каждый процесс выполнялся минимум в одном из них. Возможно ли это? Если построить граф G на базе множества процессов, соединяя два процесса ребром при наличии конфликта, то k-раскраска G будет представлять план выполнения, свободный от конфликтов: все узлы, окрашенные в цвет j, будут выполняться на шагеj, а вся конкуренция за ресурсы будет исключена.

♦ Другое известное применение задачи встречается при разработке компиляторов. Предположим, при компиляции программы мы пытаемся связать каждую переменную с одним из к регистров. Если две переменные используются одновременно, они не могут быть связаны с одним регистром (в противном случае присваивание одной переменной приведет к потере значения другой). Для множества переменных строится граф G; две переменные соединяются ребром в том случае, если они используются одновременно. K-раскраска G соответствует безопасному способу распределения переменных между регистрами: все узлы с раскраской j могут быть связаны с регистром j, так как никакие два из них не используются одновременно.

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

Вычислительная сложность задачи о раскраске графа

Какую сложность имеет задача k-раскраски? Прежде всего, в случае k = 2 возникает задача, которую мы уже видели в главе 3. Вспомните, что мы рассматривали задачу определения того, является ли граф G двудольным, и показали, что она эквивалентна следующему вопросу: можно ли раскрасить узлы G в красный и синий цвета так, чтобы у каждого ребра один конец был красным, а другой синим?

Но последний вопрос в точности соответствует задаче о раскраске графа для k = 2 цветам (красный и синий). Таким образом, мы показали, что

(8.21) Граф G является 2-раскрашиваемым в том, и только в том случае, если он является двудольным.

Это означает, что алгоритм из раздела 3.4 может использоваться для принятия решения о том, является ли входной граф 2-раскрашиваемым, за время O(m + n), где n — количество узлов G, а m — количество ребер.

Стоит перейти к k = 3 цветам, как ситуация значительно усложняется. Никакого простого эффективного алгоритма для задачи 3-раскраски не видно, и рассуждать об этой задаче вообще сложно. Например, изначально может возникнуть впечатление, что в любом графе, не являющиеся 3-раскрашиваемым, присутствует “доказательство” в форме четырех узлов, являющихся взаимно смежными (для которых потребуются четыре разных цвета) — но это не так. Например, граф на рис. 8.10 не имеет 3-раскраски по более тонкой (хотя и объяснимой) причине; более того, можно привести намного более сложные графы, не являющиеся 3-раскрашиваемыми по причинам, для которых трудно найти компактное объяснение.

Рис. 8.10. Граф, не имеющим 3-раскраски

Более того, как вы сейчас убедитесь, в случае трех цветов задача уже становится очень сложной.

Доказательство NР-полноты задачи о 3-раскраске

(8.22) Задача о 3-раскраске является NP-полной.

Доказательство. Легко увидеть, почему задача принадлежит NP. Для заданных G и k одним из сертификатов, подтверждающих истинность ответа, является k-раскраска: за полиномиальное время можно убедиться в том, что в раскраске используется не более k цветов и никакая пара узлов, соединенных ребром, не окрашена в один цвет.

Как и другие задачи в этом разделе, задачу о 3-раскраске графа трудно связать с другой NP-полной задачей, виденной ранее, поэтому мы снова вернемся к 3-SAT. Заданный экземпляр 3-SAT с переменными x₁, ..., x_n и условиями C₁, ..., C_k будет решен с использованием “черного ящика” для решения задачи 3-раскраски.

Начало сведения выглядит вполне ожидаемо. Возможно, основное достоинство 3-раскраски при кодировании булевых выражений заключается в том факте, что мы можем связать узлы графа с конкретными литералами, а соединяя узлы ребрами, можно гарантировать, что им будут назначены разные цвета; это обстоятельство позволяет связать с одним узлом истинное, а с другим — ложное значение. С учетом сказанного мы определяем узлы и соответствующие каждой переменной и ее отрицанию Также определяются три “специальных узла” Т, F и В (сокращения от True, False и Base).

Для начала мы соединим каждую пару узлов v_i, ребром и соединим оба этих узла с Base (в результате чего образуется треугольник из v_i, и Base для каждого У). Также True, False и Baseсоединяются в треугольник. Простой граф G, определенный к настоящему моменту, изображен на рис. 8.11, и он уже обладает рядом полезных свойств.

♦ В любой 3-раскраске графа G узлам v_i и должны быть назначены разные цвета, и оба они должны отличаться от цвета Base.

♦ В любой 3-раскраске графа G узлам True, False и Base должны быть назначены все три цвета в некоторой перестановке. В дальнейшем эти три цвета будут называться цветами True, False и Base в зависимости от того, какому из узлов соответствует тот или иной цвет. В частности, это означает, что для всех i одно из значений v_i или получает цвет True, а другому достается цвет False. В оставшейся части этого построения будем считать, что переменной х_i значение 1 в заданном экземпляре 3-SAT присваивается в том, и только в том случае, если узлу v_i назначается цвет True.

Рис. 8.11. Начало сведения для задачи о 3-раскраске

Короче говоря, мы получили граф G, в котором любая 3-раскраска неявно определяет логическое присваивание для переменных в экземпляре 3-SAT. Теперь необходимо нарастить G так, чтобы только выполняющие присваивания могли быть расширены до 3-раскрасок полного графа. Как это сделать?

Как и в других сведениях 3-SAT, рассмотрим условие вида На языке 3-раскраски графа G это означает: “По крайней мере одному из узлов или v₃ должен быть назначен цвет True”. Итак, нам нужен маленький подграф, который можно присоединить к G, чтобы любая 3-раскраска, расширяющаяся на этот подграф, обладала свойством назначения цвета True по крайней мере одному из узлов или v₃. Найти такой подграф удается не сразу, но один из работающих вариантов изображен на рис. 8.12.

Этот подграф из шести узлов “присоединяется” к основному графу G в пяти существующих узлах: True, False и узлах, соответствующих трем литералам в условии, которое мы пытаемся представить (в данном случае и v₃). Теперь предположим, что в некоторой 3-раскраске G всем трем узлам или v₃ назначен цвет False. Тогда двум нижним затемненным узлам подграфа должен достаться цвет Base, а трем затемненным узлам над ними — соответственно цвета False, Base и True, а следовательно, для верхних затемненных узлов цветов уже не останется. Другими словами, 3-раскраска, в которой ни одному из узлов или v₃ не назначается цвет True, не может быть расширена до 3-раскраски этого подграфа².

Рис. 8.12. Присоединение подграфа для представления условия

Наконец, ручная проверка показывает, что если одному из узлов или v₃ назначен цвет True, весь подграф может иметь 3-раскраску.

Далее остается лишь завершить построение: мы начинаем с графа G, определенного выше, и для каждого условия в экземпляре 3-SAT присоединяем подграф из шести узлов, изображенный на рис. 8.12. Назовем полученный граф G'.

Утверждается, что заданный экземпляр 3-SAT выполним в том, и только в том случае, если граф G' имеет 3-раскраску. Сначала предположим, что для экземпляра 3-SAT существует выполняющее присваиванием. Определим раскраску G', окрасив Base, True и False в три разных цвета, а затем для каждого У назначим v цвет True, если х_i = 1, или цвет False, если х_i = 0. После этого назначается единственный свободный цвет. Наконец, как объяснялось выше, теперь эта 3-раскраска может быть расширена на каждый подграф условия, состоящий из шести узлов, что приведет к 3-раскраске всех G'.

И наоборот, предположим, что у G' существует 3-раскраска. В этой раскраске каждому узлу v_i назначается либо цвет True, либо цвет False; переменная x_i задается соответствующим образом. Теперь утверждается, что в каждом условии экземпляра 3-SAT по крайней мере один из литералов в условии имеет значение истинности 1. В противном случае всем трем соответствующим узлам в 3-раскраске G' был бы назначен цвет False, но, как было показано выше, в такой ситуации не существует 3-раскраски соответствующего подграфа условия, — возникает противоречие. ■

При k > 3 задача о 3-раскраске очень легко сводится к k-раскраске. Фактически все, что требуется, — взять экземпляр задачи 3-раскраски, представленный графом G, добавить k - 3 новых узлов и соединить эти новые узлы друг с другом и с каждым узлом в G. Полученный граф является k-раскрашиваемым в том, и только в том случае, если исходный граф G является 3-раскрашиваемым. Следовательно, k-раскраска для всех k > 3 также является NР-полной.

Заключение: о проверке гипотезы четырех цветов

В завершение этого раздела стоит рассказать и о том, как закончилась история гипотезы четырех цветов для карт на плоскости. Более чем через 100 лет гипотеза была доказана Аппелем и Хакеном в 1976 году. Структура доказательства была простой индукцией по количеству областей, но шаг индукции включал около двух тысяч относительно сложных случаев, проверку которых пришлось поручить компьютеру. Многие математики были недовольны таким результатом: они надеялись получить доказательство, которое бы давало представление о том, почему гипотеза была истинной, — а вместо этого получили перебор запредельной сложности, проверку которого нельзя было осуществить вручную. Задача поиска относительно короткого, доступного доказательства все еще остается открытой.