Maximum flow problem
Einfache Sprache
Hier sind der Knoten $s$ die Quelle (Start) und $t$ die Senke (Ziel) des Flusses.
Maximum flow problem
Gegeben sei ein Netzwerk $N=(G=(V,E),k,s,t)$. Gesucht ist ein s-t-Fluss $f$, der also sowohl die Kapazitätskonformität als auch den Flusserhalt erfüllt, und dabei den Flusswert $|f|$ maximiert.