NP-полнота задач о гамильтоновом цикле и пути в графах — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство принадлежности к NPH)
(Доказательство принадлежности к NPH)
Строка 21: Строка 21:
 
===Доказательство принадлежности к NPH===
 
===Доказательство принадлежности к NPH===
  
Доказательство взято из книги <ref>[Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. "Структуры данных и алгоритмы" — Издательский дом «Вильямс», 2000. — С. 384. — ISBN 5-8459-0122-7 (рус.) / ISBN 0-201-00023-7 (англ.)]</ref>.
+
Доказательство и иллюстрации взяты из книги <ref>[Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. "Структуры данных и алгоритмы" — Издательский дом «Вильямс», 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>. Для всех дизъюнктов и переменных строятся подграфы, как показано на рисунках.
 
Сведем задачу о выполнимости булевых формул вида 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>. Для всех дизъюнктов и переменных строятся подграфы, как показано на рисунках.

Версия 16:36, 26 марта 2010

Содержание

Определения

Определение 1

Гамильтоновым путем в графе [math]G[/math] называется упорядочение всех узлов [math]n_{1}[/math], [math]n_{2}[/math], ..., [math]n_{k}[/math], при котором для каждого [math]i = 1, 2, ..., k - 1[/math] существует ребро из [math]n_{i}[/math] в [math]n_{i+1}[/math].

Ориентированным гамильтоновым путем называется то же самое для ориентированного графа (должна существовать дуга из [math]n_{i}[/math] в [math]n_{i+1}[/math]).

Определение 2

Гамильтоновым циклом в графе [math]G[/math] называется упорядочение всех узлов [math]n_{1}[/math], [math]n_{2}[/math], ..., [math]n_{k}[/math], при котором для каждого [math]i = 1, 2, ..., k - 1[/math] существует ребро из [math]n_{i}[/math] в [math]n_{i+1}[/math], а также существует ребро из [math]n_{k}[/math] в [math]n_{1}[/math].

Ориентированным гамильтоновым циклом называется то же самое для ориентированного графа (должна существовать дуга из [math]n_{i}[/math] в [math]n_{i+1}[/math] и дуга из [math]n_{k}[/math] в [math]n_{1}[/math]).

Формулировка задачи о гамильтоновом цикле в графе

В задаче об (ориентированном) гамильтоновом цикле в графе ([U]HAM) в качестве входных данных выступает (ориентированный) граф [math]G[/math]. Требуется выяснить, есть ли в заданном (ориентированном) графе [math]G[/math] (ориентированный) гамильтонов цикл.

Доказательство NP-полноты задачи об ориентированном гамильтоновом цикле в графе (HAM)

Для доказательства того, что HAMP [math]\in[/math] NPC, необходимо доказать два факта:

  • HAM [math]\in[/math] NP
  • HAM [math]\in[/math] NPH

Доказательство принадлежности к NP

В качестве сертификата возьмем ориентированный гамильтонов цикл в графе [math]G[/math]. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.

Доказательство принадлежности к NPH

Доказательство и иллюстрации взяты из книги [1].

Сведем задачу о выполнимости булевых формул вида 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]. Для всех дизъюнктов и переменных строятся подграфы, как показано на рисунках.

Для каждой переменной [math]x_i[/math] строится подграф [math]H_i[/math], структура которого показана на рисунке а). Здесь [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 \lt 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].

На рисунке б) показана структура графа в целом. Каждый шестиугольник представляет один подграф, построенный для переменной (его структура показана на рисунке а). Шестиугольники расположены циклически, и из нижнего узла каждого подграфа дуга ведет в верхний узел следующего.

Picture aho graph1.png Picture aho graph2.png Picture aho graph3.png Picture gam cycle1.gif

Допустим, граф на рисунке б) имеет ориентированный гамильтонов цикл. Не ограничивая общности, можно считать, что этот цикл начинается в [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]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] - значения "ложь". Поэтому граф на рисунке б) имеет [math]2^n[/math] ориентированных гамильтоновых циклов, соответствующих [math]2^n[/math] возможным подстановкам для [math]n[/math] переменных.

Однако на рисунке б) изображен лишь скелет графа, порождаемого по формуле [math]E[/math], находящейся в 3-КНФ. Каждому дизъюнкту [math]e_{i}[/math] ставится в соответствие подграф [math]I_{j}[/math] (рисунок в). Он обладает тем свойством, что если цикл входит в [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]. Построим ориентированный гамильтонов цикл следующим образом.

  1. Вначале выберем путь, обходящий только подграфы [math]H[/math] (т.е. граф, изображенный на рисунке б) в соответствии с подстановкой [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].
  2. Однако цикл, построенный к данному моменту, может содержать дугу из [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] исключается из цикла, но узлы на ее концах остаются в нем.
  3. Аналогично, если в цикле есть дуга из [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] и является ориентированным гамильтоновым.

Доказательство необходимости

Предположим, что граф [math]G[/math] имеет ориентированный гамильтонов цикл, и покажем, что формула [math]E[/math] выполнима. Напомним два важных пункта из предыдущего анализа.

  1. Если гамильтонов цикл входит в некоторый [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] соответственно.
  2. Таким образом, рассматривая данный гамильтонов цикл как обход подграфов типа [math]H[/math], можно характеризовать "экскурсию", совершаемую в некоторое [math]I_j[/math], как переход цикла по дуге, "параллельной" одной из дуг [math]b_{ip} \rightarrow с_{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-полноты задачи о гамильтоновом цикле в графе (UHAM)

Для доказательства того, что UHAM [math]\in[/math] NPC, необходимо доказать два факта:

  • UHAM [math]\in[/math] NP
  • UHAM [math]\in[/math] NPH

Доказательство принадлежности к NP

В качестве сертификата возьмем гамильтонов цикл в графе [math]G[/math]. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.

Доказательство принадлежности к NPH

Сведем задачу о гамильтоновом цикле (HAM) к UHAM. Пусть дан ориентированный граф [math]G[/math]. Построим по нему неориентированный граф [math]H[/math]. Для этого каждой вершине из графа [math]G[/math] поставим в соответствие 3 вершины в графе [math]H[/math], соединив в [math]H[/math] ребром первую получившуюся со второй, а вторую - с третьей. Для каждой дуги, инцидентной исходной вершине в [math]G[/math] поставим в соответствие ребро в [math]H[/math]. В случае, если дуга исходит из этой вершины, то соединим ребро с последней из получившихся вершин в [math]H[/math], а если она входит в вершину, то соединим с первой из получившихся. Таким образом, в построенном графе [math]H[/math] гамильтонов путь будет тогда и только тогда, когда в исходном графе [math]G[/math] будет ориентированный гамильтонов путь.

Формулировка задачи о гамильтоновом пути в графе

В задаче об (ориентированном) гамильтоновом пути в графе ([U]HAMP) в качестве входных данных выступает (ориентированный) граф [math]G[/math]. Требуется выяснить, есть ли в заданном (ориентированном) графе [math]G[/math] (ориентированный) гамильтонов путь.

Доказательство NP-полноты задачи об ориентированном гамильтоновом пути в графе (HAMP)

Для доказательства того, что HAMP [math]\in[/math] NPC, необходимо доказать два факта:

  • HAMP [math]\in[/math] NP
  • HAMP [math]\in[/math] NPH

Доказательство принадлежности к NP

В качестве сертификата возьмем ориентированный гамильтонов путь в графе [math]G[/math]. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.

Доказательство принадлежности к NPH

Сведем задачу об ориентированном гамильтоновом цикле (HAM) к HAMP. Пусть дан граф [math]G[/math]. Выберем произвольную вершину графа [math]G[/math] и раздвоим ее, и входящие дуги направим в одну из полученных вершин, а исходящие пустим из другой. Теперь, если в исходном графе был ориентированный гамильтонов цикл, то в полученном будет ориентированный гамильтонов путь. В обратную сторону, если в полученном графе будет ориентированный гамильтонов путь, то на первом и последнем местах в этом пути окажутся новые вершины, соответствующие раздвоенной, поскольку ни одна из них не может оказаться в середине пути (у неё есть либо входящие, либо исходящие дуги). Таким образом, если в полученном графе будет гамильтонов путь, то в исходном графе [math]G[/math] был гамильтонов цикл.

Доказательство NP-полноты задачи о гамильтоновом пути в графе (UHAMP)

Для доказательства того, что UHAMP [math]\in[/math] NPC, необходимо доказать два факта:

  • UHAMP [math]\in[/math] NP
  • UHAMP [math]\in[/math] NPH

Доказательство принадлежности к NP

В качестве сертификата возьмем гамильтонов путь в графе [math]G[/math]. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.

Доказательство принадлежности к NPH

Сведем задачу о гамильтоновом цикле (HAMP) к UHAMP. Пусть дан ориентированный граф [math]G[/math]. Построим по нему неориентированный граф [math]H[/math]. Для этого каждой вершине из графа [math]G[/math] поставим в соответствие 3 вершины в графе [math]H[/math], соединив в [math]H[/math] ребром первую получившуюся со второй, а вторую - с третьей. Для каждой дуги, инцидентной исходной вершине в [math]G[/math] поставим в соответствие ребро в [math]H[/math]. В случае, если дуга исходит из этой вершины, то соединим ребро с последней из получившихся вершин в [math]H[/math], а если она входит в вершину, то соединим с первой из получившихся. Таким образом, в построенном графе [math]H[/math] гамильтонов путь будет тогда и только тогда, когда в исходном графе [math]G[/math] будет ориентированный гамильтонов путь.

Ссылки

  1. [Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. "Структуры данных и алгоритмы" — Издательский дом «Вильямс», 2000. — С. 384. — ISBN 5-8459-0122-7 (рус.) / ISBN 0-201-00023-7 (англ.)]