Flussproblem

Flussproblem, auch als Netzwerkflussproblem bekannt, ist ein fundamentales Problem der Graphentheorie und Optimierung. Gegeben ist ein gerichteter Graph G=(V,E) mit Kapazitätsfunktion c:E→R+, sowie zwei besondere Knoten s (Quelle) und t (Senke). Ein Fluss f:E→R+ erfüllt 0 ≤ f(e) ≤ c(e) für alle Kanten e∈E und die Konservierung: Für alle v∈V mit v ≠ s,t gilt Sum_{(u,v)∈E} f(u,v) = Sum_{(v,w)∈E} f(v,w). Der Wert des Flusses ist |f| = Sum_{(s,v)∈E} f(s,v) - Sum_{(v,s)∈E} f(v,s) und entspricht dem ausgehenden Fluss aus der Quelle.

Das klassische Flussproblem ist das Maximum-Flow-Problem: Es soll der maximale Wert |f| erreicht werden. Ein zentrales Theorem ist der Max-Flow-Min-Cut-Satz, der besagt, dass der maximale Flusswert gleich der Kapazität eines minimalen s-t-Schnitts ist. Rechenverfahren umfassen Algorithmen wie Ford-Fulkerson, Edmonds-Karp (BFS-basiert), Dinic und Push-Relabel. Je nach Netzwerkstruktur ergeben sich unterschiedliche Laufzeiten.

Es existieren Variationen und Erweiterungen, etwa Flüsse mit unteren Schranken, der Minimum-Cost-Flow (Kosten minimieren bei festgelegtem Fluss), Flüsse mit Forderungen (Demands) oder Mehrziel- bzw. Mehrkomponentenflüsse. Anwendungen finden sich in Transport- und Logistikplanung, Telekommunikations- und Netzwerkinfrastruktur, Energie- und Wasserverteilung sowie in der Optimierung von Supply Chains.

Historisch entstand das Flussproblem in den 1950er Jahren durch Ford und Fulkerson; seitdem bildet es eine zentrale Grundlage in Theorien und Algorithmen.