Network Flows
Interactive visualizations for Chapter 11 of the Ricerca Operativa notes
The Flow Network
We work with a directed flow network of 5 nodes throughout this chapter.
- Nodes: s, a, b, c, t
- Arcs (with capacities): s→a(5), s→b(6), a→b(3), a→c(4), b→t(7), c→t(3)
- Max flow = 10 (min cut: {s,a,b,c} | {t}, capacity = 7+3 = 10)
Ford–Fulkerson: Augmenting Paths
The Ford–Fulkerson algorithm finds a maximum flow by repeatedly discovering augmenting paths in the residual graph and pushing flow along them. Here we use BFS (Edmonds–Karp) to pick the shortest augmenting path at each iteration.
Starting point: all flows = 0, flow value = 0.
| Aug. | Path | Bottleneck | Flow value after |
|---|---|---|---|
| 1 | s → a → c → t | min(5, 4, 3) = 3 | 3 |
| 2 | s → a → b → t | min(2, 3, 7) = 2 | 5 |
| 3 | s → b → t | min(6, 5) = 5 | 10 |
After augmentation 3 the residual graph contains no path from s to t → max flow = 10.
Max Flow = 10
After the three augmentation steps no further augmenting path exists. The final flow assignment is:
| Arc | Flow / Capacity | Saturated? |
|---|---|---|
| s → a | 5 / 5 | yes |
| s → b | 5 / 6 | no |
| a → b | 2 / 3 | no |
| a → c | 3 / 4 | no |
| b → t | 7 / 7 | yes |
| c → t | 3 / 3 | yes |
Flow conservation at every intermediate node:
- Node a: in = 5, out = 2 + 3 = 5 ✓
- Node b: in = 5 + 2 = 7, out = 7 ✓
- Node c: in = 3, out = 3 ✓
Total flow value = flow leaving s = 5 + 5 = 10.
The Min Cut
The Max-Flow Min-Cut theorem states that the value of the maximum flow equals the capacity of the minimum cut.
For our network the minimum cut is:
- S = {s, a, b, c}
- T = {t}
- Arcs crossing the cut (from S to T): b→t (cap 7) and c→t (cap 3)
- Cut capacity = 7 + 3 = 10 = max flow ✓
The dashed red line separates S from T. The two arcs crossing the cut — b→t and c→t — are both saturated, which is exactly what the Max-Flow Min-Cut theorem predicts at optimality.
Residual Graph
After reaching max flow, we inspect the residual graph to confirm no augmenting path remains.
For each arc (u, v) with capacity cap and flow f:
- Forward residual arc u→v with capacity cap − f (only if > 0)
- Backward residual arc v→u with capacity f (only if > 0, represents “undo” potential)
Reading the residual graph
The residual arcs present after max flow are:
| Residual arc | Capacity | Meaning |
|---|---|---|
| s → b (fwd) | 1 | 1 unit unused on s→b |
| a → b (fwd) | 1 | 1 unit unused on a→b |
| a → c (fwd) | 1 | 1 unit unused on a→c |
| a → s (bwd) | 5 | can undo up to 5 units on s→a |
| b → s (bwd) | 5 | can undo up to 5 units on s→b |
| b → a (bwd) | 2 | can undo up to 2 units on a→b |
| b → t (fwd) | — | saturated; no forward residual |
| t → b (bwd) | 7 | can undo up to 7 units on b→t |
| c → a (bwd) | 3 | can undo up to 3 units on a→c |
| t → c (bwd) | 3 | can undo up to 3 units on c→t |
To reach t from s in the residual graph we would need to traverse backward arcs that ultimately go to t — but every path leads to a dead end before t. In particular the only “new” forward arc is s→b(1), yet b→t is saturated (no forward residual) and no alternative route to t has residual capacity. This confirms no augmenting path exists and the flow of 10 is maximum.