Maksimum akış minimum kesme

Maksimum akış minimum kesme teoremini öğrenirsin.

Maksimum akış minimum kesme

Maksimum akış minimum kesme teoremi, bir akış ağında maksimum akışın, ağı ikiye bölen herhangi bir kesimin minimum kapasitesine eşit olduğunu söyler.

Bir kesim, düğümleri S ve T olarak ikiye ayırmadır; kaynak S'de, hedef T'de bulunur. Kesimin kapasitesi, S'ten T'ye giden kenarların kapasitelerinin toplamıdır.

Bu teorem, akış problemlerini kesim problemlerine bağlar; birçok pratik uygulaması vardır.

Kesim bulma

Maksimum akış bulunduktan sonra, minimum kesim kolayca elde edilir. Artık grafta kaynaktan ulaşılabilen tüm düğümler S kümesini, geri kalanlar T kümesini oluşturur.

S'ten T'ye giden orijinal kenarlar, minimum kesimi verir. Bu kenarlar maksimum akışta tamamen doyurulmuştur.

Bu yapı, teoremin yapıcı kanıtını da sağlar.

Uygulama cut_capacity fonksiyonu

cut_capacity(capacity, s_set) yaz. capacity kenar listesi (u, v, c); S kümesinden T kümesine giden kenarların toplam kapasitesini döndür. print(cut_capacity([('s','a',3), ('s','b',2), ('a','t',2), ('b','t',3)], {'s'})) ile 5 yazdır.

Örnek çözümü göster

def cut_capacity(capacity, s_set):
    # S'ten T'ye kesim kapasitesi
    total = 0
    for u, v, c in capacity:
        if u in s_set and v not in s_set:
            total += c
    return total
print(cut_capacity([('s','a',3), ('s','b',2), ('a','t',2), ('b','t',3)], {'s'}))

Kendini test et

Maksimum akış neye eşittir?
```
max_flow = min_cut_capacity
```
- Minimum kesim kapasitesine
- Toplam kenar sayısına
- En uzun yola
- Kaynak derecesine
Cevabı göster

Minimum kesim kapasitesine — Maksimum akış minimum kesim kapasitesine eşittir.

kesim kapasitesi

total = 0
for u, v, c in capacity:
    if u in s_set and v not in ____:
        total += c

Cevabı göster

total = 0
for u, v, c in capacity:
    if u in s_set and v not in s_set:
        total += c

Max-flow min-cut kavramları

maksimum akış

Minimum kesim
S kümesi

Kaynak tarafı
T kümesi

Hedef tarafı
kesim kenarı

Tam doygun

Sıradaki ders: İki parçalı eşleştirme

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler