Hamilton yolu: Revizyonlar arasındaki fark
| [kontrol edilmemiş revizyon] | [kontrol edilmemiş revizyon] |
İçerik silindi İçerik eklendi
Değişiklik özeti yok |
Değişiklik özeti yok |
||
55. satır:
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:<br />[[Dosya:Hamiltonyoluproblemi11s.JPG]]<br />Bu Durum Gerçekleşemez<br /><br />
Yol a<sub>1</sub>’den C’ye gider, ancak aynı elmastaki a<sub>2</sub>’ye dönmesi gerekirken, farklı bir elmastaki b<sub>2</sub>’ye döner. Eğer bu durum olursa, ya a<sub>2</sub> yada a<sub>3</sub> ayırıcı düğüm olmak zorundadır. Şayet a<sub>2</sub> ayırıcı düğüm olsaydı, a<sub>2</sub>’ye giren kenarlar yalnızca a<sub>1</sub> ve a<sub>3</sub>’ten olurdu. Eğer a3 ayırıcı düğüm olsaydı,a<sub>1</sub> ve a<sub>2</sub> aynı clause çifti içerisinde yer alırdı. Bundan ötürüde a<sub>2</sub>’ye giren kenarlar yalnızca a<sub>1</sub>, a<sub>3</sub> ve c’den olabilirdi. Her iki durumdada, yol a2 düğümünü içermezdi. Yol a<sub>2</sub>’ye c veya a<sub>1</sub>’den giremez çünkü yol bu düğümlerden başka bir yere gitmektedir. Yol a<sub>2</sub>’ye a<sub>3</sub>’ten giremez çünkü a<sub>3</sub>, a<sub>2</sub>’nin işaret ettiği tek mevcut düğüm. Bu yüzden, yol a<sub>2</sub>’den a<sub>3</sub> 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.<br />
| |||