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

Определения

Определение 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

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

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

В задаче об (ориентированном) гамильтоновом пути в графе ([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] будет ориентированный гамильтонов путь.