NP-полнота задач о гамильтоновом цикле и пути в графах — различия между версиями
Артем (обсуждение | вклад) (→Доказательство принадлежности к NPH) |
AKhimulya (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | + | {{Определение | |
| − | = | + | |definition = '''(Ориентированным) гамильтоновым путем''' в (ориентированном) графе <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>. |
| − | ''' | + | }} |
| − | '''Ориентированным гамильтоновым | + | {{Определение |
| + | |definition = '''(Ориентированным) гамильтоновым циклом''' в (ориентированном) графе <math>G</math> называется гамильтонов путь <math>n_{1}</math>, <math>n_{2}</math>, ..., <math>n_{k}</math> такой, что существует ребро из <math>n_{k}</math> в <math>n_{1}</math>. | ||
| + | }} | ||
| − | == | + | ==Задача о гамильтоновом цикле в графе== |
| − | + | {{Определение | |
| − | + | |definition = '''[U]HAM''' - задача нахождения (ориентированного) гамильтонова цикла в заданном графе. | |
| − | + | }} | |
| − | + | ===Доказательство NP-полноты для неориентированного графа=== | |
| − | + | Для доказательства того, что HAM <math>\in</math> [[NPC]], необходимо доказать два факта: | |
| − | |||
| − | |||
| − | ==Доказательство NP-полноты | ||
| − | Для доказательства того, что | ||
*HAM <math>\in</math> [[NP]] | *HAM <math>\in</math> [[NP]] | ||
*HAM <math>\in</math> [[NPH]] | *HAM <math>\in</math> [[NPH]] | ||
| − | ===Доказательство принадлежности к NP=== | + | ====Доказательство принадлежности к NP==== |
В качестве сертификата возьмем ориентированный гамильтонов цикл в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время. | В качестве сертификата возьмем ориентированный гамильтонов цикл в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время. | ||
| − | ===Доказательство принадлежности к NPH=== | + | ====Доказательство принадлежности к NPH<ref>Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. "Структуры данных и алгоритмы" {{---}} Издательский дом «Вильямс», 2000. {{---}} С. 384. {{---}} ISBN 5-8459-0122-7 (рус.) / ISBN 0-201-00023-7 (англ.)</ref>==== |
| − | + | [[Файл:HAM_fig1.png|200px|thumb|right|Рисунок 1]] [[Файл:HAM_fig2.png|200px|thumb|right|Рисунок 2]] [[Файл:HAM_fig3.png|200px|thumb|right|Рисунок 3]] [[Файл:HAM_fig4.png|200px|thumb|right|Рисунок 4]] | |
| − | Сведем задачу о выполнимости булевых формул вида 3-КНФ | + | Сведем задачу о выполнимости булевых формул вида [[3CNFSAT | 3-КНФ]] к 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>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>. |
| − | На рисунке | + | На рисунке 2 показана структура графа в целом. Каждый пятиугольник представляет один подграф, построенный для переменной (его структура показана на рисунке 1. пятиугольники расположены циклически, и из нижнего узла каждого подграфа дуга ведет в верхний узел следующего. |
| − | + | Допустим, граф на рисунке 2 имеет ориентированный гамильтонов цикл. Не ограничивая общности, можно считать, что этот цикл начинается в <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}</math>, <math>b_{10}</math>, то далее он должен спускаться "лесенкой", переходя из стороны в сторону: | ||
| Строка 45: | Строка 41: | ||
Закончив обход подграфа <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>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>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>, находящейся в 3-КНФ. Каждому дизъюнкту <math>e_{i}</math> ставится в соответствие подграф <math>I_{j}</math> (рисунок 3). Он обладает тем свойством, что если цикл входит в <math>r_{j}</math>, то должен выходить из <math>u_{j}</math><ref>Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. 2-е издание. {{---}} М.: Издательский дом "Вильямс", 2002. {{---}} 528 с. {{---}} ISBN 5-8459-0261-4 (рус.)</ref>. Аналогично для <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</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> | ||
| Строка 54: | Строка 50: | ||
Мы утверждаем, что построенный таким образом граф <math>G</math> имеет ориентированный гамильтонов цикл тогда и только тогда, когда формула <math>E</math> выполнима. | Мы утверждаем, что построенный таким образом граф <math>G</math> имеет ориентированный гамильтонов цикл тогда и только тогда, когда формула <math>E</math> выполнима. | ||
| − | ====Доказательство достаточности==== | + | =====Доказательство достаточности===== |
Предположим, существует подстановка <math>T</math>, удовлетворяющая формуле <math>E</math>. Построим ориентированный гамильтонов цикл следующим образом. | Предположим, существует подстановка <math>T</math>, удовлетворяющая формуле <math>E</math>. Построим ориентированный гамильтонов цикл следующим образом. | ||
| − | # Вначале выберем путь, обходящий только подграфы <math>H</math> (т.е. граф, изображенный на рисунке | + | # Вначале выберем путь, обходящий только подграфы <math>H</math> (т.е. граф, изображенный на рисунке 2 в соответствии с подстановкой <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>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>c_{ip}</math> в <math>b_{i,p+1}</math> и у <math>c_{ip}</math> есть еще одна дуга в один из <math>I_{j}</math>, пока не включенных в цикл, то к циклу добавляется "крюк", проходящий через все шесть узлов <math>I_{j}</math>. | ||
| Строка 62: | Строка 58: | ||
Тот факт, что <math>T</math> удовлетворяет формуле <math>E</math>, гарантирует, что исходный путь, построенный на шаге 1, будет содержать, по крайней мере, одну дугу, которая на шаге 2 или 3 позволит включить в цикл подграф <math>I_j</math> для каждого дизъюнкта <math>e_i</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> выполнима. Напомним два важных пункта из предыдущего анализа. | Предположим, что граф <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>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> соответственно. | ||
| Строка 71: | Строка 67: | ||
Причина в том, что если цикл переходит из <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> выполнима. | Причина в том, что если цикл переходит из <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-полноты | + | ===Доказательство NP-полноты для ориентированного графа=== |
Для доказательства того, что UHAM <math>\in</math> [[NPC]], необходимо доказать два факта: | Для доказательства того, что UHAM <math>\in</math> [[NPC]], необходимо доказать два факта: | ||
*UHAM <math>\in</math> [[NP]] | *UHAM <math>\in</math> [[NP]] | ||
*UHAM <math>\in</math> [[NPH]] | *UHAM <math>\in</math> [[NPH]] | ||
| − | ===Доказательство принадлежности к NP=== | + | ====Доказательство принадлежности к NP==== |
В качестве сертификата возьмем гамильтонов цикл в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время. | В качестве сертификата возьмем гамильтонов цикл в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время. | ||
| − | ===Доказательство принадлежности к NPH=== | + | ====Доказательство принадлежности к 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>, а если она входит в вершину, то соединим с первой из получившихся (см. рисунок | + | Сведем задачу о гамильтоновом цикле (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>, а если она входит в вершину, то соединим с первой из получившихся (см. рисунок 4). Таким образом, в построенном графе <math>H</math> гамильтонов путь будет тогда и только тогда, когда в исходном графе <math>G</math> будет ориентированный гамильтонов путь. |
| − | == | + | ==Задача о гамильтоновом пути в графе== |
| − | + | {{Определение | |
| + | |definition = '''[U]HAMP''' - задача нахождения (ориентированного) гамильтонова пути в заданном графе. | ||
| + | }} | ||
| − | ==Доказательство NP-полноты | + | ===Доказательство NP-полноты для ориентированного графа=== |
Для доказательства того, что HAMP <math>\in</math> [[NPC]], необходимо доказать два факта: | Для доказательства того, что HAMP <math>\in</math> [[NPC]], необходимо доказать два факта: | ||
*HAMP <math>\in</math> [[NP]] | *HAMP <math>\in</math> [[NP]] | ||
*HAMP <math>\in</math> [[NPH]] | *HAMP <math>\in</math> [[NPH]] | ||
| − | ===Доказательство принадлежности к NP=== | + | ====Доказательство принадлежности к NP==== |
В качестве сертификата возьмем ориентированный гамильтонов путь в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время. | В качестве сертификата возьмем ориентированный гамильтонов путь в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время. | ||
| − | ===Доказательство принадлежности к NPH=== | + | ====Доказательство принадлежности к NPH==== |
Сведем задачу об ориентированном гамильтоновом цикле (HAM) к HAMP. Пусть дан граф <math>G</math>. Выберем произвольную вершину графа <math>G</math> и раздвоим ее, и входящие дуги направим в одну из полученных вершин, а исходящие пустим из другой. Теперь, если в исходном графе был ориентированный гамильтонов цикл, то в полученном будет ориентированный гамильтонов путь. В обратную сторону, если в полученном графе будет ориентированный гамильтонов путь, то на первом и последнем местах в этом пути окажутся новые вершины, соответствующие раздвоенной, поскольку ни одна из них не может оказаться в середине пути (у неё есть либо входящие, либо исходящие дуги). Таким образом, если в полученном графе будет гамильтонов путь, то в исходном графе <math>G</math> был гамильтонов цикл. | Сведем задачу об ориентированном гамильтоновом цикле (HAM) к HAMP. Пусть дан граф <math>G</math>. Выберем произвольную вершину графа <math>G</math> и раздвоим ее, и входящие дуги направим в одну из полученных вершин, а исходящие пустим из другой. Теперь, если в исходном графе был ориентированный гамильтонов цикл, то в полученном будет ориентированный гамильтонов путь. В обратную сторону, если в полученном графе будет ориентированный гамильтонов путь, то на первом и последнем местах в этом пути окажутся новые вершины, соответствующие раздвоенной, поскольку ни одна из них не может оказаться в середине пути (у неё есть либо входящие, либо исходящие дуги). Таким образом, если в полученном графе будет гамильтонов путь, то в исходном графе <math>G</math> был гамильтонов цикл. | ||
| − | ==Доказательство NP-полноты | + | ===Доказательство NP-полноты для неориентированного графа=== |
Для доказательства того, что UHAMP <math>\in</math> [[NPC]], необходимо доказать два факта: | Для доказательства того, что UHAMP <math>\in</math> [[NPC]], необходимо доказать два факта: | ||
*UHAMP <math>\in</math> [[NP]] | *UHAMP <math>\in</math> [[NP]] | ||
*UHAMP <math>\in</math> [[NPH]] | *UHAMP <math>\in</math> [[NPH]] | ||
| − | ===Доказательство принадлежности к NP=== | + | ====Доказательство принадлежности к NP==== |
В качестве сертификата возьмем гамильтонов путь в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время. | В качестве сертификата возьмем гамильтонов путь в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время. | ||
| − | ===Доказательство принадлежности к NPH=== | + | ====Доказательство принадлежности к 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> будет ориентированный гамильтонов путь. | Сведем задачу о гамильтоновом цикле (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> будет ориентированный гамильтонов путь. | ||
| − | == | + | ==См. также== |
| + | * [[Классы NP и Σ₁]] | ||
| + | * [[3CNFSAT]] | ||
| + | |||
| + | ==Источники информации== | ||
<references/> | <references/> | ||
Версия 18:05, 13 марта 2016
| Определение: |
| (Ориентированным) гамильтоновым путем в (ориентированном) графе называется упорядочение всех узлов , , ..., , при котором для каждого существует ребро из в . |
| Определение: |
| (Ориентированным) гамильтоновым циклом в (ориентированном) графе называется гамильтонов путь , , ..., такой, что существует ребро из в . |
Содержание
Задача о гамильтоновом цикле в графе
| Определение: |
| [U]HAM - задача нахождения (ориентированного) гамильтонова цикла в заданном графе. |
Доказательство NP-полноты для неориентированного графа
Для доказательства того, что HAM NPC, необходимо доказать два факта:
Доказательство принадлежности к NP
В качестве сертификата возьмем ориентированный гамильтонов цикл в графе . Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.
Доказательство принадлежности к NPH[1]
Сведем задачу о выполнимости булевых формул вида 3-КНФ к HAM. Начнем построение экземпляра HAM по булевой формуле в 3КНФ. Пусть формула имеет вид , где каждое - дизъюнкт, представляющий собой сумму трех литералов, скажем, . Пусть - переменные в формуле . Для всех дизъюнктов и переменных строятся подграфы, как показано на рисунках.
Для каждой переменной строится подграф , структура которого показана на рисунке 1. Здесь - большее из чисел вхождений и в . Узлы и , расположенные в двух столбцах, соединены между собой дугами в обоих направлениях. Кроме того, каждое имеет дугу, ведущую в , расположенное на ступеньку ниже, т.е., если , то имеет дугу, ведущую в . Аналогично для . Наконец, есть верхний узел , из которого дуги ведут в и , и нижний узел , в который ведут дуги из и .
На рисунке 2 показана структура графа в целом. Каждый пятиугольник представляет один подграф, построенный для переменной (его структура показана на рисунке 1. пятиугольники расположены циклически, и из нижнего узла каждого подграфа дуга ведет в верхний узел следующего.
Допустим, граф на рисунке 2 имеет ориентированный гамильтонов цикл. Не ограничивая общности, можно считать, что этот цикл начинается в . Если затем он переходит в , то на следующем шаге он обязательно перейдет в (иначе не появится в цикле). В самом деле, если цикл переходит из в , а затем - в , то никогда не появится в цикле, поскольку оба его предшественника ( и ) уже содержатся в нем.
Таким образом, если начало цикла имеет вид , , то далее он должен спускаться "лесенкой", переходя из стороны в сторону:
.
Если начало цикла имеет вид , , то в лесенке меняется порядок предшествования и .
.
Решающим пунктом в доказательстве является то, что порядок, при котором спуск совершается от к , можно трактовать как приписывание переменной, соответствующей данному подграфу, значения "истина", а порядок, при котором спуск совершается от к , соответствует приписыванию этой переменной значения "ложь".
Закончив обход подграфа , цикл должен перейти в , где снова возникает выбор следующего перехода - в или в . Однако в силу тех же аргументов, которые приведены для , после того, как сделан выбор направления вправо или влево от , путь обхода уже зафиксирован. Вообще, при входе в каждый , есть выбор перехода влево или вправо, но никакого другого. Иначе некоторый узел обречен быть недоступным, т.е. он не сможет появиться в ориентированном гамильтоновом цикле, поскольку все его предшественники появились в нем ранее.
В дальнейшем это позволит нам считать, что выбор перехода из в означает приписывание переменной значения "истина", а перехода в - значения "ложь". Поэтому граф на рисунке 2 имеет ориентированных гамильтоновых циклов, соответствующих возможным подстановкам для переменных.
Однако на рисунке 2 изображен лишь скелет графа, порождаемого по формуле , находящейся в 3-КНФ. Каждому дизъюнкту ставится в соответствие подграф (рисунок 3). Он обладает тем свойством, что если цикл входит в , то должен выходить из [2]. Аналогично для и . В завершение построения графа для формулы соединяем подграфы и следующим образом. Допустим, у дизъюнкта первым литералом является , переменная без отрицания. Выберем некоторый узел , где от 0 до - 1, ранее не использованный для соединения с подграфами . Введем дуги, ведущие из в и из в . Если же первым литералом дизъюнкта является отрицание , то нужно отыскать неиспользованный узел , а затем соединить с и с
Для второго и третьего литералов граф дополняется точно так же, за одним исключением. Для второго литерала и используются узлы и , а для третьего - и . Таким образом, каждый имеет три соединения с подграфами типа , которые представляют переменные, присутствующие в дизъюнкте . Если литерал не содержит отрицания, то соединение выходит из -узла и входит в -узел, расположенный ниже, а если содержит - то наоборот.
Мы утверждаем, что построенный таким образом граф имеет ориентированный гамильтонов цикл тогда и только тогда, когда формула выполнима.
Доказательство достаточности
Предположим, существует подстановка , удовлетворяющая формуле . Построим ориентированный гамильтонов цикл следующим образом.
- Вначале выберем путь, обходящий только подграфы (т.е. граф, изображенный на рисунке 2 в соответствии с подстановкой . Таким образом, если , то цикл переходит из в , а если , то он переходит из в .
- Однако цикл, построенный к данному моменту, может содержать дугу из в , причем у есть еще одна дуга в один из подграфов в , который пока не включен в цикл. Тогда к циклу добавляется "крюк", который начинается в , обходит все шесть узлов подграфа и возвращается в . Дуга из в исключается из цикла, но узлы на ее концах остаются в нем.
- Аналогично, если в цикле есть дуга из в и у есть еще одна дуга в один из , пока не включенных в цикл, то к циклу добавляется "крюк", проходящий через все шесть узлов .
Тот факт, что удовлетворяет формуле , гарантирует, что исходный путь, построенный на шаге 1, будет содержать, по крайней мере, одну дугу, которая на шаге 2 или 3 позволит включить в цикл подграф для каждого дизъюнкта . Таким образом, цикл включает в себя все подграфы и является ориентированным гамильтоновым.
Доказательство необходимости
Предположим, что граф имеет ориентированный гамильтонов цикл, и покажем, что формула выполнима. Напомним два важных пункта из предыдущего анализа.
- Если гамильтонов цикл входит в некоторый в узле , или , то он должен выходить из него в узле , или соответственно.
- Таким образом, рассматривая данный гамильтонов цикл как обход подграфов типа , можно характеризовать "экскурсию", совершаемую в некоторое , как переход цикла по дуге, "параллельной" одной из дуг или .
Если игнорировать экскурсии в подграфы , то гамильтонов цикл должен быть одним из циклов, которые возможны с использованием только подграфов и соответствуют выборам переходов из либо в , либо в . Каждый из этих выборов соответствует приписыванию значений переменным из . Если один из них дает гамильтонов цикл, включающий подграфы , то подстановка, соответствующая этому выбору, должна удовлетворять формуле .
Причина в том, что если цикл переходит из в , то экскурсия в может быть совершена только тогда, когда -й дизъюнкт содержит в качестве одного из литералов. Если цикл переходит из в , то экскурсия в может быть совершена только тогда, когда является литералом в -ом дизъюнкте. Таким образом, из того, что все подграфы могут быть включены в граф, следует, что при данной подстановке хотя бы один из литералов в каждом дизъюнкте истинен, т.е. формула выполнима.
Доказательство NP-полноты для ориентированного графа
Для доказательства того, что UHAM NPC, необходимо доказать два факта:
Доказательство принадлежности к NP
В качестве сертификата возьмем гамильтонов цикл в графе . Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.
Доказательство принадлежности к NPH
Сведем задачу о гамильтоновом цикле (HAM) к UHAM. Пусть дан ориентированный граф . Построим по нему неориентированный граф . Для этого каждой вершине из графа поставим в соответствие 3 вершины в графе , соединив в ребром первую получившуюся со второй, а вторую - с третьей. Для каждой дуги, инцидентной исходной вершине в поставим в соответствие ребро в . В случае, если дуга исходит из этой вершины, то соединим ребро с последней из получившихся вершин в , а если она входит в вершину, то соединим с первой из получившихся (см. рисунок 4). Таким образом, в построенном графе гамильтонов путь будет тогда и только тогда, когда в исходном графе будет ориентированный гамильтонов путь.
Задача о гамильтоновом пути в графе
| Определение: |
| [U]HAMP - задача нахождения (ориентированного) гамильтонова пути в заданном графе. |
Доказательство NP-полноты для ориентированного графа
Для доказательства того, что HAMP NPC, необходимо доказать два факта:
Доказательство принадлежности к NP
В качестве сертификата возьмем ориентированный гамильтонов путь в графе . Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.
Доказательство принадлежности к NPH
Сведем задачу об ориентированном гамильтоновом цикле (HAM) к HAMP. Пусть дан граф . Выберем произвольную вершину графа и раздвоим ее, и входящие дуги направим в одну из полученных вершин, а исходящие пустим из другой. Теперь, если в исходном графе был ориентированный гамильтонов цикл, то в полученном будет ориентированный гамильтонов путь. В обратную сторону, если в полученном графе будет ориентированный гамильтонов путь, то на первом и последнем местах в этом пути окажутся новые вершины, соответствующие раздвоенной, поскольку ни одна из них не может оказаться в середине пути (у неё есть либо входящие, либо исходящие дуги). Таким образом, если в полученном графе будет гамильтонов путь, то в исходном графе был гамильтонов цикл.
Доказательство NP-полноты для неориентированного графа
Для доказательства того, что UHAMP NPC, необходимо доказать два факта:
Доказательство принадлежности к NP
В качестве сертификата возьмем гамильтонов путь в графе . Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.
Доказательство принадлежности к NPH
Сведем задачу о гамильтоновом цикле (HAMP) к UHAMP. Пусть дан ориентированный граф . Построим по нему неориентированный граф . Для этого каждой вершине из графа поставим в соответствие 3 вершины в графе , соединив в ребром первую получившуюся со второй, а вторую - с третьей. Для каждой дуги, инцидентной исходной вершине в поставим в соответствие ребро в . В случае, если дуга исходит из этой вершины, то соединим ребро с последней из получившихся вершин в , а если она входит в вершину, то соединим с первой из получившихся. Таким образом, в построенном графе гамильтонов путь будет тогда и только тогда, когда в исходном графе будет ориентированный гамильтонов путь.
См. также
Источники информации
- ↑ Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. "Структуры данных и алгоритмы" — Издательский дом «Вильямс», 2000. — С. 384. — ISBN 5-8459-0122-7 (рус.) / ISBN 0-201-00023-7 (англ.)
- ↑ Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. 2-е издание. — М.: Издательский дом "Вильямс", 2002. — 528 с. — ISBN 5-8459-0261-4 (рус.)
