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 |
||
3. satır:
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 />
[[Dosya:Hamiltonyoluproblemi1s.JPG]] doğrulanması durumunda iddia ispatlanmış olacaktır.<br />
==İspat==
Her 3cnf formülü [[Dosya:Hamiltonyoluproblemi2s.JPG]] için, s ve t düğümleri ile yönlü graf G’nin nasıl oluşturulacağı gösterilecektir.<br />
Satır 62 ⟶ 64:
[[Kategori:Karmaşıklık kuramı]]
[[Kategori:Karmaşıklık ve Diller Kuramı]]
[[en:Hamiltonian path problem]]
<br />
| |||