Özet - Network flow
- Algoritmalar kursu
- Uzman seviye
- Ders 30/41
- 4 dk
Maksimum akışı yazdıran mini görev yaparsın.
Özet - Network flow
Bu grupta ağ akışının temellerini gördük: akış ağı, Ford-Fulkerson, Edmonds-Karp, maksimum akış minimum kesme ve iki parçalı eşleştirme.
Ford-Fulkerson ve Edmonds-Karp, artık yollarla maksimum akışı bulur. Maksimum akış minimum kesme teoremi bunu kesim problemine bağlar; iki parçalı eşleştirme ise bir uygulamadır.
Şimdi kaynak kapasitesini küçük bir görevle tekrar edeceğiz.
Uygulama source_capacity mini görev
source_capacity(graph, source) yaz. Kaynaktan çıkan kenarların toplam kapasitesini döndür. print(source_capacity([('s','a',5), ('s','b',3), ('a','t',4)], 's')) ile 8 yazdır.
Başlangıç kodu
def source_capacity(graph, source):
# Kaynaktan çıkan toplam kapasiteÖrnek çözüm
def source_capacity(graph, source):
# Kaynaktan çıkan toplam kapasite
total = 0
for u, v, c in graph:
if u == source:
total += c
return total
print(source_capacity([('s','a',5), ('s','b',3), ('a','t',4)], 's'))Beklenen çıktı
8
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Edmonds-Karp hangi yöntemi kullanır?
- DFS
- Greedy
- BFS Doğru cevap
- DP
Açıklama: Edmonds-Karp BFS ile en kısa yol bulur.
2 maksimum akış değeri
# max_flow = min_cut_capacity
# max_flow == ____# max_flow = min_cut_capacity
# max_flow == min_cutAçıklama: Maksimum akış minimum kesime eşittir.
3 Yöntem-araç
| Kavram | Anlamı |
|---|---|
Ford-Fulkerson |
DFS |
Edmonds-Karp |
BFS |
maks akış min kesim |
Teorem |
iki parçalı eşleştirme |
Uygulama |