Hamilton yolu: Revizyonlar arasındaki fark
| [kontrol edilmemiş revizyon] | [kontrol edilmemiş revizyon] |
İçerik silindi İçerik eklendi
Şablon yardımcısı kullanılarak {{Çift_madde}} etiketi ekleniyor |
Değişiklik özeti yok |
||
1. satır:
{{Çift_madde|Yönsüz Hamilton Yolu Problemi}}
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. 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<ref> M. R. Garey, D. S. Johnson. [http://portal.acm.org/citation.cfm?id=803884 Some simplified NP-complete problems]. ''Proceedings of the sixth annual ACM symposium on Theory of computing'', p. 47-63. 1974.</ref>.
==İddia==
Bir graf’taki '''Hamilton yollarının''' bulunması '''NP-tam''' bir işlemdir.<br />
==
'''Hampath'''’in NP bir problem olduğu zaten bilinmektedir.<ref>Michael Sipser: "Introduction to the Theory of Computation" Course Technology Press Second Edition, 2005.</ref><br /><br />
Satır 60 ⟶ 64:
'''İş bu nedenle''', hamilton yolu '''''normal''''' olmak zorundadır. Bu indirgeme açık olarak polinomsal zamanda işler ve ispat tamamlanmış olur.<br />
==Ayrıca Bakınız==
*[[Seyyar_satıcı_problemi]]
== Kaynakça ==
| |||