Изменения

Перейти к: навигация, поиск

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

4124 байта добавлено, 13:52, 13 марта 2010
Новая страница: «==Определения== ===Определение 1=== '''Гамильтоновым путем''' в графе <math>G</math> называется упоряд…»
==Определения==
===Определение 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]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> был гамильтонов цикл.
Анонимный участник

Навигация