Maksimum akış minimum kesme
- Algoritmalar kursu
- Uzman seviye
- Ders 28/41
- 4 dk
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.
Başlangıç kodu
def cut_capacity(capacity, s_set):
# S'ten T'ye kesim kapasitesiÖrnek çözüm
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'}))Beklenen çıktı
5
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Maksimum akış neye eşittir?
max_flow = min_cut_capacity- Minimum kesim kapasitesine Doğru cevap
- Toplam kenar sayısına
- En uzun yola
- Kaynak derecesine
Açıklama: Maksimum akış minimum kesim kapasitesine eşittir.
2 kesim kapasitesi
total = 0
for u, v, c in capacity:
if u in s_set and v not in ____:
total += ctotal = 0
for u, v, c in capacity:
if u in s_set and v not in s_set:
total += cAçıklama: S'ten T'ye giden kenarlar toplanır.
3 Max-flow min-cut kavramları
| Kavram | Anlamı |
|---|---|
maksimum akış |
Minimum kesim |
S kümesi |
Kaynak tarafı |
T kümesi |
Hedef tarafı |
kesim kenarı |
Tam doygun |