Hamilton ve Euler Turu

Konu graf teorisi olunca graflar üzerindeki yol hesaplamaları da kaçınılmaz oluyor. Bugün de sizler ile literatürde çok sık karşılaşılan Hamilton ve Euler turları hakkında bilgi edinelim.

Hamilton Turu

Hamilton Yolu (Hamiltonian Path), yönlü veya yönsüz bir grafikte Hamilton yolu veya Hamilton devresinin olup olmadığının kararının verilmesinin problemidir. Hamilton grafı söz konusu olduğunda bir graftaki tüm tepeler yalnız bir kez geçilerek tur tamamlanmalıdır. Eğer bu yol kapalı olarak tamamlanırsa Hamilton Grafı olarak adlandırılır.

HamiltonianPlatonicCycles

NP-Complete problemlerden biri olan Hamilton yolunda, tüm kenarlar kapatılabilir veya kapatılmayabilir. Ancak kenarlar kesinlikle tekrarlanmamalıdır.

Daha önce sizler için belirttiğim orijinal grafı hatırlarsanız bu bölümde de o grafımız ile yolumuza devam edelim. Ne dersiniz? Çünkü verilen graf için arama algoritmalarını harekete geçirerek inceleme şansımız olmuştu. Bu sebeptendir ki aynı graf ile devam etmek istemekteyim.

Haydi, birlikte bir örnek yapalım!

Şekilde görüldüğü üzere var olan orijinal graf Hamilton turu açısından incelenmek istendiğinde tüm tepelerin yalnızca bir kez geçileceği varsayılarak yol tamamlanmalıdır. Hamilton turları hesaplanırken tüm ihtimaller kombinasyonu göz önünde bulundurulur. Tepeler kontrol edilirken ise komşu olması ve seçilen tepenin yol üstünde olmaması gereklidir.

Şimdi ise konuya daha iyi hakim olmak adına C kodunu birlikte oluşturalım.

Komşuluk ve Yol Kontrol Fonksiyonu C Kodu
Hamilton Rekürsif Fonksiyon C Kodu

Euler Turu

Bir yönsüz grafta şayet bütün düğümleri dolaşan bir yol bulunabiliyorsa bu yola Euler yolu( Eulerian Path, Eulerian Trail, Eulerian Walk) ismi verilir.

▪ Bir yönsüz bağlı grafın bütün düğümlerinin derecesi çift ise bu graf euler grafıdır.
▪ Bir yönsüz grafta euler yolu bulunabilmesi için iki veya sıfır sayıda tek düğüm derecesine sahip üyesi olmalıdır.

Tabiki işin biraz daha derinine inelim ve birlikte kodlamasına göz gezdirelim.

Kenar Silme Fonksiyonu Başlangıcı

Euler yolunun oluşturulduğu graf üzerinde daha görsel detaylar görmek isterseniz graphonline.ru/en linkinden deneyip işi daha eğlenceli hale getirebilirsiniz!

NOT: Euler yolu için yukarıda yazılmış olan şartlar Euler izi için geçerli olacak şekilde Fleury Algoritması temellerine dayanmaktadır.

Öncelikle Hamilton yolunun aksine bir turun Euler turu sayılabilmesi için tepelerin dereceleri tek derece ise ya 0 ya 2 adet olacaktır. Bunun kontrolü için ise daha önce oluşturulmuş olan printDegrees( ) fonksiyonu kullanılacaktır.

Grafta Yer Alan Tepelerin Derecelerinin Yazdırılması

Şekilde görüldüğü üzere bu grafın Euler turu olma ihtimali yüksektir. Bu sebeple bir kontrol daha yapılarak tepeler arasındaki kenarlar gezilmelidir. Şekil 36’ da görüldüğü gibi graftaki tüm tepeler gezilerek gezinme sırasında bulunan tepenin tek olma durumu bir değişkende tutulur. Tek olan değişkenin sayısı ya 0 (hiç) ya da 2 olmalıdır.

Tepenin Tek Derecelerinin Yazdırılması

Tepeler arasında gezinmenin sağlanabilmesi için aşağıdaki şekilde görüldüğü gibi belirli köşeden başlanarak turun yazdırılması fonksiyonu hazırlanmalıdır.

Tur Başlangıcı

Aşağıda yer verdiğim görselde ise Euler turu fonksiyonun tam hali bulunmaktadır.

Kodda gösterdiğim gibi u tepesinden başlayarak geçerli bir sonraki tepeye her seferinde yinelemeli uğramak koşulu ile tüm kenarlar gezilebilmektedir. Aşağıdaki şekilde ise tepeler arasında geçiş kontrolünü sağlayan fonksiyona yer verilmiştir.

Özetlersek, Graf teorisinde sıkça yer verilen Euler ve Hamilton yolları hakkında bilgi sahibi olmuş olduk. Bir sonraki yazımda görüşmek dileğiyle. Sağlıklı günler dilerim.

REFERANSLAR

https://mathworld.wolfram.com/HamiltonianGraph.html

https://www.gatevidyalay.com/hamiltonian-graphs-hamiltonian-path-hamiltonian-circuit/

Vikipedi, “Hamilton Yolu”, Şubat 2020, https://tr.wikipedia.org/wiki/Hamilton_yolu, Özgür Ansiklopedi.

Bilgi Sayamıyorum Beta, “Hamilton Graf nedir?”, https://bilgisayamiyorum.com/post/38/.

Bilgisayar Kavramları, Şadi Evren Şeker, “Öyler Yolu (Eulerian Path)”, Haziran 2009.

https://bilgisayarkavramlari.sadievrenseker.com/2009/06/17/oyler-yolu-eulerian-path/.

From Wikipedia, The free encyclopedia, “Euler tour technique”, February 2019, https://en.wikipedia.org/wiki/Euler_tour_technique.


Leave a Reply

Your email address will not be published. Required fields are marked *