Netzflussprobleme

Netzflussprobleme sind Optimierungsprobleme, die in Graphen mit Kapazitäten auftreten. Ein solcher Fall besteht aus einem Graphen G=(V,E) mit Kapazitäten c(e)≥0 für alle Kanten e∈E, sowie zwei besonderen Knoten s (Quelle) und t (Senke). Ein Fluss f ordnet jeder Kante eine Flussmenge zu, die 0 ≤ f(e) ≤ c(e) erfüllt. An allen Knoten v ≠ s, t gilt das Flussausgleichsprinzip: Die Summe der hereinkommenden Flüsse entspricht der Summe der herausgehenden Flüsse. Der Wert des Flusses wird durch die Summe der Flüsse bestimmt, die den Quelle-Knoten verlassen. Netzflussprobleme zielen oft darauf ab, diesen Wert zu maximieren, können aber auch andere Ziele verfolgen, etwa minimale Kosten bei gegebenem Fluss, oder Zirkulationsprobleme mit Anforderungen.

Max-Flow-Problem und Dualität: Beim Max-Flow-Problem geht es darum, den Flusswert von s nach t unter den Kapazitäts- und Ausgleichsbedingungen zu maximieren. Das Max-Flow-Min-Cut-Theorem besagt, dass der maximale Flusswert gleich der Kapazität des kleinsten Cuts ist, der das Graphen in eine Teilmenge S (enthält s) und T (enthält t) teilt. Solche Formulierungen lassen sich entweder als Flussprobleme oder als Schnittprobleme behandeln.

Algorithmen und Varianten: Zur Lösung kommen verschiedene Verfahren zum Einsatz, darunter der Ford-Fulkerson-Algorithmus, die Edmonds-Karp-Variante, Dinic- und Preflow-Push-Verfahren. Vorteile treten besonders bei ganzzahligen Kapazitäten zutage, da Terminierung garantiert. Als Varianz ergänzt der Min-Cost-Flow das Modell um Kosten pro Kante und Ziel, die Gesamtkosten bei einer vorgegebenen Flussmenge zu minimieren. Weitere Varianten umfassen Zirkulationen mit Anforderungen oder Flussuntergrenzen.

Anwendungen: Netzflussprobleme finden Anwendungen in Logistik, Transportplanung, Telekommunikation, Datenrouting und Bildverarbeitung (z. B. Graph-Cut-Verfahren zur Segmentierung). Das Modell verbindet Graphentheorie, Optimierung und Algorithmik.