Worked examples — Network flow — max-flow min-cut theorem, Ford-Fulkerson, Edmonds-Karp

Before anything, one picture to fix the vocabulary we reuse everywhere.

The scenario matrix

Every worked example below is tagged with the cell it covers. Together they hit all of them.

Example 1 — the baseline (Cell A)

1. Total capacity out of $s$ is $3+2=5$. So max flow $\le 5$ (nothing can enter $t$ faster than it leaves $s$). Why this step? It gives an instant upper bound — the cut $S=\{s\}$ already caps the answer. If we can reach 5 we are done.
2. Push path $s\to a\to t$, bottleneck $\min (3,2)=2$. Now $a\to t$ is saturated. Why this step? $a\to t$ is the limiter on this route; taking it first uses the cheap capacity.
3. Push path $s\to b\to t$, bottleneck $\min (2,3)=2$. Now $s\to b$ is saturated. Why this step? Independent route, no conflict with step 2.
4. Push path $s\to a\to b\to t$. Residuals: $s\to a$ has $3-2=1$ left, $a\to b=1$, $b\to t=3-2=1$. Bottleneck $=1$. Why this step? We still have $1$ unit of $s\to a$ unused; route it through $b$ to $t$.
5. Total $|f|=2+2+1=5$. No residual $s\to \cdot$ edge remains, so no augmenting path exists.

Verify: the cut $S=\{s\},T=\{a,b,t\}$ has forward capacity $c(s,a)+c(s,b)=3+2=5$. Flow $=5=$ cut $\Rightarrow$ optimal by the theorem. ✔

Example 2 — the greedy trap (Cell B)

1. Greedy push $s\to a\to b\to t$, bottleneck $1$. Now $s\to a,a\to b,b\to t$ are saturated. $|f|=1$. Why this step? This is exactly the "wrong" first choice — it blocks the two direct routes.
2. Panic check: $a\to t$ needs incoming flow at $a$, but $s\to a$ is full. $s\to b$ needs outgoing at $b$, but $b\to t$ is full. Looks stuck. Why this step? To see why greedy-without-backward-edges fails.
3. Look at the residual graph: committing $f(a,b)=1$ created a backward edge $b\to a$ of capacity $1$. New path: $s\to b\to a\to t$ using $s\to b$(1), backward $b\to a$(1), $a\to t$(1). Bottleneck $1$. Why this step? The backward edge says "I can undo up to $1$ unit of $a\to b$" — that frees $a\to t$ and $s\to b$.
4. Push it. $|f|=1+1=2$. Net effect: $f(a,b)$ dropped back to $0$; flow now goes $s\to a\to t$ and $s\to b\to t$.

Verify: cut $S=\{s\}$ gives $c(s,a)+c(s,b)=1+1=2$. Flow $=2=$ cut $\Rightarrow$ optimal. Backward edge rescued us. ✔ (See Menger's Theorem: $2$ = number of edge-disjoint $s\to t$ paths.)

Example 3 — zero / degenerate input (Cell C)

1. (3a): The only $s\to t$ route passes through the $0$-capacity edge $s\to a$. Its residual capacity is $c_f=0-0=0$, so no augmenting path exists from the start. Why this step? A $0$-capacity edge is as if the edge is absent — the definition allows it explicitly ($c=0$ "if no edge").
2. (3a) answer: max flow $=0$. The min cut is $S=\{s\}$, $c(S,T)=c(s,a)=0$. Theorem holds: $0=0$. Why this step? Confirms $0$ is a legitimate optimum, not an error.
3. (3b): $s$ can fill $a$, but $a$ has no outgoing edge to $t$. By conservation, $a$ cannot accumulate water, so nothing can flow into $a$ either. Max flow $=0$. Why this step? Conservation forbids a "dead-end pool" — flow into $a$ must equal flow out, which is $0$.
4. (3b) cut: $S=\{s,a\},T=\{t\}$. Forward edges $S\to T$: none. So $c(S,T)=0$. Again $0=0$.

Verify: In both sub-cases $\max |f|=\min c(S,T)=0$. A max flow of $0$ means $t$ is unreachable from $s$ in the residual graph — perfectly valid, never a bug. ✔

Example 4 — ties: multiple min cuts (Cell D)

1. Push $s\to a\to t$ (bottleneck $2$) and $s\to b\to t$ (bottleneck $2$). $|f|=4$. Why this step? Two independent chains, no interaction — saturate both.
2. Enumerate cuts. Each middle node $a,b$ can be on the $S$ side or $T$ side, giving $2\times 2=4$ cuts:
   • $S=\{s\}$: forward edges $s\to a,s\to b$ → capacity $2+2=4$.
   • $S=\{s,a\}$: forward $a\to t,s\to b$ → $2+2=4$.
   • $S=\{s,b\}$: forward $s\to a,b\to t$ → $2+2=4$.
   • $S=\{s,a,b\}$: forward $a\to t,b\to t$ → $2+2=4$. Why this step? We list every partition with $s\in S,t\in T$ to find which are minimal.
3. All four cuts have capacity $4$. So the min cut is not unique — every cut here is a min cut.

Verify: $\max |f|=4$ equals the minimum (indeed the only) cut capacity $4$. Ties are normal; the theorem promises a min cut equals max flow, not a unique one. ✔

Example 5 — path choice changes the work (Cell E)

1. Bad Ford-Fulkerson: always pick a path through the middle edge $a\to b$ (or its backward twin).
   • Iter 1: $s\to a\to b\to t$, bottleneck $\min (1000,1,1000)=1$. Push $1$.
   • Iter 2: $s\to b\to a\to t$ (backward $b\to a$), bottleneck $1$. Push $1$.
   • Each iteration only moves the middle edge by $1$, so it takes $2000$ iterations to reach $|f|=2000$. Why this step? The bottleneck is always the tiny middle edge; a careless chooser keeps threading it.
2. Edmonds-Karp (BFS shortest path): BFS finds the fewest-edge path first.
   • Path $s\to a\to t$ (length $2$), bottleneck $1000$. Push $1000$.
   • Path $s\to b\to t$ (length $2$), bottleneck $1000$. Push $1000$.
   • Done: $|f|=2000$ in $2$ augmentations — BFS never touches the middle edge. Why this step? Shortest paths avoid the useless detour, so the bound is $O(V{E}^2)$ independent of the $1000$s.

Verify: both reach max flow $|f|=2000$ (cut $S=\{s\}$: $c=1000+1000=2000$). Bad order: $2000$ iterations. Edmonds-Karp: $2$ iterations. Same answer, wildly different cost — that's why BFS path selection matters. ✔

Example 6 — limiting behaviour, huge capacities (Cell F)

1. (a) Max flow $=2C$. The two direct paths $s\to a\to t$ and $s\to b\to t$ each carry $C$; the middle edge is never needed. Cut $S=\{s\}$ gives $c=C+C=2C$. Why this step? The min cut is the two source edges; the middle edge $1$ contributes nothing to any forward $S\to T$ boundary that beats $2C$.
2. (b) Worst Ford-Fulkerson: the zig-zag order pushes $1$ unit per iteration → $2C=2\times 10^9$ iterations. This is $O(E\cdot |f^{\ast }|)$ — it scales with the capacity value. For irrational capacities the analogous construction may never terminate. Why this step? Shows the failure mode: value-dependent, and unbounded in the limit $C\to \infty$.
3. (b) Edmonds-Karp: still just $2$ augmentations (both length-$2$ direct paths), independent of $C$. Its bound $O(V{E}^2)$ has no $C$ in it. Why this step? This is the whole point of switching to BFS — the limit $C\to \infty$ leaves Edmonds-Karp untouched.

Verify: max flow $=2C=2\times 10^9$. FF worst iterations $=2C=2\times 10^9$; EK iterations $=2$. Confirms capacity-independence of Edmonds-Karp. ✔

Example 7 — word problem: build the graph (Cell G)

1. Model it. Add a super-source $s$: edges $s\to F_i$ with capacities $4,3,5$ (production limits). Middle edges $F_i\to D_j$ each capacity $2$. Depot edges $D_1\to T,D_2\to T$ each capacity $6$. Sink $=T$. Why this step? Every "at most $x$" becomes a capacity; a super-source turns "each factory produces some" into one flow value.
2. Bound 1 — production: $s$'s out-capacity $=4+3+5=12$.
3. Bound 2 — depot forwarding: total into $T$ is $6+6=12$.
4. Bound 3 — roads (the true bottleneck): each factory reaches the depots through only $2+2=4$ units of road, but more sharply: each depot receives from $3$ factories over roads of cap $2$, so at most $6$ enters each depot from the middle layer — total middle capacity into depots $=6\times$ ... let's cut cleanly. Take $S=\{s,F_1,F_2,F_3\}$, $T=\{D_1,D_2,T\}$. Forward edges are the six $F_i\to D_j$ roads, each cap $2$: $c(S,T)=6\times 2=12$. Why this step? We test the middle layer as a cut — it also gives $12$.
5. Can we achieve $12$? Each depot must forward $6$ (its cap) and receive $6$ over three cap-$2$ roads ($2+2+2=6$ ✔). Production must supply: $F_1$ sends $2+2=4$ ✔ (cap $4$), $F_2$ sends $2+1$... let's just balance: route each $F_i\to D_1$ and $F_i\to D_2$ at $2$ where possible. $F_1$: $2+2=4$. $F_2$: $2+1=3$. $F_3$: $2+3$? road cap is $2$, so $F_3$ sends $2+2=4\le 5$. Total into depots $=4+3+4=11$. Hmm — recheck. Why this step? We must verify a cut value is actually achievable, not just an upper bound.
6. Recount reachable: depot capacity forces $\le 6$ per depot. $D_1$ can receive $\le \min (6,2+2+2)=6$; likewise $D_2\le 6$. But each factory road is cap $2$, and $F_2$ produces only $3$, so $F_2$ contributes at most $3$ split as $2+1$. Max middle throughput $=\min (6,6)$ per depot but limited by production $4+3+5=12$ and roads. Achievable assignment: $F_1:2/2$, $F_2:2/1$, $F_3:2/2$ → $D_1$ gets $2+2+2=6$, $D_2$ gets $2+1+2=5$; total $=11$. Try $F_2:1/2$, $F_3:2/2$ → $D_1=2+1+2=5$, $D_2=2+2+2=6$, total $11$. The road+production structure caps us at $11$, not $12$. Why this step? The naive cut gave $12$, but a tighter cut exists. Find it.
7. Tighter cut: put $S=\{s,F_1,F_3\}$ and $T=\{F_2,D_1,D_2,t\}$. Forward edges: $s\to F_2$ (cap $3$), plus $F_1\to D_1,F_1\to D_2$ ($2+2$), $F_3\to D_1,F_3\to D_2$ ($2+2$) $=3+8=11$. Why this step? Cutting the low-production factory $F_2$ at the source edge ($3$) plus the four cap-$2$ roads of the two big factories gives $11$ — matching the achievable flow.

Verify: max flow $=11$. Achievable assignment above yields exactly $11$ into $T$ ($6+5$), and the cut $S=\{s,F_1,F_3\}$ has capacity $3+2+2+2+2=11$. Flow $=$ cut $\Rightarrow$ optimal. The roads-plus-$F_2$ bottleneck binds, not raw production. ✔

Example 8 — exam twist: node capacities & matching (Cell H)

1. (8a) Node-splitting trick. Replace $r$ by two copies $r_{\text{in}}\to r_{\text{out}}$ joined by an edge of capacity $=$ the node's limit ($3$). All incoming edges enter $r_{\text{in}}$, all outgoing leave $r_{\text{out}}$. Why this step? A raw flow network only limits edges; to limit a node you force all its traffic through one internal edge.
2. (8a) Solve: now $s\to r_{\text{in}}$ (5), $r_{\text{in}}\to r_{\text{out}}$ (3), $r_{\text{out}}\to t$ (5). The internal edge caps everything: max flow $=3$. Min cut $=\{s,r_{\text{in}}\}$ vs rest, capacity $3$. Why this step? Confirms the node limit now correctly bottlenecks the flow.
3. (8b) Matching-as-flow. Add super-source $s\to L_i$ (cap $1$ each — each worker takes one job), each allowed pair $L_i\to R_j$ (cap $1$), each $R_j\to t$ (cap $1$ — each job filled once). Max flow $=$ max matching size (see Bipartite Matching). Why this step? Capacity-$1$ edges make every unit of flow a chosen pair; conservation forbids reusing a worker or job.
4. (8b) Solve: $R_2$ is wanted by $L_1,L_2,L_3$ but has cap $1$ into $t$ — only one of them can use it. Best matching: $L_1-R_1$, $L_2-R_2$, $L_3-R_3$. Size $=3$. Why this step? Route around the $R_2$ bottleneck: give $R_1$ to $L_1$ and $R_3$ to $L_3$, freeing $R_2$ for $L_2$.

Verify: (8a) max flow $=3$ (the split-node edge). (8b) max matching $=3$, and the flow network achieves value $3$ with the three disjoint pairs. By König/max-flow-min-cut the min vertex cover also has size $3$. ✔ (This is Linear Programming Duality in disguise — matching vs cover.)

Flashcards