Hamilton yolu: Revizyonlar arasındaki fark
| [kontrol edilmemiş revizyon] | [kontrol edilmemiş revizyon] |
İçerik silindi İçerik eklendi
Sayfanın düzenlenmesi gerekiyor. |
Değişiklik özeti yok |
||
1. satır:
{{düzenle|Ocak 2010}}
Bir graf’taki '''Hamilton yollarının''' bulunması '''NP-tam''' bir işlemdir.
==İspat==
[[Dosya:Hamiltonyoluproblemi1s.JPG]] doğrulanması durumunda iddia ispatlanmış olacaktır.<br />
Satır 50 ⟶ 53:
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.<br />
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>
'''İş bu nedenle''', hamilton yolu '''''normal''''' olmak zorundadır. Bu indirgeme açık olarak polinomsal zamanda işler ve ispat tamamlanmış olur.
== Kaynakça ==
{{kaynakça}}
▲Michael Sipser, 2005. "Introduction to the Theory of Computation" Course Technology Press Second Edition
[[Kategori:Karmaşıklık kuramı]]
[[Kategori:Karmaşıklık ve Diller Kuramı]]
<br />
| |||