Minimum Kapsama Ağacı

Yine konuyu olabilecek en karışık şekilde anlatmak için kaymakamlık örneğini kullanalım. Bu kez kaymakamımız hepsi hala toprak ya da stabilize olan ilçe yollarına asfalt döşetmek istiyor. Ödenek kısıntıları nedeniyle, her köye asfalt bir yoldan ulaşılmasını garantilemek koşuluyla, toplam asfalt uzunluğunu en aza indirgemek zorunda. İlçenin her köyüne ulaşmış olma koşulu nedeniyle köy yolları ağı üzerinde bir kapsama ağacı oluşturması gerekiyor, ama bu kez hedef dallanmalar en aza ya da en fazla olsun değil, toplam uzunluk en az olsun.

Bir ağ yapısında her bağlantının bir "ağırlık" (weight) değeri vardır. Bu ağırlık köy yolları ağında yol uzunluğu olabilir, ama bir yolun trafik kazası riski, bir iletim hattının kayıp oranı, vb. çok çeşitli nicelikler ağ bağlantılarının ağırlıkları olarak görülebilir. Bizim sunduğumuz türden bir problem ağ yapısı üzerinde toplam ağırlığı en düşük olacak kapsama ağacını oluşturmaktır ve "minimum kapsama ağacı" (minimum spanning tree) problemi diye adlandırılır.

Prim Algoritması

Kaymakamlıkta bu problemi çözmek için tüm köy yollarını uzunluklarıyla gösteren bir harita üzerinde çalışacaklardır, ama iki farklı algoritmaya göre çalışabilirler. Önce Prim algoritmasını anlatalım. Bu algoritmanın ilk adımınında ilçe merkezinden çıkan yollar ilk muhtemel güzergahlar olarak dikkate alınacaktır, ama uzunluk sırasına göre. Uzunluk değerlerini basitleştirdiğimiz köy yolları ağında bu ilk aşamayı şöyle gösterebiliriz:

2 nolu köy yolu 3,0 km uzunluğuyla asfaltanacak muhtemel güzergahlar listesinin en balındadır. 5, 1, 4 ve 3 nolu köy yolları sonraki adaylardır.

2 nolu köye asfalt yol döşenmediğine göre, bu güzergah kesinleştirilir. Hedef toplam asfalt uzunluğunu minimum yapmak olduğuna göre, ilk erişilen 2 nolu köyden çıkan yollar da uzunluk sorasına göre muhtemel güzergahlar listesine girerler.

toplam asfalt uzunluğu en kısa olacak kapsama ağacı aşağıdaki gibi oluşturulur:

Özetle, Prim'in algoritmasında aday bağlantılar, belli bir merkezden başlayarak, ağırlık sırasına göre dikkate alınır ve daha önce erişilmemiş bir noda erişenler kesinleştirilir.

Dikkat edin, toplam asfalt uzunluğu en kısaysa da, bu asfalt ağaç ilçe merkezinden köylere en kısa yoldan erişileceği anlamına gelmiyor. Örnek olarak, 3 nolu köye doğrudan erişen 15 kmlik yol dururken, 5-15-4-12-11-3 yolu üzerinden 33,5 km asfalt döşenmiş oluyor. Peki toplam asfalt uzunluğu ne kadar? Bunu da hesaplayın ve daha sonra "En kısa yollar" (shortest paths) problemi çözdüğünüzde bu sonucu oradakilerle karşılaştırın.

Kruskal Algoritması

Uzunlukları gösteren köy yolları haritası masada açıldığında uzunluk sırasını ilçe merkezinden çıkan yollarla oluşturmak zorunluluğu yoktur. Tüm köy yolları uzunluk sırasına sokulursa, aday bağlantılar o sraya göre dikkate alınabilir. Bunu yaparken izlenen adımlar "Kruskal Algortması" dye bilinir. Yukarıdaki ağ yapısı üzerinde bu algoritmayı deneyelim ve sonuç aynı mıymış, görelim.

İlk adımda tüm köy yolları uzunluk sırasına göre muhtemel güzergahlar listesindedir. Yani tüm ağ bağlantıları ağırlık sırasıyla aday bağlantılar listesine eklenmişlerdir:

Muhtemel güzergahlar bu sıraya göre dikkate alınırlar. Bu kez kapsama ağacı tek parça şeklinde oluşmak zorunda değildir. Halka oluşturmamak kuralı yine geçerlidir, bu kural aynı ağaç parçasındaki nodlara uyglanır. Örneğin, 7-21 aday bağlantısını sırası geldiğinde farklı ağaçlara dahil olan bu iki nodu birleştirmekte sakınca yoktur:

ama 7-19 aday bağlantısının sırası geldiğinde artık aynı ağaç parçasına dahil olan bu iki nodu birleştirmemek gerekir:

Bu adımlar izlenerek oluşturulan minimum kapsama ağacı aşağıdaki gibidir:

Size ilginç gelebilir, ama bu kapsama ağacı Prim algoritmasıyla oluşturulan ağaçla aynıdır. Aynı ağırlığa sahip bağlantıların çokluğunda, kullanılan sıralama algoritmasına bağlı olarak aday bağlantılar sırası değişebilir; bu nedenle iki algoritma bazen farklı ağaç şekilleri oluştursa da toplam ağırlık aynı olacaktır.