Kapsama Ağaçları

Bir ağ yapısındaki bağlantılardan tüm nodları bağlayan bir alt gruba "kapsama ağacı" (spanning tree) denir. Özel kural hiç bir nodun bir başka noda birden fazla yoldan bağlı olmamasıdır, yani "halka" (loop) olmamalıdır. Bu özel alt yapıya "ağaç" denmesinin nedeni de budur. Nasıl ki bir ağaç dallara ayrılır ama bu dallar (bahçıvan özel bir çaba harcamamışsa) tekrar bir araya gelmezler, bir kapsama ağacındaki bağlantılar da mutlaka belli bir merkezden dallanıyorlarmış gibi ayrılıyor gözükeceklerdir.

Bir ağ yapısındaki nodları "kapsayan", yani her noduna erişebilen birden fazla kapsama ağacı oluşturabilirsiniz. Bir ağ yapısı üzerinde mümkün olan tüm kapsama ağaçlarının sayısı kolay bir formülle verilemez. Halka oluşturmaktan kaçınmak dışında özel bir kural da yoktur, ama belli adımlar izleyecekseniz, aşağıdaki ik yöntemden birini izleyebilirsiniz.

Genişlik Öncelikli Kapsama Ağacı

Bir kapsama ağacını oluşturmanın basit bir yolu bir merkezden başlamak ve bağlantıları dallandırarak devam etmektir . Gerçek hayattan bir örnek verecek olursak, bir kaymakamın ilçeye bağlı köylerden her birine ayrı bir araçla seçim sandık heyetini ya da nüfus sayım memurlarını göndermek istediğini düşünelim.

Hangi aracı hangi güzergah üzerinden göndermeye karar vermek için yardımcılarıyla birlikte haritayı açacak ve öncelikle ilçe merkezine doğrudan bağlı köylerin bağlantılarını listeletecektir. Aşağıdaki ağ yapısında 0 nolu nod ilçe merkezini ve diğer nodlar da köyleri temsil ediyor olsun. Kaymakam ve yardımcıları ilçeye doğrudan bağlı olan 1, 2, 3, 4 ve 5 noluköylere giden yolları muhtemel güzergahlar olarak listeleyecektir:

Bu ağacın genişlik öncelikli olması demek, eriştiği her yeni noktada kabul edebileceği tüm dalları içermesi demektir. Oluşturduğunuz bu son ağaç yapısındaki merkez noddan (bu örnekte 0) diğer nodlardan herhangi birine mümkün olan en az sayıda bağlantıyla erişebilirsiniz. Kaymakamın gönderdiği araç 16 nolu köye yalnızca 1 nolu köyden geçerek gidecektir. 2 ve 8 nolu köylerden geçerek gitseydi, fazladan bir durak yapmış olurdu.

Dikkat edin, diğer her noda en kısa yoldan değil, en az sayıda bağlantıyla diyoruz. Örneğin, yukarıdaki ağaçta tek duraklı 0-3-11 yolu toplam uzunluğu 262,2 olacaktır, ama iki duraklı 0-4-12-11 yolu için toplam uzunluk 228,9 ile daha kısa olurdu.

Derinlik Öncelikli Kapsama Ağacı

Şimdi gerçek hayat örneğimizi biraz değiştirelim. Bu kez kaymakam vatandaşların öneri ve sorunlarını öğrenmek için ilçeye bağlı tüm köyleri ziyaret etmeye karar vermiş. Yardımcılarıyla birlikte bir araca atlamış, önce ilçe merkezine doğrudan bağlı köylerden birine gidecekler. Doğrudan bağlantısı olan 1, 2, 3, 4 ve 5 nolu köyler var deniyor. Bunları duydupu sırayla listeye ekletiyor, ama her duyduğu yolu muhtemel güzergahlar listesinin en başına ekletiyor. Yani muhtemel güzergahlar (aday bağlantılar) listesi bu kez bir kuyruk değil, bir yığın (stack). Son duyduğu 5 numara bu yıığın listenin başında olduğu için oraya hareket emri veriyor. 5 nolu köye varıp görüşmeleri tamamladıktan sonra da geri dönüp ilçe merkezine doğrudan bağlı bir başka köye gitmek yerine, 5 nolu köyden çıkan yolları muhtemel güzergahlar listesine ekletiyor, ama yine en son duyduğunu en başa yazdırıyor.

Ve tabi ki yeni eklediğiniz 16 nodundan dallanan bağlantıları da aday bağlantılar listesinin sonuna, yani kuyruğa eklersiniz.

Bu adımları izleyerek "genişlik öncelikli" (breadth-first) bir kapsama ağacı oluşturursunuz:

0 nodundan dallanan aday bağlantıları böylece tüketmiş olursunuz. Yani kaymakamlık görevlileri ilçe merkezine doğrudan bağlı köylere giden yolları ilk güzergahlar olarak kesinleştirdiler. Şu an sıradaki aday bağlantı 1-0 zaten ağacınızın merkezi olan 0 noduna eriştiğine göre ağaca eklenmeyecektir. Yani güzergah çıkış noktası olan ilçe merkezine gitmenin bir anlamı yoktur. Nod 5 de ağaca zaten eklenmiş olduğuna göre 1-5 bağlantısını da dikkate almaya gerekyoktur. Bununla birlikte 1-16 bağlantısı daha önceden erişilmemiş nod 16'ya erişiyor. Böylelikle, 1 nolu köy muhtarının yolu var dediği 16 nolu köy için de 0-1-16 yolu güzergah olarak kesinleştirilir:

Kesinleşen güzergahları izleyen ikincil yollar listenin sonuna eklenir, ve muhtemel güzergahlar kuyrukta (queue) bekleyen insanlar gibi sırayla dikkate alınırlar. Önemli olan her köye mümkün olan en az duraklı güzergahtan erişmektir. Örneğin, 1 nolu köy muhtarı 5 nolu köye giden yolu da bildirmiştir, ama 5 numaraya zaten doğrudan erişen bir yol olduğuna göre, önce o güzergah dikkate alınır.

Her neyse, ilçe merkezi 0'dan 2, 3, 4 ve 5 nolu köylere giden yollar da kesinleşmiş güzergahlar olarak kapsama ağacına eklenirler. Her kesinleşen güzergah için de gidilecek köyün muhtarından o köylerden çıkan yollar öğrenilir ve muhtemel güzergahlar (aday bağlantılar) kuyruğuna eklenir:

Bu muhtemel güzergahları "Aday Bağlantılar" listesinde görüyorsunuz. İlk muhtemel güzergahın eriştiği 1 nolu köye erişen başka güzergah olmadığına göre, o bağlantı araç gönderilecek ilk güzergah olarak seçilecektir. Tabi ki ilçe merkezine doğrudan bağlı olmayan başka köyler için de güzergah belirlemek gerekir. 1 nolu köy muhtarına telefon açan kaymakamlık görevlileri 1 nolu köyden çıkan yolları da muhtemel güzergahlar (buradaki aday bağlantılar) listesine ekleyeceklerdir, ama sona ekleyeceklerdir.

Bu arada şunu da belirtelim: Bu adımları kendi çizdiğiniz bir ağ yapısı üzerinde elle uyguluyor olsaydınız, nodları etiket sayı veya harf sırasına göre dikkate alırdınız. Bizim kullandığımız örnek program bağlantıların orijinal oluşturma sırasını izliyor, daha doğrusu bir yığınla uğraştığımıza göre, sırayı tersten izliyor, ama anlayın artık. Programın belirlediği sıraya göre, 5 nolu köyün muhtarı 0, 6, 7, 15 ve 1 nolu köylere giden yolları saymış. Kaymakamlık heyeti de son duydukları 1 nolu köye henüz gitmedikleri için oraya doğru hareket etmişler.

aaa, neyse artık. Biz çoktan sırayı şaşırdık. Bunu kendiniz elle deneyin. Aday sırasını kendi belirleyeceğiniz bir kurala göre yapabilirsiniz ya da kural da izlemek zorunda değilsiniz, ama aday bağlantıları bir yığına ekleyip ters sırayla dikkate alırsanız, buradakinden farklı da olsa bir derinlik öncelikli (depth-first) kapsama ağacı oluşturmuş olursunuz.

Bu tür bir kapsama ağacında merkez noddan diğer nodlara mümkün olan en az dallanmayla erişilir.

Bu adımları izleyerek oluşturduğunuz kapsama ağacı "derinlik öncelikli" (depth-first) diye bilinir, çünkü eklediği dallarla mümkün olduğu kadar derinlere erişir. Kaymakamlık heyeti 16 nolu köyden sonra 8 nolu köy, oradan 2 nolu köy, sonra 9 nolu köy ve sonra 18 nolu köye gidecektir. 18 nolu köyden henüz gitmedikleri bir başka köye gidemeyeceklerine göre, oradan 9 noya geri dönüp, "Başka hangi köy vardı gitmediğimiz?" diye sormak zorunda kalacaklardır. 17 nolu köyü duyup oraya da uğrarlar, ama yine gerisin geri, bu kez taaa 5 nolu köye kadar dönerler. 6 nolu köye gidip yine 5'e döndükten sonra 15-7-21-19, geri 21, sonra 20-14-13-11-...

1 no muhtarı da 0, 5 ve 16 yollarını sayınca, tabi ki istikamet 16 nolu köy olmuş.

Page updated

Report abuse