NP-полнота задачи о гамильтоновом пути в графе — различия между версиями
(→Доказательство принадлежности к NPH) |
(→Доказательство принадлежности к NPH) |
||
Строка 29: | Строка 29: | ||
Таким образом, если начало цикла имеет вид <math>a_{1}</math>, <math>b_{10}</math>, то далее он должен спускаться "лесенкой", переходя из стороны в сторону: | Таким образом, если начало цикла имеет вид <math>a_{1}</math>, <math>b_{10}</math>, то далее он должен спускаться "лесенкой", переходя из стороны в сторону: | ||
+ | |||
+ | <math>a_1, b_{10}, c_{10}, b_{11}, c_{11}, ..., d_1</math>. | ||
+ | |||
+ | Если начало цикла имеет вид <math>a_{1}</math>, <math>c_{10}</math>, то в лесенке меняется порядок предшествования <math>c</math> и <math>b</math>. | ||
+ | |||
+ | <math>a_1, c_{10}, b_{10}, c_{11}, b_{11}, ..., d_1</math>. | ||
+ | |||
+ | Решающим пунктом в доказательстве является то, что порядок, при котором спуск совершается от <math>c</math> к <math>b</math>, можно трактовать как приписывание переменной, соответствующей данному подграфу, значения "истина", а порядок, при котором спуск совершается от <math>b</math> к <math>c</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>e_{j}</math> граф дополняется точно так же, за одним исключением. Для второго литерала и используются узлы <math>s_{j}</math> и <math>v_{j}</math>, а для третьего - <math>t_{j}</math> и <math>w_{j}</math>. Таким образом, каждый <math>I_{j}</math> имеет три соединения с подграфами типа <math>H</math>, которые представляют переменные, присутствующие в дизъюнкте <math>e_{j}</math>. Если литерал не содержит отрицания, то соединение выходит из <math>c</math>-узла и входит в <math>b</math>-узел, расположенный ниже, а если содержит - то наоборот. | ||
+ | |||
+ | Мы утверждаем, что построенный таким образом граф <math>G</math> имеет ориентированный гамильтонов цикл тогда и только тогда, когда формула <math>E</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>. | ||
+ | |||
+ | Тот факт, что <math>T</math> удовлетворяет формуле <math>E</math>, гарантирует, что исходный путь, построенный на шаге 1, будет содержать, по крайней мере, одну дугу, которая на шаге 2 или 3 позволит включить в цикл подграф <math>I_j</math> для каждого дизъюнкта <math>e_i</math>. Таким образом, цикл включает в себя все подграфы <math>I_j</math> и является ориентированным гамильтоновым. | ||
==Формулировка задачи о гамильтоновом пути в графе== | ==Формулировка задачи о гамильтоновом пути в графе== |
Версия 15:57, 13 марта 2010
Содержание
- 1 Определения
- 2 Формулировка задачи о гамильтоновом цикле в графе
- 3 Доказательство NP-полноты задачи об ориентированном гамильтоновом цикле в графе (HAM)
- 4 Формулировка задачи о гамильтоновом пути в графе
- 5 Доказательство NP-полноты задачи об ориентированном гамильтоновом пути в графе (HAMP)
- 6 Доказательство NP-полноты задачи о гамильтоновом пути в графе (UHAMP)
Определения
Определение 1
Гамильтоновым путем в графе
называется упорядочение всех узлов , , ..., , при котором для каждого существует ребро из в .Ориентированным гамильтоновым путем называется то же самое для ориентированного графа (должна существовать дуга из
в ).Определение 2
Гамильтоновым циклом в графе
называется упорядочение всех узлов , , ..., , при котором для каждого существует ребро из в , а также существует ребро из в .Ориентированным гамильтоновым циклом называется то же самое для ориентированного графа (должна существовать дуга из
в и дуга из в ).Формулировка задачи о гамильтоновом цикле в графе
В задаче об (ориентированном) гамильтоновом цикле в графе ([U]HAM) в качестве входных данных выступает (ориентированный) граф
. Требуется выяснить, есть ли в заданном (ориентированном) графе (ориентированный) гамильтонов цикл.Доказательство NP-полноты задачи об ориентированном гамильтоновом цикле в графе (HAM)
Для доказательства того, что HAMP NPC, необходимо доказать два факта:
Доказательство принадлежности к NP
В качестве сертификата возьмем ориентированный гамильтонов цикл в графе
. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.Доказательство принадлежности к NPH
Сведем задачу о выполнимости булевых формул вида 3-КНФ (3CNF SAT) к HAM. Начнем построение экземпляра HAM по булевой формуле в 3КНФ. Пусть формула имеет вид
, где каждое - дизъюнкт, представляющий собой сумму трех литералов, скажем, . Пусть - переменные в формуле . Для всех дизъюнктов и переменных строятся подграфы, как показано на рисунке 1.Для каждой переменной
строится подграф , структура которого показана на рисунке 1а. Здесь - большее из чисел вхождений и в . Узлы и , расположенные в двух столбцах, соединены между собой дугами в обоих направлениях. Кроме того, каждое имеет дугу, ведущую в , расположенное на ступеньку ниже, т.е., если , то имеет дугу, ведущую в . Аналогично для . Наконец, есть верхний узел , из которого дуги ведут в и , и нижний узел , в который ведут дуги из и .На рисунке 1б показана структура графа в целом. Каждый шестиугольник представляет один подграф, построенный для переменной (его структура показана на рисунке 1а). Шестиугольники расположены циклически, и из нижнего узла каждого подграфа дуга ведет в верхний узел следующего.
Допустим, граф на рисунке 1б имеет ориентированный гамильтонов цикл. Не ограничивая общности, можно считать, что этот цикл начинается в
. Если затем он переходит в , то на следующем шаге он обязательно перейдет в (иначе не появится в цикле). В самом деле, если цикл переходит из в , а затем - в , то никогда не появится в цикле, поскольку оба его предшественника ( и ) уже содержатся в нем.Таким образом, если начало цикла имеет вид
, , то далее он должен спускаться "лесенкой", переходя из стороны в сторону:.
Если начало цикла имеет вид
, , то в лесенке меняется порядок предшествования и ..
Решающим пунктом в доказательстве является то, что порядок, при котором спуск совершается от
к , можно трактовать как приписывание переменной, соответствующей данному подграфу, значения "истина", а порядок, при котором спуск совершается от к , соответствует приписыванию этой переменной значения "ложь".Закончив обход подграфа
, цикл должен перейти в , где снова возникает выбор следующего перехода - в или в . Однако в силу тех же аргументов, которые приведены для , после того, как сделан выбор направления вправо или влево от , путь обхода уже зафиксирован. Вообще, при входе в каждый , есть выбор перехода влево или вправо, но никакого другого. Иначе некоторый узел обречен быть недоступным, т.е. он не сможет появиться в ориентированном гамильтоновом цикле, поскольку все его предшественники появились в нем ранее.В дальнейшем это позволит нам считать, что выбор перехода из
в означает приписывание переменной значения "истина", а перехода в - значения "ложь". Поэтому граф на рисунке 1б имеет ориентированных гамильтоновых циклов, соответствующих возможным подстановкам для переменных.Однако на рисунке 1б изображен лишь скелет графа, порождаемого по формуле
, находящейся в 3-КНФ. Каждому дизъюнкту ставится в соответствие подграф (рисунок 1в). Он обладает тем свойством, что если цикл входит в , то должен выходить из . Аналогично для и (доказательство этого утверждения см. в книге "Введение в теорию автоматов, языков и вычислений", Дж. Хопкрафт, Р. Мотвани, Дж. Ульман). В завершение построения графа для формулы соединяем подграфы и следующим образом. Допустим, у дизъюнкта первым литералом является , переменная без отрицания. Выберем некоторый узел , где от 0 до - 1, ранее не использованный для соединения с подграфами . Введем дуги, ведущие из в и из в . Если же первым литералом дизъюнкта является отрицание , то нужно отыскать неиспользованный узел , а затем соединить с и сДля второго и третьего литералов
граф дополняется точно так же, за одним исключением. Для второго литерала и используются узлы и , а для третьего - и . Таким образом, каждый имеет три соединения с подграфами типа , которые представляют переменные, присутствующие в дизъюнкте . Если литерал не содержит отрицания, то соединение выходит из -узла и входит в -узел, расположенный ниже, а если содержит - то наоборот.Мы утверждаем, что построенный таким образом граф
имеет ориентированный гамильтонов цикл тогда и только тогда, когда формула выполнима.Доказательство достаточности
Предположим, существует подстановка
, удовлетворяющая формуле . Построим ориентированный гамильтонов цикл следующим образом.- Вначале выберем путь, обходящий только подграфы (т.е. граф, изображенный на рисунке 1б) в соответствии с подстановкой . Таким образом, если , то цикл переходит из в , а если , то он переходит из в .
- Однако цикл, построенный к данному моменту, может содержать дугу из в , причем у есть еще одна дуга в один из подграфов в , который пока не включен в цикл. Тогда к циклу добавляется "крюк", который начинается в , обходит все шесть узлов подграфа и возвращается в . Дуга из в исключается из цикла, но узлы на ее концах остаются в нем.
- Аналогично, если в цикле есть дуга из в и у есть еще одна дуга в один из , пока не включенных в цикл, то к циклу добавляется "крюк", проходящий через все шесть узлов .
Тот факт, что
удовлетворяет формуле , гарантирует, что исходный путь, построенный на шаге 1, будет содержать, по крайней мере, одну дугу, которая на шаге 2 или 3 позволит включить в цикл подграф для каждого дизъюнкта . Таким образом, цикл включает в себя все подграфы и является ориентированным гамильтоновым.Формулировка задачи о гамильтоновом пути в графе
В задаче об (ориентированном) гамильтоновом пути в графе ([U]HAMP) в качестве входных данных выступает (ориентированный) граф
. Требуется выяснить, есть ли в заданном (ориентированном) графе (ориентированный) гамильтонов путь.Доказательство NP-полноты задачи об ориентированном гамильтоновом пути в графе (HAMP)
Для доказательства того, что HAMP NPC, необходимо доказать два факта:
Доказательство принадлежности к NP
В качестве сертификата возьмем ориентированный гамильтонов путь в графе
. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.Доказательство принадлежности к NPH
Сведем задачу об ориентированном гамильтоновом цикле (HAM) к HAMP. Пусть дан граф
. Выберем произвольную вершину графа и раздвоим ее, и входящие дуги направим в одну из полученных вершин, а исходящие пустим из другой. Теперь, если в исходном графе был ориентированный гамильтонов цикл, то в полученном будет ориентированный гамильтонов путь. В обратную сторону, если в полученном графе будет ориентированный гамильтонов путь, то на первом и последнем местах в этом пути окажутся новые вершины, соответствующие раздвоенной, поскольку ни одна из них не может оказаться в середине пути (у неё есть либо входящие, либо исходящие дуги). Таким образом, если в полученном графе будет гамильтонов путь, то в исходном графе был гамильтонов цикл.Доказательство NP-полноты задачи о гамильтоновом пути в графе (UHAMP)
Для доказательства того, что UHAMP NPC, необходимо доказать два факта:
Доказательство принадлежности к NP
В качестве сертификата возьмем гамильтонов путь в графе
. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.Доказательство принадлежности к NPH
Сведем задачу о гамильтоновом цикле (HAMP) к UHAMP. Пусть дан ориентированный граф
. Построим по нему неориентированный граф . Для этого каждую вершине из графа поставим в соответствие 3 вершины в графе , соединив в ребром первую получившуюся со второй, а вторую - с третьей. Для каждого дуги, инцидентной исходной вершине в поставим в соответствие ребро в . В случае, если дуга исходит из этой вершины, то соединим ребро с последней из получившихся вершин в , а если она входит в вершину, то соединим с первой из получившихся. Таким образом, в построенном графе гамильтонов путь будет тогда и только тогда, когда в исходном графе будет ориентированный гамильтонов путь.