8.2 Erweiternder Weg

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) $\in$ E mit f (i,j) < c(i,j)

oder

(ii)

Es existiert eine Rückwärtskante (j,i) $\in$ 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.