Netzwerkfluss

# Netzwerkfluss

Überblick

Netzwerkfluss ist ein fundamentales Konzept in der Graphentheorie und Optimierung, das sich mit der effizienten Bewegung von Ressourcen durch ein Netzwerk beschäftigt. Diese Algorithmen haben weitreichende Anwendungen in Transportlogistik, Kommunikationsnetzwerken, Bioinformatik und vielen anderen Bereichen.

Grundlegende Konzepte

Flussnetzwerk

Ein Flussnetzwerk ist ein gerichteter Graph G = (V, E) mit:

• Quelle (s): Knoten ohne eingehende Kanten
• Senke (t): Knoten ohne ausgehende Kanten
• Kapazitätsfunktion c(u,v): Maximaler Fluss durch Kante (u,v)

Fluss

Ein Fluss ist eine Funktion f: E → ℝ⁺, die erfüllt:

Kapazitätsbeschränkung

0 ≤ f(u,v) ≤ c(u,v) für alle Kanten (u,v)

Flusserhaltung

∑f(u,v) = ∑f(v,w) für alle Knoten v ≠ s,t (Eingehender Fluss = Ausgehender Fluss)

Wert des Flusses

|f| = ∑f(s,v) - ∑f(v,s) (Gesamter Fluss von der Quelle minus Fluss zur Quelle)

Residualgraph

Definition

Der Residualgraph Gf zu einem Fluss f enthält für jede Kante (u,v):

• Vorwärtskante: Restkapazität cf(u,v) = c(u,v) - f(u,v)
• Rückwärtskante: Restkapazität cf(v,u) = f(u,v)

Bedeutung

• Vorwärtskanten: Zusätzlicher Fluss möglich
• Rückwärtskanten: Fluss kann reduziert werden
• Augmentierender Pfad: Pfad von s zu t im Residualgraphen

Eigenschaften

• Dynamisch: Ändert sich mit dem Fluss
• Bidirektional: Enthält Rückwärtskanten
• Kapazitäten: Zeigen verfügbare Verbesserungen