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:

ham1

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

ham2

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.

ham3

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.

Yorumlar

  1. Duygu

    Hocam kolay gelsin öncelikle, HP den HC ye ya da HC den HP ye dönüşümü(reduction oluyor sanırım) graf üzerinde şekilsel olarak gösterebilir misiniz?Teşekkürler.

  2. Pelin

    Merhabalar,

    yurtdisinda bilgisayar bilimleri okuyorum ve Türkce kaynak arayisindayim. Indirgemelerin, problemlerin anlatildigi yani gelen olarak karmasiklik teorisiyle ilgili bir kaynak önerebilir misiniz? Belki de konu adlarini tam ceviremedigimden bir iki ders notu disinda bir sey bulamiyorum. Eger Türkce kaynak yoksa bildiginiz, iyi bir Ingilizce kaynak da isime yarayabilir.
    Üstünü cize cize, not alarak, kendi diline okuyarak ögrenmek gibisi yokmus maalesef. Cevap verirseniz cok cok mutlu olurum. Tesekkürler.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir