Akış ağı
- Algoritmalar kursu
- Uzman seviye
- Ders 25/41
- 4 dk
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.
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',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 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 Doğru cevap
- Kapasitesi sıfırdır
- Hedef ile aynıdır
Açıklama: Kaynak yalnızca giden kenarlara sahiptir.
2 kapasite koşulu
if flow[u][v] <= capacity[u][____]:
# akış geçerliif flow[u][v] <= capacity[u][v]:
# akış geçerliAçıklama: capacity[u][v] ile karşılaştırma yapılır.
3 Akış ağı kavramları
| Kavram | Anlamı |
|---|---|
kaynak |
Akış üretir |
hedef |
Akış tüketir |
kapasite |
Maksimum akış |
korunum |
Giren = çıkan |