19
правок
Изменения
→Доказательство принадлежности к NPH
Доказательство взято из книги <ref>[Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. Структуры данных и алгоритмы = Data Structures and Algorithms. — Издательский дом «Вильямс», 2000. — С. 384. — ISBN 5-8459-0122-7 (рус.) / ISBN 0-201-00023-7 (англ.)]</ref>
Сведем задачу о выполнимости булевых формул вида 3-КНФ (3CNF SAT) к HAM. Начнем построение экземпляра HAM по булевой формуле в 3КНФ. Пусть формула имеет вид <math>E = e_1 \land e_2 \land... \land e_k</math>, где каждое <math>e_i</math> - дизъюнкт, представляющий собой сумму трех литералов, скажем, <math>e_i = (\alpha_{i1} + \alpha_{i2} + \alpha_{i3})</math>. Пусть <math>x_1, x_2, ..., x_n</math> - переменные в формуле <math>E</math>. Для всех дизъюнктов и переменных строятся подграфы, как показано на рисунке 1рисунках.
Для каждой переменной <math>x_i</math> строится подграф <math>H_i</math>, структура которого показана на рисунке 1аа). Здесь <math>m_i</math> - большее из чисел вхождений <math>\bar{x_i}</math> и <math>x_i</math> в <math>E</math>. Узлы <math>c_{ij}</math> и <math>b_{ij}</math>, расположенные в двух столбцах, соединены между собой дугами в обоих направлениях. Кроме того, каждое <math>b</math> имеет дугу, ведущую в <math>c</math>, расположенное на ступеньку ниже, т.е., если <math>j < m_i</math>, то <math>b_{ij}</math> имеет дугу, ведущую в <math>c_{i,j+1}</math>. Аналогично для <math>c_{ij}</math>. Наконец, есть верхний узел <math>a_i</math>, из которого дуги ведут в <math>b_{i0}</math> и <math>c_{i0}</math>, и нижний узел <math>d_i</math>, в который ведут дуги из <math>b_{im_i}</math> и <math>c_{im_i}</math>.
На рисунке 1б б) показана структура графа в целом. Каждый шестиугольник представляет один подграф, построенный для переменной (его структура показана на рисунке 1аа). Шестиугольники расположены циклически, и из нижнего узла каждого подграфа дуга ведет в верхний узел следующего.
[[Файл:Picture_aho_graph1.png]] [[Файл:Picture_aho_graph2.png]] [[Файл:Picture_aho_graph3.png]]
Допустим, граф на рисунке 1б б) имеет ориентированный гамильтонов цикл. Не ограничивая общности, можно считать, что этот цикл начинается в <math>a_1</math>. Если затем он переходит в <math>b_{10},</math>, то на следующем шаге он обязательно перейдет в <math>c_{10}</math> (иначе <math>c_{10}</math> не появится в цикле). В самом деле, если цикл переходит из <math>a_{1}</math> в <math>b_{10}</math>, а затем - в <math>c_{11}</math>, то <math>c_{10}</math> никогда не появится в цикле, поскольку оба его предшественника (<math>a_{0}</math> и <math>b_{10}</math>) уже содержатся в нем.
Таким образом, если начало цикла имеет вид <math>a_{1}</math>, <math>b_{10}</math>, то далее он должен спускаться "лесенкой", переходя из стороны в сторону:
Закончив обход подграфа <math>H_1</math>, цикл должен перейти в <math>a_2</math>, где снова возникает выбор следующего перехода - в <math>b_{20}</math> или в <math>c_{20}</math>. Однако в силу тех же аргументов, которые приведены для <math>H_1</math>, после того, как сделан выбор направления вправо или влево от <math>a_{2}</math>, путь обхода <math>H_{2}</math> уже зафиксирован. Вообще, при входе в каждый <math>H_{i}</math>, есть выбор перехода влево или вправо, но никакого другого. Иначе некоторый узел обречен быть недоступным, т.е. он не сможет появиться в ориентированном гамильтоновом цикле, поскольку все его предшественники появились в нем ранее.
В дальнейшем это позволит нам считать, что выбор перехода из <math>a_{i}</math> в <math>b_{i0}</math> означает приписывание переменной <math>x_{i}</math> значения "истина", а перехода в <math>c_{i0}</math> - значения "ложь". Поэтому граф на рисунке 1б б) имеет <math>2^n</math> ориентированных гамильтоновых циклов, соответствующих <math>2^n</math> возможным подстановкам для <math>n</math> переменных.
Однако на рисунке 1б б) изображен лишь скелет графа, порождаемого по формуле <math>E</math>, находящейся в 3-КНФ. Каждому дизъюнкту <math>e_{i}</math> ставится в соответствие подграф <math>I_{j}</math> (рисунок 1вв). Он обладает тем свойством, что если цикл входит в <math>r_{j}</math>, то должен выходить из <math>u_{j}</math>. Аналогично для <math>s, v</math> и <math>t, w</math> (доказательство этого утверждения см. в книге "Введение в теорию автоматов, языков и вычислений", Дж. Хопкрофт, Р. Мотвани, Дж. Ульман).
В завершение построения графа <math>G</math> для формулы <math>E</math> соединяем подграфы <math>I</math> и <math>H</math> следующим образом. Допустим, у дизъюнкта <math>e_i</math> первым литералом является <math>x_i</math>, переменная без отрицания. Выберем некоторый узел <math>c_{ip}</math>, где <math>p</math> от 0 до <math>m_{i}</math> - 1, ранее не использованный для соединения с подграфами <math>I</math>. Введем дуги, ведущие из <math>c_{ip}</math> в <math>r_{j}</math> и из <math>u_{j}</math> в <math>b_{i,p+1}</math>. Если же первым литералом дизъюнкта <math>e_j</math> является отрицание <math>\bar{x_i}</math>, то нужно отыскать неиспользованный узел <math>b_{ip}</math>, а затем соединить <math>b_{ip}</math> с <math>r_{j}</math> и <math>u_{j}</math> с <math>c_{i,p+1}</math>
====Доказательство достаточности====
Предположим, существует подстановка <math>T</math>, удовлетворяющая формуле <math>E</math>. Построим ориентированный гамильтонов цикл следующим образом.
# Вначале выберем путь, обходящий только подграфы <math>H</math> (т.е. граф, изображенный на рисунке 1бб) в соответствии с подстановкой <math>T</math>. Таким образом, если <math>T(x_{i}) = 1</math>, то цикл переходит из <math>a_{i}</math> в <math>b_{i0}</math>, а если <math>T(x_{i}) = 0</math>, то он переходит из <math>a_i</math> в <math>c_{i0}</math>.
#Однако цикл, построенный к данному моменту, может содержать дугу из <math>b_{ip}</math> в <math>c_{i,p+1}</math>, причем у <math>b_{ip}</math> есть еще одна дуга в один из подграфов в <math>I_{j}</math>, который пока не включен в цикл. Тогда к циклу добавляется "крюк", который начинается в <math>b_{ip}</math>, обходит все шесть узлов подграфа <math>I_{j}</math> и возвращается в <math>c_{i,p+1}</math>. Дуга из <math>b_{ip}</math> в <math>c_{i,p+1}</math> исключается из цикла, но узлы на ее концах остаются в нем.
#Аналогично, если в цикле есть дуга из <math>c_{ip}</math> в <math>b_{i,p+1}</math> и у <math>c_{ip}</math> есть еще одна дуга в один из <math>I_{j}</math>, пока не включенных в цикл, то к циклу добавляется "крюк", проходящий через все шесть узлов <math>I_{j}</math>.
