Flüsse in Netzwerken

In Graphen und Netzwerken trifft man häufig auf die Problemstellung, einen Fluss zu bestimmen. Dabei kann es sich um einen Güterfluss durch ein Logistiknetz handeln, um Informationen, die in einem Kommunikationsnetzwerk zwischen den Teilnehmerinnen und Teilnehmern ausgetauscht werden, oder um den Transport von Erdgas in einem Versorgungsnetz. Meist ist das Ziel die Bestimmung eines maximalen Flusses zwischen zwei gegebenen Knoten, wobei die Kapazität jeder einzelnen Kante beschränkt ist. Oft ist man auch daran interessiert, eine vorgegebene Flussmenge möglichst kostengünstig von einem Start- zu einem Zielkonten zu transportieren, man sucht also einen Fluss mit minimalen Kosten.