20
правок
Изменения
м
→Задача о гамильтоновом пути в графе
==Задача о гамильтоновом цикле в графе==
{{Определение
|definition = '''<math>\mathrm{[U]HAM}</math>''' {{---}} задача нахождения (ориентированного) язык графов, содержащих [неориентированный] [[Гамильтоновы графы#Основные определения|гамильтонова циклагамильтонов цикл]] в заданном графе.
}}
===Доказательство NP-полноты для неориентированного ориентированного графа===
Для доказательства того, что <math>\mathrm{HAM}</math> <math>\in</math> [[NPC|<math>\mathrm{NPC}</math>]], необходимо доказать два факта:
*<math>\mathrm{HAM}</math> <math>\in</math> [[NP|<math>\mathrm{NP}</math>]]
Сведем задачу о выполнимости булевых формул вида [[3CNFSAT | <math>\mathrm{3CNF}</math>]] к <math>\mathrm{HAM}</math>. Начнем построение экземпляра <math>\mathrm{HAM}</math> по булевой формуле в [[3CNFSAT | <math>\mathrm{3CNF}</math>]]. Пусть формула имеет вид <math>E = e_1 \land e_2 \land \ldots \land e_k</math>, где каждое <math>e_i</math> {{---}} дизъюнкт, представляющий собой сумму трех литералов, скажем, <math>e_i = (\alpha_{i1} \vee \alpha_{i2} \vee \alpha_{i3})</math>. Пусть <math>x_1, x_2, \ldots, x_n</math> {{---}} переменные в формуле <math>E</math>. Для всех дизъюнктов и переменных строятся подграфы, как показано на рисунках.
Для каждой переменной <math>x_i</math> строится подграф <math>H_i</math> высотой <math>m_i + 2</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>.
На рисунке 2 показана структура графа в целом. Каждый пятиугольник представляет один подграф, построенный для переменной (его структура показана на рисунке 1. пятиугольники расположены циклически, и из нижнего узла каждого подграфа дуга ведет в верхний узел следующего.
В дальнейшем это позволит нам считать, что выбор перехода из <math>a_{i}</math> в <math>b_{i0}</math> означает приписывание переменной <math>x_{i}</math> значения "истина", а перехода в <math>c_{i0}</math> {{---}} значения "ложь". Поэтому граф на рисунке 2 имеет <math>2^n</math> ориентированных гамильтоновых циклов, соответствующих <math>2^n</math> возможным подстановкам для <math>n</math> переменных.
Однако на рисунке 2 изображен лишь скелет графа, порождаемого по формуле <math>E</math>, находящейся в <math>\mathrm{3-КНФ3CNF}</math>. Каждому дизъюнкту <math>e_{i}</math> ставится в соответствие подграф <math>I_{j}</math> (рисунок 3). Он обладает тем свойством, что если цикл входит в <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>G</math> имеет ориентированный гамильтонов цикл, и покажем, что формула <math>E</math> выполнима. Напомним два важных пункта из предыдущего анализа.
# Если гамильтонов цикл входит в некоторый <math>I_j</math> в узле <math>r_{j}</math>, <math>s_{j}</math> или <math>t_{j}</math>, то он должен выходить из него в узле <math>u_{j}</math>, <math>v_{j}</math> или <math>w_{j}</math> соответственно.
# Таким образом, рассматривая данный гамильтонов цикл как обход подграфов типа <math>H</math>, можно характеризовать "экскурсию", совершаемую в некоторое <math>I_j</math>, как переход цикла по дуге, "параллельной" одной из дуг <math>b_{ip} \rightarrow с_c_{i,p+1}</math> или <math>c_{ip} \rightarrow b_{i,p+1}</math>.
Если игнорировать экскурсии в подграфы <math>I_{j}</math>, то гамильтонов цикл должен быть одним из <math>2^n</math> циклов, которые возможны с использованием только подграфов <math>H_i</math> и соответствуют выборам переходов из <math>a_{i}</math> либо в <math>b_{i0}</math>, либо в <math>c_{i0}</math>. Каждый из этих выборов соответствует приписыванию значений переменным из <math>E</math>. Если один из них дает гамильтонов цикл, включающий подграфы <math>I_j</math>, то подстановка, соответствующая этому выбору, должна удовлетворять формуле <math>E</math>.
Причина в том, что если цикл переходит из <math>a_{i}</math> в <math>b_{i0}</math>, то экскурсия в <math>I_{j}</math> может быть совершена только тогда, когда <math>j</math>-й дизъюнкт содержит <math>x_i</math> в качестве одного из литералов. Если цикл переходит из <math>a_i</math> в <math>c_{i0}</math>, то экскурсия в <math>I_{j}</math> может быть совершена только тогда, когда <math>\bar{x_i}</math> является литералом в <math>j</math>-ом дизъюнкте. Таким образом, из того, что все подграфы <math>I_j</math> могут быть включены в граф, следует, что при данной подстановке хотя бы один из литералов в каждом дизъюнкте истинен, т.е. формула <math>E</math> выполнима.
===Доказательство NP-полноты для ориентированного неориентированного графа===
Для доказательства того, что <math>\mathrm{UHAM}</math> <math>\in</math> [[NPC|<math>\mathrm{NPC}</math>]], необходимо доказать два факта:
*<math>\mathrm{UHAM}</math> <math>\in</math> [[NP|<math>\mathrm{NP}</math>]]
==Задача о гамильтоновом пути в графе==
{{Определение
|definition = '''<math>\mathrm{[U]HAMP}</math>''' {{---}} задача нахождения (ориентированного) язык графов, содержащих [неориентированный] [[Гамильтоновы графы#Основные определения|гамильтонова путигамильтонов путь]] в заданном графе.
}}
В качестве сертификата возьмем ориентированный гамильтонов путь в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.
====Доказательство принадлежности к NPH====
Сведем задачу об ориентированном гамильтоновом цикле (<math>\mathrm{HAM}</math>) к <math>\mathrm{HAMP}</math>. Пусть дан граф <math>G</math>. Выберем произвольную вершину графа <math>G</math> и раздвоим ее, и входящие дуги направим в одну из полученных вершин, а исходящие пустим из другой. Теперь, если в исходном графе был ориентированный гамильтонов цикл, то в полученном будет ориентированный гамильтонов путь. В обратную сторону, если в полученном графе будет ориентированный гамильтонов путь, то на первом и последнем местах в этом пути окажутся новые вершины, соответствующие раздвоенной, поскольку ни одна из них не может оказаться в середине пути (у неё есть либо входящие, либо исходящие дуги). Таким образом, если в полученном графе будет гамильтонов путь, то в исходном графе <math>G</math> был гамильтонов цикл.
===Доказательство NP-полноты для неориентированного графа===
* [[3CNFSAT]]
* [[Примеры NP-полных языков]]
* [[Гамильтоновы графы#Задача о коммивояжере | Задача о коммивояжере]]
==Источники информации==
* Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. "Структуры данных и алгоритмы" {{---}} Издательский дом «Вильямс», 2000. {{---}} С. 384. {{---}} ISBN 5-8459-0122-7 (рус.) / ISBN 0-201-00023-7 (англ.)
* Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. 2-е издание. {{---}} М.: Издательский дом "Вильямс", 2002. {{---}} 528 с. {{---}} ISBN 5-8459-0261-4 (рус.)z
[[Категория: Теория сложности]]
[[Категория: Детерминированные и недетерминированные вычисления, сложность по времени и по памяти]]
[[Категория: Примеры NP-полных языков]]
