Examkin

Question

Difficulty: HardEn 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. 34Answer
  3. C
    36
  4. D
    45
  5. E
    46

Answer

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.

Step-by-Step Solution

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.

Key Concept

En Küçük Yayılan Ağaç (Minimum Spanning Tree) Problemi ve Topoloji Analizi
Rate this question

Topics

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

More questions from this topic