Hamilton Yolu, yönlü veya yönsüz bir grafikte Hamilton yolu veya Hamilton devresinin olup olmadığının kararının verilmesinin problemidir. Yönlü ve yönsüz Hamilton devresi problemi Karp’ın 21 NP-tam probleminden ikisidir . Garey ve Johnson, 1974 senesinde düzlemsel grafikler için yönlü hamilton devresi probleminin ve kübik düzlemsel grafikler için yönsüz hamilton devresi probleminin değişmeden NP-tam kalacağını kısaca göstermişlerdir . Hamilton yolları, yaygın olarak Gezgin satıcı problemi'nin çözümü için kullanılmaktadır. İddia Bir graf’taki Hamilton yollarının bulunması NP-tam bir işlemdir. Çözüm fikri Hampath’in NP bir problem olduğu zaten bilinmektedir. 3SAT HAMPATH indirgemesinin doğrulanması durumunda iddia ispatlanmış olacaktır. İspat Her 3cnf formülü için, s ve t düğümleri ile yönlü graf G’nin nasıl oluşturulacağı gösterilecektir. Eğer şartları sağlıyorsa, s ve t arasında bir hamilton yolu bulunmaktadır. k adet clause’dan oluşan 3cnf formülü : Dosya:Hamiltonyoluproblemi3s.JPG Denklemde yer alan her p, q, r ; x veya x’ olmak üzere ’nın l adet değişken içerdiği varsayılacak olursa denklemde yer alan değişkenler : x ... x ’nın graf G’ye dönüştürülmesi işleminde; graf G, ’nın içerisindeki değişkenler ve clause’lardan oluşacaktır. Her değişken x, 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:Hamiltonyoluproblemi4s.JPG Değişken x’nin elmas içerisinde tasvir edilmesi Dosya:Hamiltonyoluproblemi5s.JPG ’daki her clase’un tek bir düğüm ile tasvir edilmesi Aşağıdaki figür, G’nin global yapısını göstermektedir. İllüstrasyon, değişkenlerin clause’lar ile olan ilişkileri haricinde G’nin tüm elemanları ve ilişkilerini göstermektedir. Dosya:Hamiltonyoluproblemi6s.JPG 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ı şekilde de görüldüğü gibi: Dosya:Hamiltonyoluproblemi7s.JPG Elmas yapısında yer alan yatay düğümler Eğer değişken x, clause c içerisinde yer alıyorsa; i. değişkendeki j. çift ile j. clause ilişki içerisindedir. Dosya:Hamiltonyoluproblemi8s.JPG Clause c nin x yi içermesi durumundaki ilave kenarlar Eğer x’, clause c içerisinde yer alıyorsa; i. değişkendeki j. çift ile j. clause ilişki içerisindedir.Dosya:Hamiltonyoluproblemi9s.JPGClause cj nin xi‘ yi içermesi durumundaki ilave kenarlar Her clause’da her x veya x’ nin var oluşuna göre eklenecek kenarlar ile, G’nin yapısı tamamlanmış olacaktır. Yol s’den başlayacak, her elmasa sırasıyla uğrayacak t’de son bulacaktır. Elmasta izlenecek yolun bulunması için, ’yı sağlayan değerlerden belirlenmek üzere yol ya soldan sağa doğru zig-zag yapacak ya da sağdan sola doğru zag-zig yapacaktır. Şayet x DOĞRU olarak belirlenmişse yol elmas boyunca zig-zag yapacak, YANLIŞ olarak belirlenmişse yol elmas boyunca zag-zig yapacaktır. Her iki ihtimalde takip eden figürde gösterilmiştir. Dosya:Hamiltonyoluproblemi10s.JPGElmas boyunca zig-zag veya zag-zig yapılması denklemde şartları sağlayan değerler tarafından belirlenmektedir. Böylelikle arzu edilen Hamilton yolu oluşturulmuş olur. Geriye gösterilmesi kalan tek şey Hamilton yolunun normal olmak zorunda olduğudur. Normallik sadece bir yol clause’a bir elmastan girip, clause çıkışında farklı bir elmasa gidiyorsa başarısız olacaktır. Tıpkı illüstrasyonda betimlendiği gibi
osya:Hamiltonyoluproblemi11s.JPGBu Durum Gerçekleşemez 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 durumda da, 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. İş bu nedenle, hamilton yolu normal olmak zorundadır. Bu indirgeme açık olarak polinomsal zamanda işler ve ispat tamamlanmış olur. Ayrıca bakınız Gezgin satıcı problemi Sıfır bilgi ispatı Kaynakça Kategori:Karmaşıklık teorisi
osya:Hamiltonyoluproblemi11s.JPGBu Durum Gerçekleşemez 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 durumda da, 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. İş bu nedenle, hamilton yolu normal olmak zorundadır. Bu indirgeme açık olarak polinomsal zamanda işler ve ispat tamamlanmış olur. Ayrıca bakınız Gezgin satıcı problemi Sıfır bilgi ispatı Kaynakça Kategori:Karmaşıklık teorisi