NP-полнота задачи о гамильтоновом пути в графе — различия между версиями
Строка 12: | Строка 12: | ||
==Формулировка задачи о гамильтоновом пути в графе== | ==Формулировка задачи о гамильтоновом пути в графе== | ||
В '''задаче об (ориентированном) гамильтоновом пути в графе''' ([U]HAMP) в качестве входных данных выступает (ориентированный) граф <math>G</math>. Требуется выяснить, есть ли в заданном (ориентированном) графе <math>G</math> (ориентированный) гамильтонов путь. | В '''задаче об (ориентированном) гамильтоновом пути в графе''' ([U]HAMP) в качестве входных данных выступает (ориентированный) граф <math>G</math>. Требуется выяснить, есть ли в заданном (ориентированном) графе <math>G</math> (ориентированный) гамильтонов путь. | ||
− | |||
− | |||
==Доказательство NP-полноты задачи об ориентированном гамильтоновом пути в графе (HAMP)== | ==Доказательство NP-полноты задачи об ориентированном гамильтоновом пути в графе (HAMP)== | ||
Для доказательства того, что 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=== | ||
+ | В качестве сертификата возьмем ориентированный гамильтонов путь в графе <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=== | ===Доказательство принадлежности к NP=== | ||
В качестве сертификата возьмем гамильтонов путь в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время. | В качестве сертификата возьмем гамильтонов путь в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время. | ||
===Доказательство принадлежности к NPH=== | ===Доказательство принадлежности к NPH=== | ||
− |
Версия 14:07, 13 марта 2010
Содержание
Определения
Определение 1
Гамильтоновым путем в графе
называется упорядочение всех узлов , , ..., , при котором для каждого существует ребро из в .Ориентированным гамильтоновым путем называется то же самое для ориентированного графа (должна существовать дуга из
в ).Определение 2
Гамильтоновым циклом в графе
называется упорядочение всех узлов , , ..., , при котором для каждого существует ребро из в , а также существует ребро из в .Ориентированным гамильтоновым циклом называется то же самое для ориентированного графа (должна существовать дуга из
в и дуга из в ).Формулировка задачи о гамильтоновом пути в графе
В задаче об (ориентированном) гамильтоновом пути в графе ([U]HAMP) в качестве входных данных выступает (ориентированный) граф
. Требуется выяснить, есть ли в заданном (ориентированном) графе (ориентированный) гамильтонов путь.Доказательство NP-полноты задачи об ориентированном гамильтоновом пути в графе (HAMP)
Для доказательства того, что HAMP NPC, необходимо доказать два факта:
Доказательство принадлежности к NP
В качестве сертификата возьмем ориентированный гамильтонов путь в графе
. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.Доказательство принадлежности к NPH
Сведем задачу об ориентированном гамильтоновом цикле (HAM) к HAMP. Пусть дан граф
. Выберем произвольную вершину графа и раздвоим ее, и входящие дуги направим в одну из полученных вершин, а исходящие пустим из другой. Теперь, если в исходном графе был ориентированный гамильтонов цикл, то в полученном будет ориентированный гамильтонов путь. В обратную сторону, если в полученном графе будет ориентированный гамильтонов путь, то на первом и последнем местах в этом пути окажутся новые вершины, соответствующие раздвоенной, поскольку ни одна из них не может оказаться в середине пути (у неё есть либо входящие, либо исходящие дуги). Таким образом, если в полученном графе будет гамильтонов путь, то в исходном графе был гамильтонов цикл.Доказательство NP-полноты задачи об гамильтоновом пути в графе (UHAMP)
Для доказательства того, что UHAMP NPC, необходимо доказать два факта:
Доказательство принадлежности к NP
В качестве сертификата возьмем гамильтонов путь в графе
. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.