8.3 Algorithmus von Ford-Fulkerson

Aus dieser Eigenschaft läßt sich ein erster generischer Algorithmus zur Berechnung des maximalen Flusses ableiten: der Algorithmus von Ford-Fulkerson (1962)

     Finde einen zulässigen Fluß f in G
     REPEAT
          erhöhe diesen Fluß f
     UNTIL eine Erhöhung von f ist nicht möglich

Die Korrektheit dieses Algorithmus folgt unmittelbar aus dem folgenden Satz:

Ein Fluß f ist maximal $\iff$ Es gibt keinen erweiternden Weg.

Beweis:

$$\Rightarrow$$ klar !

$$\Leftarrow$$ Der Beweis wird dem Leser hier noch schuldig geblieben und folgt später.