Bir grafın tüm düğümlerini bir kere geçen yola “Hamilton Yolu(Hamiltonian Path)” denir. Bir grafın herhangi bir düğümünden başlayarak tüm düğümleri sadece bir kere geçerek başlangıç düğümüne gelebiliyosa buna Hamilton Devresi(Hamiltonian Circuit) denir. Burada dikkat edilmesi gereken nokta tüm düğümlere uğranacak fakat tüm ayrıtları geçmek zorunda değil.

Hamilton yolu, seyyar satıcı problemi ve sıfır bilgi ispatı (Zero-Knowledge proof) gibi bilgisayar bilimlerinin problemlerin çözümünde kullanılmaktadır.

Teorem:n>=3 olmak üzere n düğümlü basit bir G grafında tüm düğümlerin dereceleri en az n/2 ise G grafında hamilton devre vardır.

image-center