Изменения
Нет описания правки
==Формулировка задачи о гамильтоновом пути в графе==
В '''задаче об (ориентированном) гамильтоновом пути в графе''' ([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===
