Negative-Kreise-Optimalitätsbedingung

Die Zirkulation $x$ ist optimal für das Minimalkosten-Zirkulations-Problem, wenn das Residualnetzwerk keinen negativen Kreis bezüglich der Kostenfunktion mehr enthält.

Veranschaulichung des Beweis