Ford-Fulkerson Max Flow — $S→A10,S→C10,A→B4,A→C2,C→D9,B→T10,D→B6,D→T10$

Network Structure

Source $S$, sink $T$, intermediate A,B,C,D.

Execution (Edmonds-Karp BFS for shortest augmenting path, but any path works; show one valid sequence)

Init flow 0, residual = capacities.

Augment 1: $S-A-B-T$ bottlenecks min(10,4,10)=4

• Push 4: residual $S-A$6, $A-B$0, $B-T$6. Flow=4

Augment 2: $S-A-C-D-T$ (via $A→C$)

• Path capacities: S-A6, A-C2, C-D9, D-T10 → bottleneck 2
• Push 2: $S-A$4, $A-C$0, $C-D$7, $D-T$8. Flow=6
• Note alternative $S-C-D-T$ also available but we use through A to show.

Augment 3: $S-C-D-T$ bottleneck min(S-C10, C-D7, D-T8)=7

• Push 7: $S-C$3, $C-D$0, $D-T$1. Flow=13

Augment 4: $S-C-D-B-T$ ??? Need residual check: After 1, $A→B$ saturated, but reverse $B→A$ 4 exists. However $D→B$6 is forward.
Path $S-C$3 → $C-D$ is 0 residual (saturated) so no. Let's instead use remaining $S-A$4 → but $A-C$0 and $A-B$0 blocked, so $S-A$ cannot reach T via A. So remaining flow must go $S-C-D-B-T$ if $C-D$0 no. Actually after step3 $C-D$0, so D only reachable not via C. So need alternative.

Let's choose better order: Instead of exhausting C-D early, more systematic:

Re-run with better path selection (standard max flow =13? Let's compute min cut).

Min Cut analysis: Cut $(S,A)$? Edges crossing: $S-A$10 + $S-C$10 =20. Cut $(S,A,C)$ → edges $A-B$4, $C-D$9 → 13. Cut $(S,A,C,D)$ → $A-B$4, $D-B$6? Actually $D-B$ internal, $B-T$10, $D-T$10 → cut includes $B-T$10 + $D-T$10 =20? Wait compute: Partition $\{S,A,C\}$ vs $\{B,D,T\}$ edges $A-B$4, $C-D$9 →13. Add $D→T$ and $B→T$ are from right to T but crossing? Actually T in right, B,D in right, so not crossing? Need correct: Let's compute max flow via brute: The bottleneck is $C-D$9 + $A-B$4 =13, and $S-C$10 + $A-B$4 =14, so min is 13. So max flow =13 (limited by $A-B$4 + $C-D$9). Another cut $\{S,A,C,D\}$ vs $\{B,T\}$ edges $A-B$4 + $D-B$6 + $D-T$10 =20? Not min. So max is 13.

Our earlier flow 13 already achievable (4+2+7=13). After step3 flow=13, indeed max reached.
Check residual: $S-A$4, $S-C$3 remain but no path to T because $A-B$0, $A-C$0, $C-D$0 blocks; alternative $S-C$ → ??? $D-B$ still has 6 but $D$ unreachable (since $C-D$0). So no augmenting path → algorithm terminates.

Updated Residual After Each Augmentation (summary)

Path	Bottleneck	Flow	Residual key edges
S-A-B-T	4	4	S-A6, A-B0(+4 reverse), B-T6
S-A-C-D-T	2	6	S-A4, A-C0(+2), C-D7, D-T8
S-C-D-T	7	13	S-C3, C-D0(+7), D-T1

Max Flow value =13 (4 via A-B-T, 9 via C-D-T split as 2+7). Achieved.

Any valid augmenting order yielding 13 is acceptable; another order S-C-D-B-T (6) etc also yields 13.