Maximalflüsse

Satz: die Aussagen sind äquivalent:

• f ist Maximalfluß für N
• es gibt keinen vergrößernden Weg P für N und f.

Beweis: ,,$\to$`` ist klar. Interessant ist ,, $\leftarrow$``.

Betrachte S : = Menge aller Knoten x, die von q aus über einen Weg aus nützlichen Vorwärts- und Rückwärtskanten erreichbar sind. (e ist nützlich, wenn $\Delta_{f}^{}$(e) > 0.)

Zeige: S definiert Schnitt und dann c(S) = f (N).

Bemerkung: falls man Rückwärtskanten nicht gestattet, gilt der Satz nicht (,,$\to$`` ja, aber ,, $\leftarrow$`` nicht)