Ulaştırma ve Altyapı Bakanlığı tarafından yürütülen 'Akıllı Otoyol' projesi kapsamında, gü… — KPSS İstatistik

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 ( $M_1, M_2, M_3, M_4, M_5$ ve $M_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âh	Maliyet (Yüz Bin TL)
$M_4 - M_5$	5
$M_1 - M_2$	6
$M_1 - M_3$	7
$M_1 - M_4$	8
$M_5 - M_6$	9
$M_2 - M_3$	10
$M_3 - M_4$	11
$M_4 - M_6$	12
$M_2 - M_6$	15

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?

35Answer
B
36
C
38
D
41
E
42

Answer

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.

Step-by-Step Solution

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.

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.

Ç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:

M_4 - M_5

(5) seçildi.
2. Kenar:

M_1 - M_2

(6) seçildi.
3. Kenar:

M_1 - M_3

(7) seçildi.
4. Kenar:

M_1 - M_4

(8) seçildi.
5. Kenar:

M_5 - M_6

(9) seçildi.
Sonraki en küçük kenar olan

M_2 - M_3

(10) seçilseydi

M_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.

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.

Key Concept

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.

Question

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Topics

More questions from this topic