Hamilton Yolu (Hamiltonian Path,hamiltonian circuit)

Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde veri modellemede kullanılan graf teorisinde (graph theory) kullanılan bir yol (path) biçimidir. Tanımı oldukça basittir. Buna göre bir yolun (path) Hamilton yolu olabilmesi için bir kere geçilen kenardan (edge) tekrar geçilmemesi gerekir ve ayrıca yolun bütün düğümleri (nodes) birer kere ziyaret etmesi gerekir.

Bir hamilton yolu başladığı yerde bitiyorsa yani tam bir döngü (cycle) tamamlıyorsa (yoldaki son düğümden ilk düğüme gidilmesi mümkünse) bu yollara hamilton döngüsü (hamiltonian cycle) ismi de verilebilir.

Hamiltonian yolları yönsüz graflarda (undirected graph) tanımlıdır ancak hamilton yollarının benzerleri yönlü graflar (directed graphs) için de uyarlanabilir.

Bir graftaki hamilton yollarının bulunması işlemi NP-Complete bir işlemdir.

Örnek

Örneğin aşağıdaki şekli (graph) ele alalım:

Yukarıdaki şekil için tanımımıza uygun bir yol (path) elde etmek istersek:

Yukarıdaki şekilde kırmızı olarak gösterilen yol bir hamiltonian yoludur. Ancak bu şekilde çıkarılabilecek tek yol yukarıdaki yol değildir.

Yukarıdaki bu yeni yol da tanıma uygun bir yoldur ve ilk çıkan yoldan farklıdır. Görüldüğü üzere bir şekilde tek bir hamilton yolu bulunmak zorunda değildir.

Hamilton yollarının özellikleri

Herhangi bir hamilton döngüsü (hamiltonian cycle) tek bir kenarın (edge) çıkarılmasıyla bir hamilton yoluna (hamiltonian path) dönüştürülebilir.

2 den fazla düğüme (node) sahip ve tam bağlı (strongly connected) turnuva çizimleri birer hamilton yoludur (hamiltonian path)

Tam bağlı graflar (strongly connected graphs) için birbirinden farlı hamilton yollarının (hamiltonian path) sayısı (n-1)!/2 tanedir.

Hamiltonian yollarının kullanım alanları

Seyyar satıcı problemi (travelling salesman problem) gibi pekçok graf teori problemin çözümünde kullanılabilirler.

Sıfır bilgi ispatı (zero-knowledge proof) gibi veri güvenliği (cryptography) problemlerinde kullanılabilirler.