TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 27

Use the algorithm of Ford and Fulkerson to compute a maximal flow in the network

G_{2}

which has two sources

s_{1}

and

s_{2}

!

Solution

First residual flow:

First flow:

Second residual flow:

Second flow:

Third residual flow:

Third flow:

Fourth residual flow:

Fourth flow:

Final residual flow and minimal cut: