Examkin

En Küçük Yayılan Ağaç Problemi

2 soru

Soru 1Soru →

Ulaştırma ve Altyapı Bakanlığı tarafından yürütülen 'Akıllı Otoyol' projesi kapsamında, güzergâh üzerindeki 6 farklı kontrol istasyonu (M1,M2,M3,M4,M5M_1, M_2, M_3, M_4, M_5 ve M6M_6) arasında yeraltı fiber optik haberleşme ağı kurulması planlanmaktadır.

İstasyonlar arasındaki olası kablo güzergâhları ve bu güzergâhların tahmini kurulum maliyetleri (yüz bin TL cinsinden) aşağıdaki tabloda verilmiştir:

GüzergâhMaliyet (Yüz Bin TL)
M4−M5M_4 - M_55
M1−M2M_1 - M_26
M1−M3M_1 - M_37
M1−M4M_1 - M_48
M5−M6M_5 - M_69
M2−M3M_2 - M_310
M3−M4M_3 - M_411
M4−M6M_4 - M_612
M2−M6M_2 - M_615

Projenin amacı, tüm istasyonları birbirine bağlayan kesintisiz bir ağ kurarken toplam kurulum maliyetini en aza indirmektir.

Buna göre, kurulacak olan en düşük maliyetli fiber optik ağın toplam maliyeti kaç yüz bin TL olur?

Cevabı ve açıklamayı göster

Cevap: 35

Cevap

En küçük yayılan ağacın toplam maliyeti 35 yüz bin TL'dir.
Doğru çözüm, Kruskal algoritması uygulanarak maliyetlerin küçükten büyüğe sıralanması ve çevrim oluşturmayan ilk 5 kenarın (5, 6, 7, 8 ve 9 maliyetli kenarlar) seçilmesiyle elde edilir. Bu kenarların toplamı 35'tir.

Adım Adım Çözüm

1
Problemin türünü belirleme.
Tüm düğümleri (istasyonları) birbirine bağlayan ve toplam kenar ağırlığı (maliyeti) en düşük olan yapıyı bulmamız gerektiğinden, bu bir 'En Küçük Yayılan Ağaç (Minimum Spanning Tree)' problemidir.
Kesintisiz bir haberleşme ağı kurmak ve bunu minimum maliyetle yapmak En Küçük Yayılan Ağaç problemi modelini gerektirir.
2
Kruskal algoritmasını uygulamak için kenarları maliyetlerine göre küçükten büyüğe sıralama.
Sıralama: (M4-M5)=5, (M1-M2)=6, (M1-M3)=7, (M1-M4)=8, (M5-M6)=9, (M2-M3)=10, (M3-M4)=11, (M4-M6)=12, (M2-M6)=15.
Kruskal algoritması, döngü oluşturmamak şartıyla her adımda en düşük maliyetli kenarın ağa eklenmesi prensibiyle çalışır.
3
Çevrim (döngü) oluşturmayacak şekilde en düşük maliyetli kenarları seçerek ağı oluşturma (N=6 düğüm için N-1=5 kenar seçilmelidir).
1. Kenar: M4−M5M_4 - M_5 (5) seçildi.
2. Kenar: M1−M2M_1 - M_2 (6) seçildi.
3. Kenar: M1−M3M_1 - M_3 (7) seçildi.
4. Kenar: M1−M4M_1 - M_4 (8) seçildi.
5. Kenar: M5−M6M_5 - M_6 (9) seçildi.
Sonraki en küçük kenar olan M2−M3M_2 - M_3 (10) seçilseydi M1−M2−M3M_1-M_2-M_3 arasında döngü oluşacaktı. 5 kenara ulaşıldığı ve tüm düğümler bağlandığı için işlem tamamlandı.
Bir ağaçta döngü bulunamaz ve 6 düğümlü bir sistemin tam olarak bağlanması için tam olarak 5 kenar gerekir.
4
Seçilen kenarların maliyetlerini toplama.
Toplam Maliyet = 5 + 6 + 7 + 8 + 9 = 35 yüz bin TL.
En Küçük Yayılan Ağacın (MST) toplam değeri, seçilen optimum kenarların ağırlıkları toplamıdır.

Anahtar Kavram

En Küçük Yayılan Ağaç problemi (Minimum Spanning Tree), bir şebekedeki tüm düğümleri döngü yaratmadan birbirine bağlayan en düşük toplam ağırlıklı kenar kümesini bulmayı amaçlar.
Soru 2Soru →

Bir ulusal demiryolu şirketi, 7 farklı lojistik merkezi (A,B,C,D,E,F,GA, B, C, D, E, F, G) arasında kesintisiz bir yüksek hızlı veri iletişim ağı kurmak istemektedir. Merkezler arası veri hatlarının olası güzergahları ve kurulum maliyetleri (milyon TL) aşağıdaki tabloda verilmiştir:

HatMaliyetHatMaliyet
A-B13C-E12
A-C8C-F10
A-D16D-F14
B-C9E-F5
B-E15E-G17
C-D7F-G6

Şebekedeki tüm merkezlerin birbirine bağlanması (herhangi iki merkez arasında bir veri yolu olması) ve toplam kurulum maliyetinin en aza indirilmesi hedeflenmektedir.

Buna göre, optimum şebeke ağı (en küçük yayılan ağaç) oluşturulduğunda, CC merkezine doğrudan bağlanan hatların kurulum maliyetleri toplamı kaç milyon TL olur?

Cevabı ve açıklamayı göster

Cevap: 34

Cevap

Optimum ağda C merkezine bağlanan hatların maliyetleri toplamı 34 milyon TL'dir.
Verilen şebeke probleminde Prim veya Kruskal algoritması uygulandığında en küçük yayılan ağaç (MST) şu hatlardan oluşur: E-F (5), F-G (6), C-D (7), A-C (8), B-C (9) ve C-F (10). Oluşan bu optimal ağaç topolojisinde, C düğümü merkezî bir köprü görevi görerek A, B, D ve F düğümlerine doğrudan bağlanmaktadır. Bu dört bağlantının maliyetleri toplamı 7+8+9+10=347 + 8 + 9 + 10 = 34 milyon TL olarak hesaplanır.

Adım Adım Çözüm

1
Kruskal veya Prim algoritması kullanarak en düşük maliyetli hatlardan başlayarak çevrim oluşturmayacak şekilde kenarları seçmek.
Sırasıyla E-F (5), F-G (6), C-D (7), A-C (8), B-C (9) hatları ağaca eklenir.
En küçük yayılan ağaç (MST) oluşturmanın temel kuralı, en düşük maliyetli bağlantıları çevrim (döngü) yaratmadan sisteme dahil etmektir.
2
{A,B,C,D} düğümleri ile {E,F,G} düğümlerini birbirine bağlayacak en düşük maliyetli hattı belirlemek.
Kalan olası bağlantılar arasından en düşük maliyetli olan C-F (10) hattı seçilir ve tüm şebeke birbirine bağlanmış olur.
Şebekenin iki ayrı parçasını (alt ağacı) birleştirmek için aralarındaki en kısa (en ucuz) köprü kullanılmalıdır.
3
Oluşturulan en küçük yayılan ağaç üzerinde sadece C merkezine doğrudan temas eden hatları bulup maliyetlerini toplamak.
C merkezine bağlanan hatlar: C-D (7), A-C (8), B-C (9) ve C-F (10). Toplam = 7 + 8 + 9 + 10 = 34.
Soru bizden tüm ağın maliyetini değil, ağaç yapısı oluştuktan sonra spesifik olarak C düğümündeki fiziksel bağlantı yükünü (maliyetini) istemektedir.

Anahtar Kavram

En Küçük Yayılan Ağaç (Minimum Spanning Tree) Problemi ve Topoloji Analizi
En Küçük Yayılan Ağaç Problemi Alıştırma Soruları — KPSS İstatistik | Examkin