Изменения

На рисунке 1б показана структура графа в целом. Каждый шестиугольник представляет один подграф, построенный для переменной (его структура показана на рисунке 1а). Шестиугольники расположены циклически, и из нижнего узла каждого подграфа дуга ведет в верхний узел следующего.

Допустим, граф на рисунке 1б имеет ориентированный гамильтонов цикл. Не ограничивая общности, можно считать, что этот цикл начинается в <math>a_1</math>. Если затем он переходит в <math>b_{10},</math>, то на следующем шаге он обязательно перейдет в <math>c_{10}</math> (иначе <math>c_{10}</math> не появится в цикле). В самом деле, если цикл переходит из <math>a_{1}</math> в <math>b_{10}</math>, а затем - в <math>c_{11}</math>, то <math>c_{10}</math> никогда не появится в цикле, поскольку оба его предшественника (<math>a_{0}</math> и <math>b_{10}</math>) уже содержатся в нем.

<math>a_1, c_{10}, b_{10}, c_{11}, b_{11}, ..., d_1</math>.

Решающим пунктом в доказательстве является то, что порядок, при котором спуск совершается от <math>c</math> к <math>b</math>, можно трактовать как приписывание переменной, соответствующей данному подграфу, значения "истина", а порядок, при котором спуск совершается от <math>b</math> к <math>c</math>, соответствует приписыванию этой переменной значения "ложь".

В дальнейшем это позволит нам считать, что выбор перехода из <math>a_{i}</math> в <math>b_{i0}</math> означает приписывание переменной <math>x_{i}</math> значения "истина", а перехода в <math>c_{i0}</math> - значения "ложь". Поэтому граф на рисунке 1б имеет <math>2^n</math> ориентированных гамильтоновых циклов, соответствующих <math>2^n</math> возможным подстановкам для <math>n</math> переменных.

Однако на рисунке 1б изображен лишь скелет графа, порождаемого по формуле <math>E</math>, находящейся в 3-КНФ. Каждому дизъюнкту <math>e_{i}</math> ставится в соответствие подграф <math>I_{j}</math> (рисунок 1в). Он обладает тем свойством, что если цикл входит в <math>r_{j}</math>, то должен выходить из <math>u_{j}</math>. Аналогично для <math>s, v</math> и <math>t, w</math> (доказательство этого утверждения см. в книге "Введение в теорию автоматов, языков и вычислений", Дж. Хопкрофт, Р. Мотвани, Дж. Ульман).