Ein erweiternder Weg in G ist eine Folge von Knoten, beginnend bei
s und endend bei t , wobei für zwei aufeinanderfolgende Knoten i und j
gilt:
- (i)
- Es existiert eine Vorwärtskante (i,j) E mit
f (i,j) < c(i,j)
- oder
- (ii)
- Es existiert eine Rückwärtskante (j,i) E mit f (j,i) > 0.
Längs so eines erweiternden Weges kann der Fluß vergrößert werden, indem
man durch die Vorwärtskanten zusätzliche Einheiten fließen läßt oder man
den Fluß in den Rückwärtskanten verringert. Beides ist nach der Definition
des erweiternden Weges möglich.