Flußvergrößernde Wege

Betrachte Knotenfolgen P = (q = x₀, x₁,..., x_n = s),

so daß für jedes i:

• x_ix_{i + 1} $\in$ E(G) (Vorwärtskante)
• oder x_{i + 1}x_i $\in$ E(G) (Rückwärtskante)

Für Netzwerk N, Knotenfolge P wie oben, Fluß f:

• für Vorwärtskante xy: setze $\Delta$(xy) = c(xy) - f (xy)
• für Rückwärtskante xy: setze $\Delta$(xy) = f (xy)

Setze $\Delta$(P) = min{$\Delta$(xy) | xy $\in$ P}.

P heißt vergrößernder Weg, falls $\Delta$(P) > 0.

Def: f$\mid_{P}^{}$ ist die Funktion e $\mapsto$

• wenn e Vorwärtskante in P, dann f (e) + $\Delta$(P),
• wenn e Rückwärtskante in P, dann f (e) - $\Delta$(P),
• wenn e nicht in P, dann f (e).

Satz: Wenn f Fluß für N und P vergrößernder Weg,

dann ist auch f$\mid_{P}^{}$ Fluß für N, und f$\mid_{P}^{}$(N) = f (N) + $\Delta$(P).