Hamilton yolu: Revizyonlar arasındaki fark

k adet clause’dan oluşan 3cnf formülü <math>\phi</math> :

Denklemde yer alan her p, q, r ; x_i veya x_i’ olmak üzere

<math>\phi</math>’nın l adet değişken içerdiği varsayılacak olursa denklemde yer alan değişkenler : x₁ … x_l

<math>\phi</math> ’nın graf G’ye dönüştürülmesi işleminde; graf G, <math>\phi</math> ’nın içerisindeki değişkenler ve clause’lardan oluşacaktır.

Her değişken x_i, aşağıdaki illüstrasyondada olduğu gibi yatayda dizilmiş düğümlerden oluşan elmas şeklindeki bir yapı ile temsil edilecektir. Daha sonra, yatay sırada gözüken düğümlerin sayısı belirlenecektir.

[[Dosya:Hamiltonyoluproblemi6s.JPG]] <br /> Graf G’nin Global Yapısı

Ardından, değişkenleri temsil eden elemanlarla clause’ları temsil eden düğümlerin nasıl ilişki içerisinde oldukları gösterilecektir. Yatay sırada 3k+1 adet düğüm ve bunlara ilavaten iki adet başta ve sonda bulunan elmasa dahil düğüm bulunmaktadır. Bu düğümler, her clause için bitişik düğümler oluşturacak şekilde gruplanacak ve bu çiftlerden sonra ekstra ayırıcı bir düğüm bulunacaktır. Tıpkı şekildede görüldüğü gibi:

Yol a₁’den C’ye gider, ancak aynı elmastaki a₂’ye dönmesi gerekirken, farklı bir elmastaki b₂’ye döner. Eğer bu durum olursa, ya a₂ ya da a₃ ayırıcı düğüm olmak zorundadır. Şayet a₂ ayırıcı düğüm olsaydı, a₂’ye giren kenarlar yalnızca a₁ ve a₃’ten olurdu. Eğer a3 ayırıcı düğüm olsaydı,a₁ ve a₂ aynı clause çifti içerisinde yer alırdı. Bundan ötürüde a₂’ye giren kenarlar yalnızca a₁, a₃ ve c’den olabilirdi. Her iki durumdada, yol a2 düğümünü içermezdi. Yol a₂’ye c veya a₁’den giremez çünkü yol bu düğümlerden başka bir yere gitmektedir. Yol a₂’ye a₃’ten giremez çünkü a₃, a₂’nin işaret ettiği tek mevcut düğüm. Bu yüzden, yol a₂’den a₃ vasıtasıyla çıkmak zorundadır.