gokhanca

Minimum Kapsayan Ağaç probleminde ise tüm şebeke gezilmek istenmekte ve bu en az yol giderek yapılmak istenmektedir.

Mesela bir telefon şirketi 6 adet şehir arasında telefon hattı kurmak istemektedir. Şehirlerin şebeke yapısı aşağıdaki gibidir. Bağlantı değerleri km cinsinden uzaklığı belirtmektedir. En az kablo uzunluğu kullanarak tüm şehirleri birbirine bağlayan bağlantıyı bulalım.

Algoritma için iki adet veri kümesi kullanacağız. Bunlardan biri HEDEF kümesi, diğeri ise BAĞLANANLAR kümesi. Algoritmamız bu şekildeyken HEDEF = { 1 , 2 , 3 , 4 , 5 , 6 } ve BAĞLANANLAR = { }' dir. Algoritmamıza istediğimiz bir düğüm noktasından başlayabiliriz. Mesela 1. düğüm noktasından başlayalım.

Önce BAĞLANANLAR = { 1 } yaparız ve HEDEF dizisinden 1'i çıkarırız. HEDEF = { 2 , 3 , 4 , 5 , 6 }
1. düğüm noktasının bağlı olduğu bağlantılar arasından en küçüğünü seçeriz. 2. düğüm noktası en kısa bağlantıyı vermektedir. O halde 1 ile 2'yi bağlarız. Bundan sonraki işlem HEDEF dizisinden 2'yi çıkarmak ve BAĞLANANLAR dizisine eklemektir. BAĞLANANLAR = { 1 , 2 } ve HEDEF = { 3 , 4 , 5 , 6 }. Unutulmaması gereken şey BAĞLANANLAR kümesindeki her eleman için HEDEF kümesindeki düğümlerle uzaklıkları araştırılır. Bulunan yeni en kısa uzaklık eğer BAĞLANANLAR kümesinin iki elamanı arasında ise bu bağlantı seçilmez.

Bundan sonraki adımda BAĞLANANLAR kümesindeki elemanların yaptığı en kısa bağlantıyı buluruz. BAĞLANANLAR kümesindeki elemanlar kırmızı düğüm noktalarıdır. Dolayısıyla kırmızı düğüm noktalarına en kısa bağlantıyı 2 ile 5'in bağlantısı vermektedir. 2. adım sonunda
BAÄžLANANLAR = { 1 , 2 , 5} ve HEDEF = { 3 , 4 , 6 }.

Yine aynı mantıkla kırmızı noktaların içinde, en kısa bağlantı 2'nin 4 ile yaptığı bağlantıdır. Dolayısıyla 2 ile 4 bağlanır.
BAÄžLANANLAR = { 1 , 2 , 5 , 4 } ve HEDEF = { 3 , 6 }.

Bu adımda ise kırmızılar ile yeşiller arasındaki en kısa bağlantıyı 4 ile 6 yapmıştır. 4 ile 6 bağlanır.
BAÄžLANANLAR = { 1 , 2 , 5 , 4 , 6 } ve HEDEF = { 3 }.

Son adımda ise en kısa bağlantıyı iki farklı şekilde seçebiliriz. Çünkü hem 1-3 hemde 3-4 bağlantıları en kısadır. Herhangi birini seçebiliriz. Mesela 3-4 bağlantısını seçelim.
BAÄžLANANLAR = { 1 , 2 , 5 , 4 , 6 , 3 } ve HEDEF = { }.

HEDEF kümesinde başka düğüm noktası kalmadığına göre işlemimiz bitmiştir. Tüm düğüm noktaları, en kısa yollar kullanılarak birbirine bağlanmıştır. Bu şekilde tüm kabloların uzunluğu 1 + 3 + 4 + 3 + 5 = 16 km'dir.

Kaynakça : Yöneylem Araştırması ( HAMDY A. TAHA ) , Literatür Yayınları