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-
Algorithmen und Varianten: Zur Lösung kommen verschiedene Verfahren zum Einsatz, darunter der Ford-Fulkerson-Algorithmus, die Edmonds-Karp-Variante, Dinic-
Anwendungen: Netzflussprobleme finden Anwendungen in Logistik, Transportplanung, Telekommunikation, Datenrouting und Bildverarbeitung (z. B. Graph-Cut-Verfahren zur Segmentierung).