Теорема. Приблема ориентированного гамильтонова цикла NP- полна.
Доказательство. Для доказательства NP-полноты задачи ОГЦ, построим алгоритм полиномиального сведения 3-КНФ к ОГЦ. Пусть F есть 3-КНФ с переменными x1, x 2,…, x n . Покажем, что граф G= (V, E) имеет гамиль- тонов цикл в том и только в том случае, если формула F выполнима.
В доказательстве будут использованы блоки графа, обладающие специальными свойствами (рис. 36.15).
Первый из используемых блоков (A) показан на рис.35.15(a). Предположим, что A входит в граф G, причем лишь вершины a, a’ ,b, b’ могут быть соединены с остальными вершинами графа. Тогда гамильтонов цикл в графе G должен проходить через вершины z1, z2, z3, z4 , что возможно двумя способами, изображенными на рис.36.15(б) и (в).
Рис.36.15.
Второй блок (B) показан на рис.36.16. Предположим, что блок B входит в граф G, тогда блок B может быть связан с остальной частью графа только через вершины b 1, b 2, b 3, b 4. Можно проверить, что гамильтонов цикл, если он существует, не может проходить одновременно через три ребра (b 1, b 2), (b 2, b 3), (b 3, b 4), поскольку цикл не мог бы пройти через все вершины B. Однако гамильтонов цикл может проходить через любое собственное подмножество этой тройки, как видно из рис.36.16(а-д).
Рис.36.16
Граф G, соответствующий формуле F, строится из блоков типа A и B (рис. 36.17). Пусть формула F составлена из k дизъюнкций F1, F2,…,Fk, каждая из которых содержит ровно 3 литерала. Для каждой дизъюнкции Fi строим блок B; обозначим через bi,j соответствующие копии вершин b j. Соединим вершины b i,4и b i+1, 1 для i = 1,2,…,k-1.
Далее, каждой переменной xm формулы F мы поставим в соответствие пару вершин x’m , x’’m, которые соединим двумя ребрами e m и e’m .
(На самом деле это не ребра, а сложные конструкции, так что кратных ребер не будет). Идея состоит в том, что гамильтонов цикл будет проходить через ребро e m , если в выполняющем наборе переменная x m принимает значение 1, и через e’m , если эта переменная принимает значение 0.
Чтобы дать возможность гамильтонову циклу пройти по e m или e’m , добавим в граф ребра (x’’m , x’m+1) для m = 1,2,…,n-1, а также два ребра:
(b1,1, x’1) и (b k,4, x’’4) (верхнее и нижнее ребра, рис.36.17).
Теперь надо связать блоки графа, соответствующие переменным формулы, с блоками, соответствующими ее дизъюнкциям. Если j-й литерал дизъюнкции Fi есть x m , соединим ребро (b i, j ,b i, j+1) с ребром e m с помощью A-блока, а если Øxm – с ребром ēm. Так в примере рис.36.17 для F2 = x1 Ú Øx2 Ú x3 размещаем три A-блока между ребрами:
(b 2, 1, b 2, 2) и e1 ; (b 2, 2, b 2, 3) и ē2; (b 2, 3, b 2, 4) и e3 .
Слова “соединить два ребра с помощью A” означают, что каждое из них заменяется на цепочку из пяти новых ребер и добавляются связывающие их ребра и вершины, как это предусмотрено конструкцией A-блока (рис.36.15).
Если литерал ym встречается в нескольких дизъюнкциях (например,
Ø x 3 на рис.36.17), то к соответствующему ребру “подключается” несколько A-блоков. Это можно сделать, если входящие в A-блоки цепочки из пяти ребер соединить последовательно, как показано на рис.36.18.
Формула F выполнима, если и только если построенный граф имеет гамильтонов цикл. Допустим, что в графе G есть гамильтонов цикл h, и докажем выполнимость формулы F. Цикл h должен быть устроен так:
- сначала проходим ребро (b1,1, x’1) слева направо;
- затем для каждого m проходим по одному (и только одному) из ребер
e m , e’m ;
- проходим по ребру (b k,4, x’’n) справа налево;
- проходим все B-блоки снизу вверх.
Заметим, что, проходя по ребрам e m и ē m, проходят по A-блокам, кото-
рые к ним присоединены, в противном случае переменная x m не входит в формулу и ее можно вообще удалить, так что кратных ребер нет.
Рис.36.17. Рис.36.18.
Укажем выполняющий набор для формулы F: если ребро e m принадлежит гамильтонову циклу h, положим x m = 1, в противном случае h содержит ребро ē m и мы полагаем x m = 0.
Покажем, что построенный набор является выполняющим для формулы F. Рассмотрим дизъюнкцию Fi и соответствующий ей B-блок. Каждое ребро (b i, j ,b i, j+1) связано с помощью A-блока либо с ребром e m, либо с ребром ēm. Цикл h проходит через ребро (b i, j ,b i, j+1), если и только если соответствующий литерал равен 0. Цикл h не может проходить через все три ребра (b i, 1 , b i, 2), (b i, 2 , b i, 3), (b i, 3 ,b i, 4) в B-блоке, поэтому хотя бы одному из этих ребер соответствует истинный литерал дизъюнкции и дизъюнкция Fi истинна. Аналогичное можно сказать про любую дизъюнкцию Fi , так что все они истинны и формула F истинна для построенного набора значений своих переменных.
Обратно, пусть формула F истинна для некоторого набора значений переменных. Построим цикл h по описанным выше правилам: цикл со- держит ребро e m, когда x m = 1, и ребро ē m, когда x m = 0; цикл проходит через ребро (b i, j ,b i, j+1), если и только если j-ый литерал дизъюнкции Fi равен 0 на данном наборе. Очевидно, описанные правила позволяют построить гамильтонов цикл по выполняющему набору.
Граф G имеет полиномиальный размер, т.е. его размер ограничен полиномом от размера формулы F, и построение графа G по формуле F осуществляется за полиномиальное время от входа, т.е. длины представления формулы F). Таким образом, задача 3-КНФ полиномиально сводима к задаче ОГЦ, что и требовалось доказать. “
