Ağ Akışları ve Tamsayı Programlama #06 | Minimum kapsayan ağaç ve Prim algoritması

Eğitmen: Dr. Süleyman Burak ÇELİK

Altı tesisi düşük maliyetle bağlayan bir ağ kuruyoruz. Prim algoritmasında her adımda bağlı kümeyi ve bu kümeden dışarı çıkan aday kenarları güncelliyoruz. Özgün örnekte seçilen beş bağlantının toplamı 14 bin TL. Bağlılık, çevrimsizlik ve maliyet kontrollerini ayrı yapıyor; kesit ve değiş tokuş düşüncesiyle seçimin neden güvenli olduğunu açıklıyoruz. Minimum kapsayan ağacın en kısa yol problemiyle aynı şey olmadığını somut bir karşılaştırmayla gösteriyoruz. Bölümler: 00:00 Bütün noktaları düşük maliyetle bağla 01:11 Ağın dili: düğüm, kenar, yol ve çevrim 02:19 Altı tesis ve on iki aday bağlantı 03:43 Bağlı kümeyi bir düğümle büyüt 04:49 Birinci adım: A’dan başla 05:50 İkinci adım: sınırı yeniden hesapla 06:58 Üçüncü adım: D düğümünü ekle 08:05 Dördüncü adım: E düğümüne geç 09:09 Beşinci adım: son düğümü bağla 10:14 Ağaç ve toplamı ayrı ayrı doğrula 11:20 En ucuz sınır kenarı neden güvenli? 12:25 Ucuz kenarları saymak tek başına yetmez 13:52 En ucuz ağ, en kısa yol sorusu değildir 15:00 Üç kısa kontrol 16:36 Ağı kurduk, seçim kuralını gerekçelendirdik Kaynak: Hamdy A. Taha, Operations Research: An Introduction, 10. baskı; §6.1–6.2; kitap s.247–252 (PDF s.248–253). Anlatım, örnek veriler ve görseller özgündür. AcEdumy — mühendislik derslerini adım adım öğren.

Bu videoyu izlemek için Premium üyelik gerekir.