Изменения
→Доказательство принадлежности к NPH
Тот факт, что <math>T</math> удовлетворяет формуле <math>E</math>, гарантирует, что исходный путь, построенный на шаге 1, будет содержать, по крайней мере, одну дугу, которая на шаге 2 или 3 позволит включить в цикл подграф <math>I_j</math> для каждого дизъюнкта <math>e_i</math>. Таким образом, цикл включает в себя все подграфы <math>I_j</math> и является ориентированным гамильтоновым.
====Доказательство необходимости====
Предположим, что граф <math>G</math> имеет ориентированный гамильтонов цикл, и покажем, что формула <math>E</math> выполнима. Напомним два важных пункта из предыдущего анализа.
# Если гамильтонов цикл входит в некоторый <math>I_j</math> в узле <math>r_{j}</math>, <math>s_{j}</math> или <math>t_{j}</math>, то он должен выходить из него в узле <math>u_{j}</math>, <math>v_{j}</math> или <math>w_{j}</math> соответственно.
# Таким образом, рассматривая данный гамильтонов цикл как обход подграфов типа <math>H</math>, можно характеризовать "экскурсию", совершаемую в некоторое <math>I_j</math>, как переход цикла по дуге, "параллельной" одной из дуг <math>b_{ip} \rightarrow с_{i,p+1}</math> или <math>c_{ip} \rightarrow b_{i,p+1}</math>.
Если игнорировать экскурсии в подграфы <math>I_{j}</math>, то гамильтонов цикл должен быть одним из <math>2^n</math> циклов, которые возможны с использованием только подграфов <math>H_i</math> и соответствуют выборам переходов из <math>a_{i}</math> либо в <math>b_{i0}</math>, либо в <math>c_{i0}</math>. Каждый из этих выборов соответствует приписыванию значений переменным из <math>E</math>. Если один из них дает гамильтонов цикл, включающий подграфы <math>I_j</math>, то подстановка, соответствующая этому выбору, должна удовлетворять формуле <math>E</math>.
Причина в том, что если цикл переходит из <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> выполнима.
==Формулировка задачи о гамильтоновом пути в графе==
