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:

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.

« İstatistiksel Dilbilim (Probabilistic Linguistic) | Markof Modeli (Markov Model) »

Yorumlar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Hamilton Yolu (Hamiltonian Path,hamiltonian circuit)' isimli yazı 17 Jun 2009 tarihinde, saat: 11:08 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 598 defa okunmuştur.

Benzer yazıları Automata (otomatlar, özdevinirler), algoritma analizi (teory of algorithms), veri yapıları kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar