(т.е. его размер ограничен полиномом от размера формулы р>), и что построение графа G по формуле р> проводится за полиномиальное время. Таким образом, задача 3-CNF-SAT сводится за полиномиальное время к задаче HAM-CYCLE, что и требовалось доказать.

36.4.4. Задача коммивояжёра

С задачей о гамильтоновом цикле тесно связана задача коммивояжёра (traveling salesman problem, TSP). В этой задаче требуется найти оптимальный маршрут посещения га городов.

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

TSP = {(G, с,k) : G = (V, Е) - полный граф,с : V X V -> Z - функция стоимости, к G Z и в G есть гамильтонов цикл стоимости не более к}.

Теорема 36.15

Задача коммивояжера является NP-полной. Доказательство

Очевидно, задача TSP принадлежит классу NP (в качестве сертификата можно взять гамильтонов цикл стоимости не выше к).

Чтобы убедиться, что задача коммивояжёра является NP-трудной, сведём к ней задачу HAM-CYCLE. Чтобы узнать, есть ли в графе G гамильтонов цикл, построим полный граф G с теми же вершинами; рёбра из G будут иметь цену 0, а все остальные рёбра - цену 1. Очевидно, что в графе G существует путь коммивояжёра стоимости 0 в том и только в том случае, когда граф G имел гамильтонов цикл.

Упражнения

36.5-1

Задача изоморфизма с подграфом subgraph-isomorphism problem требует выяснить для пары графов G\ и G2, изоморфен ли граф G\ некоторому подграфу графа G2. Докажите, что эта задача NP-полна.

36.5-2

Дана целочисленная матрица А размера т X п и то-мерный вектор Ь. Задача 0-1 целочисленного линейного программирования (01 integer-progeamming problem) требует выяснить, существует ли такой га-мерный вектор х с элементами из множества {0,1}, что Ах Ь. Докажите, что данная задача NP-полна. (Указание: сведи-

те к ней задачу 3-CNF-SAT.) 36.5-3

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

36.5-4

Задача о разбиении на равные части (set-partition problem) состоит в следующем: дано множество целых чисел S; выяснить, можно ли разбить его на две части с равными суммами, то есть найти множество ACS, для которого YlxeA х = 2xes\Ax- Покажите, что эта задача является NP-полной.

36.5-5

Докажите NP-полноту задачи о гамильтоновом пути (упр. 36.26). 36.5-6

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

36.5-7

Профессор утверждает, что конструкцию А-блока в доказательстве теоремы 36.14 можно упростить, исключив вершины z3 и z4, а также вершины под над ними. Прав ли он - или такое упрощение создаст не предвиденные им проблемы?

Задачи

36-1 Независимое множество

Множество вершин V С V графа G = (V, Е) называется независимым (independent), если никакие две его вершины не соединены ребром. Задача о независимом множестве (independent-set problem) состоит в отыскании в данном графе независимого множества максимального размера.

a.Сформулируйте соответствующую задачу разрешения и докажите ее NP-полноту.

b.Предположим, мы имеем «чёрный ящик», с помощью которого можем решать задачу из пункта (а) за единичное время. Как с его помощью находить независимое множество максимального размера (а не только этот размер) за полиномиальное (от \V\ и \Е\) время?

Хотя задача о независимом множестве в общей постановке NP-полна, некоторые её частные случаи могут быть решены за полиномиальное время.

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

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

ность вашего алгоритма и оцените время его работы. (Указание: используйте результаты раздела 27.3.) 36-2 Раскраска графа

Назовём к-раскраской (/г-coloring) неориентированного графа G = (V, Е) функцию с : V -> {1, 2,... , к}, для которой с(и) ф с[у) для всех рёбер (и, v) £ Е. Если считать, что числа 1,2,... , к обозначают к различных цветов, a c(v) есть цвет вершины v, то условие на раскраску состоит в том, что концы любого ребра имеют разные цвета. Задача о раскраске графа (graph-coloring problem) состоит в нахождении минимального количества цветов, необходимого для раскраски данного графа G с соблюдением этого условия.

a.Постройте эффективный алгоритм, находящий 2-раскраску данного графа (если таковая существует).

b.Сформулируйте задачу разрешения, соответствующую задаче о раскраске графа. Докажите, что сформулированная вами задача разрешима за полиномиальное время в том и только том случае, если задача о раскраске графа разрешима за полиномиальное время.

c.Рассмотрим язык 3-COLOR, состоящий из графов, для которых существует 3-раскраска. Покажите, что если язык 3-COLOR является NP-полным, то и задача пункта (Ь) является NP-полной.

Чтобы установить NP-полноту языка 3-COLOR, сведём к нему язык 3-CNF-SAT. Пусть имеется формула р> из класса 3-CNF, состоящая из т дизъюнкций и содержащая переменные х\, х2, • • • , хп. Построим по ней граф G = (V,E), который можно раскрасить в три цвета в том и только том случае, когда формула р> выполнима.

Для каждой переменной жг- формулы р> мы добавим в граф две вершины (одна будет обозначаться жг-, другая - -*Xi). Кроме того, для каждой дизъюнкции мы добавим по 5 вершин. Наконец, нам понадобятся три специальные вершины, которые мы будем условно называть true, false и red.

Теперь опишем рёбра графа G. Они делятся на два типа, которые мы условно назовём «литеральные» и «дизъюнктивные». Три литеральных ребра соединяют между собой вершины true, false и red (тем самым гарантируя, что каждая из трёх вершин будет окрашена в свой цвет). Кроме того, для каждой переменной жг- имеется треугольник из литеральных рёбер, включающий в себя вершины жг-, -1Жг- и red. (К дизъюнктивным рёбрам мы ещё вернёмся.)

d.Рассмотрим произвольную 3-раскраску графа G с описанными литеральными ребрами. Докажите, что из каждой пары вершин жг-, -1Жг- одна покрашена в цвет c(true), то есть в тот же цвет, что вершина true, а другая - в цвет c(false). Покажите, что есть естественное соответствие между 3-раскрасками такого графа и наборами значений переменных.

Остается описать дизъюнктивные рёбра; они нужны, чтобы наложить на 3-раскраску условия, соответствующие истинности