NP-полнота задачи о гамильтоновом пути в графе — различия между версиями
(→Доказательство NP-полноты задачи об гамильтоновом пути в графе (UHAMP)) |
|||
Строка 9: | Строка 9: | ||
'''Ориентированным гамильтоновым циклом''' называется то же самое для ориентированного графа (должна существовать дуга из <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 & e_2 & ... & e_k</math>, где каждое <math>e_i</math> - дизъюнкт, представляющий собой сумму трех литералов, скажем, <math>e_i = (a_i1 + a_i2 + a_i3)</math>. | ||
+ | |||
==Формулировка задачи о гамильтоновом пути в графе== | ==Формулировка задачи о гамильтоновом пути в графе== |
Версия 14:32, 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КНФ. Пусть формула имеет вид
, где каждое - дизъюнкт, представляющий собой сумму трех литералов, скажем, .
Формулировка задачи о гамильтоновом пути в графе
В задаче об (ориентированном) гамильтоновом пути в графе ([U]HAMP) в качестве входных данных выступает (ориентированный) граф
. Требуется выяснить, есть ли в заданном (ориентированном) графе (ориентированный) гамильтонов путь.Доказательство NP-полноты задачи об ориентированном гамильтоновом пути в графе (HAMP)
Для доказательства того, что HAMP NPC, необходимо доказать два факта:
Доказательство принадлежности к NP
В качестве сертификата возьмем ориентированный гамильтонов путь в графе
. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.Доказательство принадлежности к NPH
Сведем задачу об ориентированном гамильтоновом цикле (HAM) к HAMP. Пусть дан граф
. Выберем произвольную вершину графа и раздвоим ее, и входящие дуги направим в одну из полученных вершин, а исходящие пустим из другой. Теперь, если в исходном графе был ориентированный гамильтонов цикл, то в полученном будет ориентированный гамильтонов путь. В обратную сторону, если в полученном графе будет ориентированный гамильтонов путь, то на первом и последнем местах в этом пути окажутся новые вершины, соответствующие раздвоенной, поскольку ни одна из них не может оказаться в середине пути (у неё есть либо входящие, либо исходящие дуги). Таким образом, если в полученном графе будет гамильтонов путь, то в исходном графе был гамильтонов цикл.Доказательство NP-полноты задачи о гамильтоновом пути в графе (UHAMP)
Для доказательства того, что UHAMP NPC, необходимо доказать два факта:
Доказательство принадлежности к NP
В качестве сертификата возьмем гамильтонов путь в графе
. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.Доказательство принадлежности к NPH
Сведем задачу о гамильтоновом цикле (HAMP) к UHAMP. Пусть дан ориентированный граф
. Построим по нему неориентированный граф . Для этого каждую вершине из графа поставим в соответствие 3 вершины в графе , соединив в ребром первую получившуюся со второй, а вторую - с третьей. Для каждого дуги, инцидентной исходной вершине в поставим в соответствие ребро в . В случае, если дуга исходит из этой вершины, то соединим ребро с последней из получившихся вершин в , а если она входит в вершину, то соединим с первой из получившихся. Таким образом, в построенном графе гамильтонов путь будет тогда и только тогда, когда в исходном графе будет ориентированный гамильтонов путь.