YÖNEYLEM ARAŞTIRMASI

Bir ağdaki düğüm noktalarını birleştiren çizgiler ise kenarlar veya arklar olarak adlandırılmaktadır.

Bu şeklin 4 düğüm noktası/tepe noktası ve 3 kenarı/arkı vardır.

Eğer bir ağaç aynı zaman bağlı bir ağ ise bu durumda ona kapsayan ağaç denir.

En Küçük Kapsayan Ağaç Algoritması Adımları şunlardır ve toplam 3 tanedir (KİTAP Sayfa 166): 

Adım 1. Bize verilen düğüm noktalarından herhangi birini ve bu düğüm noktasına en yakın düğüm noktasını belirleyerek bu iki düğüm noktasını bir kenarla birleştir.

Adım 2. Henüz bağlantı kurulmamış tüm düğüm noktaları içinden, bir birine bağlanmış tüm düğüm noktalarına en kısa uzaklık değerine sahip olanı seç ve aralarındaki uzaklık değerinin en kısa olduğu düğümleri bir kenarla birleştir. Aralarındaki uzaklık değerlenin en küçük olduğu düğüm noktaları çifti birden fazla olabildiği durumlarda bu çifti keyfi olarak seçebilirsiniz. Bu seçim en iyi çözüm değerini değiştirmez ama belki alternatif en küçük kapsayan ağaç oluşmasına olanak sağlayabilir.

Adım 3. Eğer henüz bağlantı kurulmamış düğüm noktası varsa Adım 2’ye git, diğer durumda algoritmayı sonlandır: en iyi çözüm bulunmuştur.

Soruda verilen I. İFADE (Bağlantı kurulmamış düğüm noktası yoksa algoritmayı sonlandır: en iyi çözüm bulunmuştur.) Adım 3' aittir. 

Soruda verilen II. İFADE (Henüz bağlantı kurulmamış tüm dü­ğüm noktaları içinden, bir birine bağlanmış tüm düğüm noktalarına en kısa uzaklık değerine sahip olanı seç ve aralarındaki uzaklık değerinin en kısa olduğu düğümleri bir kenarla birleştir), Adım 2'ye aittir. 

Soruda verilen III. İFADE (Bize verilen düğüm noktalarından her­hangi birini ve bu düğüm noktasına en yakın düğüm noktasını belirleyerek bu iki düğüm noktasını bir ke­narla birleştir.) Adım 1' aittir. 

SORU (yönergelerden hangisi veya hangileri En Küçük Kapsayan Ağaç Algoritmasının 1.adımında yer alır?) Sadece 1.adıma ait olan yönergeyi istediğine göre DOĞRU ŞIK C

Kenarlar

Uzaklıklar

{B}

B – A

3*

{B, A}

A – C

3 + 1 = 4*

A – S

3 + 5 = 8

{B, A, C}

C – D

4 + 2 = 6*

A – S

8

{B, A, C, D}

D – S

6 + 4 = 10

A – S

8*

Son olarak S noktası da kalıcı kümeye eklendiğinde uzaklık 8 bulunmuş olur. Yol da B – A – S şeklindedir.

Kalıcı Küme

Kenarlar

Uzaklıklar

{B}

B – A

  2*

B – S

8

{B, A}

A – C

2 + 4 = 6*

B – S

8

{B, A, C}

C – D

6 + 5 = 11

C – S

6 + 1 = 7*

B – S

8

Son olarak S noktası da kalıcı kümeye eklendiğinde uzaklık 7 bulunmuş olur. Yol da B – A – C – S şeklindedir.

İkinci iterasyon. Şimdi B ve C bağlı düğüm noktaları kümesini, A, D, E, F ise henüz bağlantı kurulmamış düğüm noktaları kümesini oluşturmaktadır. Bu düğüm noktaları içerisinden B ve C noktalarına uzaklığı en küçük olan düğüm noktasını seçmeliyiz. B ve C ile bağlantısı olabilecek düğüm noktaları A, D, E, ve F noktaları, bunların içinde en yakını ise C’ye uzaklığı 2 birim olan F noktasıdır. F ile C arasında bir kenar ekleyerek bir sonraki iterasyona geçiyoruz.

Üçüncü iterasyon. Şimdi B, C, ve F bağlı düğüm noktaları kümesini, A, D, E ise henüz bağlantı kurulmamış düğüm noktaları kümesini oluşturmaktadır. Bu düğüm noktaları içerisinden B, C ve F noktalarına uzaklığı en küçük olan düğüm noktasını seçmeliyiz. B, C, F ile bağlantısı olabilecek düğüm noktaları A, D ve E noktaları, bunların içinde en yakını ise F’ye uzaklığı 3 birim olan D noktasıdır. F ile D arasında bir kenar ekleyerek bir sonraki iterasyona geçiyoruz.

Dördüncü iterasyon. Şimdi B, C, D ve F bağlı düğüm noktaları kümesini, A ve E ise henüz bağlantı kurulmamış düğüm noktaları kümesini oluşturmaktadır. Bu düğüm noktaları içerisinden B, C, D ve F noktalarına uzaklığı en küçük olan düğüm noktasını seçmeliyiz. B, C, D, F ile bağlantısı olabilecek düğüm noktaları A ve E noktaları, bunların içinde en yakını ise B’ye uzaklığı 4 birim olan E noktasıdır. B ile E arasında bir kenar ekleyerek bir sonraki iterasyona geçiyoruz.

Beşinci iterasyon. Şimdi B, C, D, E ve F bağlı düğüm noktaları kümesini, A ise henüz bağlantı kurulmamış düğüm noktaları kümesini oluşturmaktadır. Bu düğüm noktaları içerisinden B, C, D, E ve F noktalarına uzaklığı en küçük olan düğüm noktasını seçmeliyiz. B, C, D, E, F ile bağlantısı olabilecek A noktasının bağlı düğüm noktaları kümesine en yakın uzaklığı B noktasına 6 birimdir. B ile A arasında bir kenar ekliyoruz ve bağlantı kurulmamış düğüm noktası kalmadığından algoritmayı sonlandırıyoruz.

Kalıcı Küme

Kenarlar

Uzaklıklar

{B}

B – A

3*

B – S

8

{B,A}

A – C

3 + 6 = 9

A – S

  3 + 4 = 7*

B – S

8

{B,A,S}

A – C

9

Bütün tablo bu şekildedir. C noktasını da kalıcı kümeye eklediğimizde en kısa yolun B-A-S olarak 7 birim uzunluğunda olduğunu görürüz.