HERAKLES Otomatik Avlı kalıcı sunucu. 19 Haziran'da açılıyor. Atius & Wizard güvencesiyle hemen kayıt ol, ön kayıt ödülleri aktif. HEMEN TIKLA!
Graf teorisinde Hamilton Yolu Problemi ve Hamilton Devresi Problemi, yönlü veya yönsüz bir grafta 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 [1]. Garey ve Johnson, 1974 senesinde düzlemsel graflar için yönlü hamilton devresi probleminin ve kübik düzlemsel graflar için yönsüz hamilton devresi probleminin değişmeden NP-tam kalacağını kısaca göstermişlerdir [2].
Hamilton yolları, yaygın olarak Seyyar satıcı problemi'nin çözümü için kullanılmaktadır.
İddia
Bir graftaki Hamilton yollarının bulunması NP-tam bir işlemdir.
Çözüm fikri
Hampathin NP bir problem olduğu zaten bilinmektedir.[3]
3SAT \leq_p HAMPATH indirgemesinin doğrulanması durumunda iddia ispatlanmış olacaktır.
İspat
Her 3cnf formülü \phi için, s ve t düğümleri ile yönlü graf Gnin nasıl oluşturulacağı gösterilecektir.
Eğer \phi şartları sağlıyorsa, s ve t arasında bir hamilton yolu bulunmaktadır.
k adet clausedan oluşan 3cnf formülü \phi :
Hamiltonyoluproblemi3s.JPG
Denklemde yer alan her p, q, r ; xi veya xi olmak üzere
\phinın l adet değişken içerdiği varsayılacak olursa denklemde yer alan değişkenler : x1 xl
\phi nın graf Gye dönüştürülmesi işleminde; graf G, \phi nın içerisindeki değişkenler ve clauselardan oluşacaktır.
Her değişken xi, 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.
Yönlü ve yönsüz hamilton devresi problemi Karpın 21 NP-tam probleminden ikisidir [1]. Garey ve Johnson, 1974 senesinde düzlemsel graflar için yönlü hamilton devresi probleminin ve kübik düzlemsel graflar için yönsüz hamilton devresi probleminin değişmeden NP-tam kalacağını kısaca göstermişlerdir [2].
Hamilton yolları, yaygın olarak Seyyar satıcı problemi'nin çözümü için kullanılmaktadır.
İddia
Bir graftaki Hamilton yollarının bulunması NP-tam bir işlemdir.
Çözüm fikri
Hampathin NP bir problem olduğu zaten bilinmektedir.[3]
3SAT \leq_p HAMPATH indirgemesinin doğrulanması durumunda iddia ispatlanmış olacaktır.
İspat
Her 3cnf formülü \phi için, s ve t düğümleri ile yönlü graf Gnin nasıl oluşturulacağı gösterilecektir.
Eğer \phi şartları sağlıyorsa, s ve t arasında bir hamilton yolu bulunmaktadır.
k adet clausedan oluşan 3cnf formülü \phi :
Hamiltonyoluproblemi3s.JPG
Denklemde yer alan her p, q, r ; xi veya xi olmak üzere
\phinın l adet değişken içerdiği varsayılacak olursa denklemde yer alan değişkenler : x1 xl
\phi nın graf Gye dönüştürülmesi işleminde; graf G, \phi nın içerisindeki değişkenler ve clauselardan oluşacaktır.
Her değişken xi, 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.
