Examkin

Soru

Zorluk: ZorEn Küçük Yayılan Ağaç Problemi

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?

  1. A
    24
  2. 34Cevap
  3. C
    36
  4. D
    45
  5. E
    46

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
Bu soruyu puanla

Konular

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

Bu konudan daha fazla soru