10.5. ЕЩЕ НЕСКОЛЬКО NP-ПОЛНЫХ ЗАДАЧ

Теперь приступим к доказательству того, что каждая из задач, упомянутых в теореме -полна. Для этого покажем, что в нее прямо или косвенно преобразуется выполнимость. Дерево на рис. 10.6 иллюстрирует последовательность преобразований, которые мы в действительности будем применять. Если отец для

Рис. 10.6. Последовательность преобразований для различных трудных задач.

на рис. 10.6, то мы покажем, что задача полиномиально трансформируема в

Теорема 10.5. Задача КНФ-выполнимости полиномиально трансформируема в задачу о клике. Поэтому задача о клике NP-полна.

Доказательство. Пусть формула в КНФ, где сомножители; каждая формула имеет вид литерал. Построим неориентированный граф узлами которого служат пары целых чисел для и Первая компонента такой пары представляет сомножитель, а вторая — литерал, входящий в него. Таким образом, каждый узел графа естественным образом соответствует конкретному вхождению в конкретный сомножитель.

Ребрами графа служат пары для которых и Неформально, узлы и смежны в если они соответствуют различным сомножителям и можно так присвоить значения переменным из литералов чтобы оба литерала приняли значения 1 (тем самым давая значение 1 формулам Иными словами, либо либо переменные, входящие в литералы различны.

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

построить алгоритм с полиномиально ограниченным временем работы для задачи КНФ-выполнимости, построив по граф G, содержащий -клику тогда и только тогда, когда формула выполнима. Итак, покажем, что для того, чтобы граф содержал -клику, необходимо и достаточно, чтобы формула была выполнима.

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

Мы утверждаем, что множество узлов образует -клику. Если бы это было не так, то нашлись бы такие что и узлы и не соединены ребром. Отсюда следовало бы, что (по определению множества ребер графа Но это невозможно, поскольку в силу выбора переменных

Необходимость. Пусть содержит -клику. Первые компоненты узлов, составляющих такую клику, должны быть различны, поскольку узлы с одинаковыми первыми компонентами не соединяются ребрами. Так как в этой клике в точности узлов, то узлы клики взаимно однозначно соответствуют сомножителям формулы Пусть узлы клики имеют вид Пусть где и где и у — переменная}. Иными словами, множества переменных и отрицаний переменных соответственно, представленных узлами клики. Тогда ибо в противном случае какие-то узлы и для которых соединялись бы ребром. Если положить переменные из равными 1, а из равными О, то каждая формула примет значение 1. Поэтому формула выполнима.

Пример 10.5. Рассмотрим формулу Литералы таковы:

Конструкция из теоремы 10.5 дает граф, изображенный на рис. 10.7. Например, узел [1, 1] не соединен с [1, 2], потому что первые компоненты одинаковы, и с [3, 2], потому что а с остальными тремя узлами соединен.

В формуле три сомножителя, и оказывается, что в графе на рис. 10.7 две -клики, а именно В первой клике представлены три литерала

Рис. 10.7. Граф, построенный по теореме 10.5.

Это переменные без отрицаний, и первая клика соответствует присвоению значений выполняющему Вторая клика соответствует другому набору значений, обращающему формулу в истинную, а именно

Теорема 10.6. Задача о клике полиномиально трансформируема в задачу об узельном покрытии. Поэтому задача об узельном покрытии NP-полна.

Доказательство. Пусть дан неориентированный граф Рассмотрим его дополнение где Мы утверждаем, что множество является кликой в тогда и только тогда, когда является узельным покрытием графа Действительно, если клика в то никакое ребро в не соединяет никакие два узла в Поэтому всякое ребро в инцидентно по меньшей мере одному узлу из откуда следует, что есть узельное покрытие графа Аналогично, если есть узельное покрытие графа то каждое ребро из инцидентно по меньшей мере одному узлу из Поэтому никакое ребро из не соединяет два узла из Следовательно, каждая пара узлов из соединена в значит, клика в

Чтобы узнать, существует ли -клика, построим граф и выясним, содержит ли он узельное покрытие размера Разумеется, поданному стандартному представлению графа и числа можно найти представление графа и числа за время, полиномиально зависящее от длины представления

Пример 10.6. Граф на рис. 10.8,а содержит две -клики Граф на рис. 10.8,6 содержит соответствующие узельные покрытия размера 2. Граф содержит (среди других) -клики а граф соответствующие узельные покрытия размера

Рис. 10.8. а — граф его дополнение

Теорема 10.7. Задача об узельном покрытии полиномиально трансформируема в задачу о множестве узлов, разрезающих циклы. Поэтому задача о множестве узлов, разрезающих циклы, NP-полна.

Доказательство. Пусть неориентированный граф, ориентированный граф, полученный заменой каждого ребра графа двумя ориентированными ребрами. Точнее, пусть где Поскольку каждое ребро из заменено циклом графа то множество разрезает циклы в (каждый цикл графа содержит узел из тогда и только тогда, когда узельное покрытие для Кроме того, представление графа легко найти по за полиномиальное время.

Теорема 10.8. Задача об узельном покрытии полиномиально трансформируема в задачу о множестве ребер, разрезающих циклы. Поэтому задача о множестве ребер, разрезающих циклы, NP-полна.

Доказательство. Пусть неориентированный граф, ориентированный граф, где состоит из (см. рис. 10.9)

Пусть множество ребер графа содержащих по крайней мере одно ребро из каждого цикла в Заменим каждое ребро из имеющее вид , ребром . Полученное множество обозначим через Мы утверждаем, что и содержит по крайней мере одно ребро из каждого цикла. (Единственное ребро, выходящее из идет в так что принадлежит любому циклу, содержащему

Рис. 10.9. а — неориентированный граф G; б - соответствующий ориентированный граф Узельное покрытие соответствует множеству ребер, разрезающих циклы.

Не умаляя общности, будем считать, что

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

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

Теорема 10.9. Задача об узельном покрытии полиномиально трансформируема в задачу о гамильтоновом цикле для ориентированных графов. Поэтому задача о гамильтоновом цикле в ориентированном графе NP-полна.

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

Рис. 10.10. Представление ребра

содержащий гамильтонов цикл тогда и только тогда, когда некоторое -элементное подмножество множества V покрывает ребра графа

Пусть Обозначим ребро через Пусть новые символы. Множество будет включать в себя по одному узлу для каждого и еще по четыре узла для каждого ребра графа Точнее,

и ребро инцидентно

Прежде чем формально описывать ребра графа дадим объяснение на интуитивном уровне. Ребро графа представляется подграфом с четырьмя узлами (рис. 10.10).

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

Граф можно представлять себе состоящим из списков, по одному списку для каждого узла. Список для узла содержит все ребра, инцидентные узлу и расположенные в специальном порядке. Из каждого узлд идут ребра к таким узлам что первое ребро в списке для Далее, в каждый узел идут ребра из если последнее ребро в списке для Из идет ребро в если ребро непосредственно следует за в списке для Эти ребра вместе с ребрами

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

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

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

Необходимость. Пусть в графе есть гамильтонов цикл. Этот цикл можно разбить на путей, каждый из которых начинается в некотором узле и кончается в каком-то узле Из наших предыдущих рассмотрений возможных путей через подграф с четырьмя узлами, представляющий какое-то ребро (как на рис. 10.10), вытекает, что существует такой узел что каждый узел на пути из в имеет вид либо или где ребро графа либо или где ребро Поэтому первая компонента каждого узла, лежащего на пути из представляет собой либо либо узел, смежный с Пути из можно, таким образом, поставить в соответствие некоторый узел Для каждого узла графа ребро должно быть инцидентно одному из узлов графа поставленных в соответствие путям. Следовательно, эти узлов образуют узельное покрытие графа Отсюда заключаем, что содержит гамильтонов цикл тогда и только тогда, когда в существуют такие узлов, что каждое ребро из инцидентно одному из этих узлов.

Пример 10.7. Пусть граф с узлами и ребрами (рис. 10.11,а). Граф построенный в теореме 10.9, изображен на рис. Гамильтонов цикл в основанный на узельном покрытии указан жирными линиями.

Теорема 10.10. Задача о гамильтоновом цикле для ориентированных графов полиномиально трансформируема в задачу о гамильтоновом цикле для неориентированных графов. Поэтому задача существования гамильтонова цикла в неориентированном графе NP-полна.

Рис. 10.11. (см. скан) Граф с гамильтоиовым циклом: а — неориентированный граф ориентированный граф

Доказательство. Пусть ориентированный граф, неориентированный граф, где состоит из ребер

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

должна изменяться в порядке или обратном к нему. Будем считать, что реализуется первый из этих двух случаев; тогда ребра типа 3, у которых вторая компонента меняется с 2 на О, образуют ориентированный гамильтонов цикл в Обратно, гамильтонов цикл в можно превратить в неориентированный гамильтонов цикл в заменив каждое ребро путем

Теорема 10.11. Задача об узельном покрытии полиномиально трансформируема в задачу о покрытии множествами. Поэтому задача о покрытии множествами NP-полна.

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

Теорема 10.12. Задача -выполнимости полиномиально трансформируема в задачу раскрашиваемости.

Доказательство. Пусть дана формула в -КНФ с переменными и сомножителями. Покажем, как построить за время, ограниченное полиномом от неориентированный граф узлами, который можно раскрасить цветов тогда и только тогда, когда формула выполнима.

Пусть соответственно переменные и сомножители формулы Пусть новые символы. Без потери общности будем считать, что поскольку любую формулу в -КНФ, число различных переменных которой не превосходит 3, можно проверить на выполнимость за время, линейно зависящее от ее длины, не прибегая к раскрашиваемости. Узлы графа таковы:

Ребра графа

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

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

Представим себе, что тому из узлов и , который раскрашен в специальный цвет, приписано значение 0. Теперь рассмотрим цвет, приписанный узлам Узел смежен по крайней мере с из узлов Так как мы предположили, что то для каждого найдется такое что узел смежен как с так и с Поскольку один из узлов или раскрашен в специальный цвет, то не может быть раскрашен в специальный цвет.

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

Рис. 10.12. Граф с хроматическим числом 4.

Пример 10.8. Пусть Заметим, что здесь в каждом сомножителе по два, а не по три члена. Это изменение не влияет на конструкцию графа в доказательстве теоремы 10.12, но позволяет рассматривать формулы, содержащие только три переменные, и графы, раскрашиваемые в четыре цвета. (Аналог теоремы 10.12 для -КНФ верен, но неинтересен. Так как существует алгоритм для -КНФ с полиномиально ограниченным временем работы, то выполнимость для -КНФ трансформируема за полиномиальное время в любую задачу.) Результирующий граф показан на рис. 10.12. В качестве цветов взяты (специальный). Эта -раскраска соответствует решению

Теорема 10.13. Задача раскрашиваемости полиномиально трансформируема в задачу о точном покрытии. Поэтому задача о точном покрытии NP-полна.

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

Для каждого узла зададим множества

Для каждого ребра зададим множества

Установим соответствие между -раскрасками графа и точными покрытиями набора множеств, определенных равенствами (10.5) и (10.6). Предположим, что имеет -раскраску, в которой узлу приписан цвет где можно считать целым числом между Тогда легко проверить, что набор множеств, состоящий из для каждого и тех одноэлементных множеств для которых при всех образует точное покрытие. Для доказательства заметим, что если ребро, то поэтому Ясно, что если х и у не смежны, то не пересекаются, а множество выбирается, только если оно не пересекается ни с одним из выбранных множеств.

Обратно, допустим, что набор множеств, определенных в (10.5) и (10.6), имеет точное покрытие Тогда для каждого найдется такое единственное число что Это вытекает из того, что каждый узел должен принадлежать точно одному множеству из У. Мы утверждаем, что для получения -раскраски графа можно раскрасить каждый узел в цвет Допустим, что это не так.

Тогда существует такое ребро что . А тогда каждое из множеств и содержит и потому У не является точным покрытием вопреки предположению.