Изменения
Нет описания правки
Причина в том, что если цикл переходит из <math>a_{i}</math> в <math>b_{i0}</math>, то экскурсия в <math>I_{j}</math> может быть совершена только тогда, когда <math>j</math>-й дизъюнкт содержит <math>x_i</math> в качестве одного из литералов. Если цикл переходит из <math>a_i</math> в <math>c_{i0}</math>, то экскурсия в <math>I_{j}</math> может быть совершена только тогда, когда <math>\bar{x_i}</math> является литералом в <math>j</math>-ом дизъюнкте. Таким образом, из того, что все подграфы <math>I_j</math> могут быть включены в граф, следует, что при данной подстановке хотя бы один из литералов в каждом дизъюнкте истинен, т.е. формула <math>E</math> выполнима.
==Доказательство NP-полноты задачи о гамильтоновом цикле в графе (UHAM)==
Для доказательства того, что UHAM <math>\in</math> [[NPC]], необходимо доказать два факта:
*UHAM <math>\in</math> [[NP]]
*UHAM <math>\in</math> [[NPH]]
===Доказательство принадлежности к NP===
В качестве сертификата возьмем гамильтонов цикл в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.
===Доказательство принадлежности к NPH===
Сведем задачу о гамильтоновом цикле (HAM) к UHAM. Пусть дан ориентированный граф <math>G</math>. Построим по нему неориентированный граф <math>H</math>. Для этого каждой вершине из графа <math>G</math> поставим в соответствие 3 вершины в графе <math>H</math>, соединив в <math>H</math> ребром первую получившуюся со второй, а вторую - с третьей. Для каждой дуги, инцидентной исходной вершине в <math>G</math> поставим в соответствие ребро в <math>H</math>. В случае, если дуга исходит из этой вершины, то соединим ребро с последней из получившихся вершин в <math>H</math>, а если она входит в вершину, то соединим с первой из получившихся. Таким образом, в построенном графе <math>H</math> гамильтонов путь будет тогда и только тогда, когда в исходном графе <math>G</math> будет ориентированный гамильтонов путь.
==Формулировка задачи о гамильтоновом пути в графе==
В качестве сертификата возьмем гамильтонов путь в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.
===Доказательство принадлежности к NPH===
Сведем задачу о гамильтоновом цикле (HAMP) к UHAMP. Пусть дан ориентированный граф <math>G</math>. Построим по нему неориентированный граф <math>H</math>. Для этого каждую каждой вершине из графа <math>G</math> поставим в соответствие 3 вершины в графе <math>H</math>, соединив в <math>H</math> ребром первую получившуюся со второй, а вторую - с третьей. Для каждого каждой дуги, инцидентной исходной вершине в <math>G</math> поставим в соответствие ребро в <math>H</math>. В случае, если дуга исходит из этой вершины, то соединим ребро с последней из получившихся вершин в <math>H</math>, а если она входит в вершину, то соединим с первой из получившихся. Таким образом, в построенном графе <math>H</math> гамильтонов путь будет тогда и только тогда, когда в исходном графе <math>G</math> будет ориентированный гамильтонов путь.
