Изменения
Нет описания правки
'''Ориентированным гамильтоновым циклом''' называется то же самое для ориентированного графа (должна существовать дуга из <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>.
==Формулировка задачи о гамильтоновом пути в графе==
