Özet - Network flow

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.

Örnek çözümü göster

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'))

Kendini test et

Edmonds-Karp hangi yöntemi kullanır?
- DFS
- Greedy
- BFS
- DP
Cevabı göster

BFS — Edmonds-Karp BFS ile en kısa yol bulur.

maksimum akış değeri

# max_flow = min_cut_capacity
# max_flow == ____

Cevabı göster

# max_flow = min_cut_capacity
# max_flow == min_cut

Yöntem-araç

Ford-Fulkerson

DFS
Edmonds-Karp

BFS
maks akış min kesim

Teorem
iki parçalı eşleştirme

Uygulama

Sıradaki ders: Minimax

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler