Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde, şekil kuramında (graph theory) kullanılan en kısa kesim (minimum cut) problemine yönelik bir iyileştirme (optimization) ağacıdır.
Algoritmanın amacı, bir ağaç (tree) oluşturmak ve oluşturulan ağaçta, bir şekildeki (graph) kesme ihtimallerini hesaplamaktır.
Algoritmanın çalışmasını bir örnek üzerinden anlamaya çalışalım. Öncelikle en kısa kesimi bulacağımız şeklimiz (graph) aşağıdaki şekilde verilmiş olsun:
Yukarıda, yönsüz ve ağırlıklı bir şekil görülmektedir (undirected, weighted graph). Amacımız bu şekli düz bir şekilde kestiğimizde en az maliyetli kesiği bulmaktır. Konuyu anlamak için bir kesim örneği ele alalım:
Yukarıdaki kesim sırasında, A-B, A-D, E-D, F-D bağları kesilmiştir. Bu bağların toplam maliyeti 5+7+5+7 = 24 değerindedir.
İşte bizim amacımız farklı şekillerde yapılabilecek kesme eylemlerinden en az maliyete sahip olanını bulmaktır.
Algoritmamız ilk olarak bütün düğümlerin toparlandığı bir büyük düğüm ile başlıyor.
Şekilde görüldüğü üzere, bütün düğümleri içerisine alan tek bir düğümümüz bulunuyor. Şimdi rast gele seçilen iki düğüm arasındaki en küçük kesimi buluyoruz.
Bu aşamada rast gele olarak B ve E düğümlerini aldığımızı düşünelim.
Bu iki düğüm arasındaki en düğük maliyetli kesme aşağıda verilmiştir.
Yukarıdaki şekilde, görüldüğü üzere, A-B, B-D ve D-C kenarları kesilmiş ve bunun karşılığında 12 maliyetinde bir kesim elde edilmiştir. Algoritmamız, bu kesim işlemini düğümlerin tutulduğu grup üzerinde de uygular.
Aslında bu aşamada algoritma artık anlaşılmaktadır. Algoritmamız bu şekilde rast gele düğümler seçerek her grupta tek düğüm kalana kadar şekli parçalamaya devam edecek ve sonra en kısa maliyetli kenarı alacaktır.
Bu işlemi örnek üzerinde görmeye devam edelim.
Algoritmamızın şimdiki aşamasında, gruplardan birisini ve sonrada bu gruptaki düğümlerden iki tanesini seçeceğiz.
Örneğin B ve C düğümlerini seçtiğimizi düşünelim. (Bu aşamada farklı gruplardan iki düğüm seçemiyoruz. Örneğin B ve A düğümleri seçilemezdi. Ancak diğer gruptan iki düğüm seçebilirdik. Örneğin A ve D düğümleri olabilirdi).
B ve C düğümleri arasında tek bir kesme mümkündür ve bu da aşağıdaki şekilde işaretlenmiştir:
Yukarıdaki şekilde görüldüğü üzere, B-C ve C-D kenarları kesilmiş ve maliyet olarak 9 maliyetinde bir kesim elde edilmiştir. Bu durum algoritmamızın çalışmasını tutan resmin sağ tarafında gösterilmiştir. Yani bir önceki adımda beraber duran B ve C düğümleri ayrılmış ve iki ayrı düğüm olarak gomory-hu ağacında gösterilmiştir.
Bir sonraki adımda yine iki rast gele düğüm seçiyoruz. Bu sefer düğümlerimiz E ve F olsun.
Yeni halimizde E düğümü de tek başına ağacımızda yerini almıştır (resmin sağ tarafı).
Rast gele düğüm seçimine devam ediyoruz ve bu sefer D ve F düğümlerini seçelim.
D ve F düğümleri arasında, iki farklı kesim alınabilirdi. En düğük maliyetli olan alternatif yukarıda zaten gösterilmiştir, ayrıca E-D ve F-D kesimi de alınabilirdi, ancak daha önce de belirttiğimiz üzere, en düşük maliyetli olanını alıyoruz.
Gelelim son ayrıma, A-D kesimi aşağıdaki şekilde yapılmıştır:
Bu son kesimle birlikte, ağacımızı tamamlamış oluyoruz ve algoritmamız çalışmasını bitiriyor. Buna göre yukarıdaki ağaçta iki tane minimum kesim (minimum cut) olabilir. Bunlardan birincisi B-C arasındaki 9 maliyetindeki kesim, ikincisi ise A-E arasındaki 9 maliyetindeki kesim.
en son aşamada A-D ayırırken neden 12 oldu anlayamadım?A-D arasındaki kenar 7 değil mi?D yi bütün tepelerden ayıracaksak 4+3+7+5+7 olur tabi böyle bir kesimde mümkün değil fakat 12 nasıl oldu?
Kesim işlemi sırasında, düğümü, diğer bütün düğümlerden ayıran en düşük maliyet alınır. Yani A-D arasındaki mesafe 7 ancak A ve D düğümlerinin ayrılması için A düğümünü şekilden koparırsanız, A-B + A-D maliyeti olan 5+ 7 = 12 alırsınız.
Yazıyı en başından itibaren okursanız bu durum bütün kesmeler için kullanılmıştır. Örneğin ilk kesme olan BC ve diğer düğümler durumunda alınan maliyetler A-B, B-D , ve C-D uzunluklarının toplam maliyetidir. Ardından B ile C arasındaki kesmede B-C ve C-D maliyetlerinin toplamı alınmıştır ve algoritmanın geri kalanında da (ve sizin sorduğunuz son adımda da) aynı yaklaşım izlenmiştir.
Başarılar