36.15

(а) Блок А, используемый при сведении задачи 3-SAT к задаче HAM-CYCLE.

(b)-(c) Если блок А входит в граф G и соединяется с ним лишь в угловых вершинах, то любой гамильтонов цикл в графе G проходит через А одним из двух способов, (d) Символическое изображение блока А

36.16

Блок В, используемый при сведении задачи 3-CNF-SAT к задаче HAM-CYCLE. Путь из вершины Ь\ в 64 не может проходить по всем трём рёбрам 61-626 62-63 и 63-64, но может проходить по любому собственному подмножеству этого множества, как показано в (а)-(е). Символическое изображение (f) подчёркивает это свойство: по крайней мере один из трёх путей, на которые указывают стрелки, должен войти в гамильтонов путь.

формула была выполнимой. В нашей конструкции мы будем использовать некоторые блоки - куски графа, обладающие некоторыми специальными свойствами.

Первый из используемых блоков (блок А) показан на рис. 36.15 (а). Предположим, что А входит в некоторый граф G, причём лишь вершины а, а, 6, 6 могут быть соединены с остальными вершинами графа. Тогда гамильтонов цикл в графе G (если

таковой существует) должен проходить через вершины z\--Z4,

и это может происходить лишь двумя способами (рис. 36.15 (Ь) и (с)). Поэтому можно символически изображать блок А как на

рис. 36.15 (d), имея в виду, что он заменяет два ребра а-а и 6--6

с таким дополнительным условием: гамильтонов цикл должен содержать ровно одно из двух этих рёбер.

Второй используемый блок (В) показан на рис. 36.16. Предположим, что блок В входит в некоторый граф G, причём В может быть связан с остальной частью графа только через вершины 61, 62, 63 и 64. Можно проверить, что гамильтонов цикл графа G (если он существует) не может проходить одновременно через три ребра (61,62), (62,63) и (63,64), поскольку тогда цикл не смог бы пройти через все вершины В. Однако гамильтонов цикл может проходить через любое собственное подмножество этой тройки ребер, как показано на рис. 36.16 (а)-(е). (ещё два симметричных варианта получатся, если перевернуть (Ь) и (е)). Блок В будем символически изображать как на рис. 36.16(f) (стрелки на рисунке означают, что хотя бы один из трёх путей, на которые они указывают, должен войти в в гамильтонов цикл).

Теперь у нас всё готово для построения графа G, соответствующего формуле из класса 3-CNF. Этот граф G будет состоять из нескольких блоков типа А и В (рис. 36.17).

36.17 Граф G, построенный по формуле р> = (х\ У х2 У ~х3) Л (х\ У -1Ж2\/жз) Л (ж! У х2У х3). Для этой формулы имеется выполняющий набор х\ = О, Ж2 = 1, жз = 1. Соответствующий гамильтонов цикл показан серым. Отметим, что если в наборе хт = 1, то в цикл входит ребро ет, а если хт = 0, то ёт.

Предположим, что формула р> составлена из к дизъюнкций Ci, С2,... , Cki каждая из которых содержит ровно 3 литерала. Для каждой дизъюнкции С; изготовим блок типа В; обозначим через bij соответствующие копии вершин bj. Соединим вершины 64 и 6г+1д для г = 1, 2,... , к - 1.

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

Чтобы дать гамильтонову циклу возможность пройти по ет или ет, добавим в граф рёбра (х"т,хт+1) для то = 1,2,..., то- 1. а также ещё два ребра: (61,1, х[) и (6,4? ж") (верхнее и нижнее рёбра, рис. 36.17).

Построение графа ещё не окончено, мы должны связать блоки графа, соответствующие переменным формулы, с блоками, соответствующими её дизъюнкциям. Если j-ый литерал дизъюнкции Ci есть хт, соединим ребро (bij, fr;,j+i) с ребром ет с помощью А-блока. Если же j-ым литералом дизъюнкции С; является хт, мы соединим с помощью А-блока рёбра (b4-j, fr«,j+i) и ёт. Так, в примере рис. 36.17 имеем С2 = Х\У ~х2 У Ж3, поэтому мы размещаем три А-блока между рёбрами

(62,1, Ь2,2) и ei;

(62,2, Ь2,г) и ё2;

(2,3, Ь2Л) и е3.

Отметим, что слова «соединить два ребра с помощью А» означают, что каждое из них заменяется на цепочку из пяти новых ребер и добавляются связывающие их рёбра и вершины, как это предусмотрено конструкцией А-блока (рис. 36.15).

Один литерал 1т может встречаться в нескольких дизъюнкциях (например, -1Ж3 на рис. 36.17). В этих случаях требуется «подключить» к соответствующему ребру несколько А-блоков; это можно сделать, если входящие в А-блоки цепочки из пяти рёбер соединить последовательно, как показано на рис. 36.18.

Мы утверждаем, что формула р> выполнима, если и только если построенный граф G имеет гамильтонов цикл. Предположим сначала, что в графе G есть гамильтонов цикл h, и докажем вы-

36.18

Подробности конструкции для случая, когда ребро ет (или ёт) входит в несколько А-блоков.

(a)Фрагмент рис. 36.17.

(b)Граф, который этот фрагмент символизирует.

полнимость формулы Lp.

Цикл h должен быть устроен так:

сначала проходим ребро (6iji,a;/1) (будем считать, что слева направо);

затем для каждого т проходим по одному (и только одному) из рёбер ет, ет;

проходим по ребру (6,4? хп) справа налево, проходим все 5-блоки снизу вверх

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

Теперь можно указать выполняющий набор для формулы Lp: если ребро ет принадлежит гамильтонову циклу h, положим хт = 1. В противном случае цикл h содержит ребро ёт, и мы полагаем хт - 0.

Докажем, что построенный набор является выполняющим для формулы Lp. Рассмотрим какую-то дизъюнкцию С; и соответствующий ей В-блок. Каждое ребро (6;j, 6j,j+i) связано с помощью А-блока либо с ребром ет, либо с ребром ёт (в зависимости от того, является ли j-м литералов в дизъюнкции С; переменная хт или её отрицание ~хт). Цикл h проходит через ребро (6;j, &;j+i), если и только если соответствующий литерал равен 0. Вспомним, что h не может проходить через все три ребра (61,62), (&г,2? г,з) и (bi,3, ,4) в -В-блоке, поэтому хотя бы одному из этих ребер соответствует истинный литерал дизъюнкции, и дизъюнкция С; истинна. Это можно сказать про любую дизъюнкцию С;, так что все они истинны и формула Lp истинна для построенного набора значений переменных.

Обратно, пусть Lp истинная для некоторого набора значений переменных. Построим цикл h по описанным выше правилам (цикл содержит ребро ет при хт = 1 и ребро ёт при хт = 0; цикл проходит через ребро (68J-, 68J i), если и только если j-й литерал дизъюнкции С\ равен 0 на данном наборе. Очевидно, описанные правила позволяют построить гамильтонов цикл по выполняющему набору.

Отметим, наконец, что граф G имеет полиномиальный размер