Netzfluss

Netzfluss, in der Graphentheorie und Operations Research, bezeichnet das Flussproblem in einem gerichteten Netzwerk. Ein Netz besteht aus Knoten (Punkten) und Kanten (Kanten) mit Kapazitäten. Ein Fluss ordnet jeder Kante einen nichtnegativen Wert zu, der die transportierte Größe darstellt; für alle Knoten außer Quelle s und Senke t gilt Flusseinschränkung: Der Fluss, der in einen Knoten hinein- oder herausfließt, muss ausgeglichen sein. Die Quelle liefert oder erzeugt den Fluss, die Senke entnimmt ihn. Der Wert des Flusses ist die Gesamtsumme des Flusses, der in die Senke fließt, und das Ziel ist oft, diesen Wert zu maximieren.

Zu den zentralen Problemen gehört das Maximum-Flow-Problem: Bestimme den größten möglichen Fluss von s nach t. Dazu gehört auch das Minimum-Cut-Theorem: Der maximale Fluss entspricht dem Fluss, der durch eine minimale s-t-Schnittkante von s nach t getrennt wird. Relevante Algorithmen umfassen das Ford-Fulkerson-Verfahren, das durch sukzessives Auffüllen von Pfaden arbeitet, sowie seine polynomialzeitliche Umsetzung Edmonds–Karp. Fortgeschrittene Algorithmen wie Dinic oder Push-relabel-Methoden verbessern die Laufzeit in vielen Fällen.

Anwendungen finden sich in Telekommunikation, Transport- und Logistikplanung, Strom- und Wassernetzen, Datenfluss in Computernetzen sowie in der Bildverarbeitung, etwa bei der Segmentierung von Bildern durch Max-Flow/Min-Cut-Verfahren. Es existieren zahlreiche Varianten, darunter Mehrkomponenten-Flussmodelle (Multicommodity flow), zeitversetzte Netze oder stochastische Flüsse.

Historisch lässt sich Netzfluss auf Arbeiten der 1950er Jahre zurückführen, besonders Ford und Fulkerson, die das Grundprinzip und das Theorem formulierten. Seitdem ist Netzfluss ein grundlegendes Werkzeug in Optimierung und Netzwerkanalyse.