Akış ağı

Kaynaktan hedefe akış ağı modelini öğrenirsin.

Akış ağı

Bir akış ağı, yönlü kenarlarına kapasite atanmış bir graftır. İki özel düğüm vardır: kaynak (s) ve hedef (t).

Her kenar üzerindeki akış, sıfır ile kenar kapasitesi arasında bir değer alır. Akış korunan bir büyüklüktür: her iç düğüme giren akış, çıkan akışa eşittir.

Bu model; şu dağıtımı, trafik, veri iletimi ve eşleştirme gibi birçok gerçek problemi temsil eder.

Akış ve kapasite

Her kenarın bir kapasitesi vardır: o kenardan geçebilecek maksimum akış. Gerçek akış bu kapasiteyi aşamaz.

Akış korunan bir büyüklüktür: her iç düğümde giren akış toplamı, çıkan akış toplamına eşittir. Kaynaktan çıkan toplam akış, hedefe giren toplam akışa eşittir.

Bu koruma koşulu, ağ akışı algoritmalarının temelini oluşturur.

Uygulama source_capacity fonksiyonu

source_capacity(graph, source) yaz. graph bir kenar listesi (u, v, c); kaynaktan çıkan kenarların toplam kapasitesini döndür. print(source_capacity([('s','a',3), ('s','b',2), ('a','t',2), ('b','t',3)], 's')) ile 5 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',3), ('s','b',2), ('a','t',2), ('b','t',3)], 's'))

Kendini test et

Kaynak düğümün özelliği nedir?
```
graph = [('s','a',3), ('s','b',2)]
```
- Yalnızca gelen kenarları vardır
- Yalnızca giden kenarları vardır
- Kapasitesi sıfırdır
- Hedef ile aynıdır
Cevabı göster

Yalnızca giden kenarları vardır — Kaynak yalnızca giden kenarlara sahiptir.

kapasite koşulu

if flow[u][v] <= capacity[u][____]:
    # akış geçerli

Cevabı göster

if flow[u][v] <= capacity[u][v]:
    # akış geçerli

Akış ağı kavramları

kaynak

Akış üretir
hedef

Akış tüketir
kapasite

Maksimum akış
korunum

Giren = çıkan

Sıradaki ders: Ford-Fulkerson

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler