Flow networks
A water company pumps water from a reservoir to a city through a network of pipes. Each pipe can carry only so many litres per second, and water flows in one direction only. How much water per second can reach the city?
Definition
A flow network is a directed graph with a source s, a sink t, and a capacity on every edge: the most it can carry.
The same picture describes many situations. Roads have a capacity in cars per hour. Internet links have a capacity in megabits per second. A supply chain's lorries carry so many tonnes per day. The question is always the same: what's the most that can get from s to t?
The two rules of flow
A flow says how much is actually sent along each edge. We write it as "flow/capacity", like 7/9. To be valid, it must obey two rules:
- Capacity rule: on every edge, 0 ≤ flow ≤ capacity. You can't push 12 litres through a 9-litre pipe.
- Conservation rule: at every junction except s and t, what flows in equals what flows out. Water doesn't appear or vanish inside the pipes.
The value of a flow is the total amount leaving s, which by conservation equals the total arriving at t. The maximum flow problem asks for a valid flow with the largest possible value.
Example: checking a junction
At a junction, 5 units arrive along one pipe and 3 along another. Two pipes leave it, with capacities 4 and 6. Conservation says 8 units must leave. Valid splits include 4 + 4 or 2 + 6, but not 5 + 3 (the first pipe holds only 4).
Why greedy gets stuck
An obvious strategy: find any route from s to t that still has spare capacity, push as much as you can along it, and repeat. Watch what happens on a small network:
Swipe or scroll sideways to step through.
The network
Each pipe is labelled flow/capacity. Nothing is flowing yet. The source s can send at most 2 + 1 = 3 units, and the sink t can take in at most 1 + 2 = 3.
Greedy: push 2 along s → a → b → t
The path s → a → b → t can carry 2 (the smallest capacity on it). Pipes that are now full are teal. Total flow: 2.
Stuck?
Every forward path from s to t now hits a full pipe: s → a is full, and b → t is full. A greedy method stops here with 2. But 3 is possible.
Undo some flow: s → b ⇢ a → t
Send 1 unit s → b, then go backwards along a → b, cancelling 1 unit that a was sending to b. That frees a to send 1 unit straight to t.
Maximum flow: 3
Now a sends 1 to b and 1 to t; b passes on 2. Every junction balances, 3 units arrive at t, and both pipes into t are full: this is the maximum.
full pipeaugmenting path
The greedy method chose a bad first route. Sending 2 units through the middle pipe a → b used up both s → a and b → t, and no fresh route was left. The fix in frame 4 is the key idea of the whole unit: a better flow can be found by partly undoing an earlier decision.
Augmenting paths and the residual network
To spot such fixes systematically, we look at what could still change on each edge, given the current flow:
- An edge u → v with flow 3 and capacity 5 has 2 units of spare capacity forwards: we could send up to 2 more from u to v.
- It also has 3 units we could cancel. Cancelling flow on u → v has the same effect as sending flow from v back towards u.
The residual network records these possibilities: a forward edge for each bit of spare capacity and a backward edge for each bit of cancellable flow. An augmenting path is any route from s to t in the residual network. Pushing flow along it increases the total, using forward edges normally and backward edges by cancelling.
This is exactly the same idea as the augmenting paths in Unit 7, where flipping an alternating path let one pair be broken up so that two new pairs could form.
The Ford–Fulkerson method
Lester Ford and Delbert Fulkerson put this together in 1956:
- Start with zero flow everywhere.
- Find an augmenting path from s to t in the residual network.
- Push as much as possible along it: the smallest residual capacity on the path, called the bottleneck.
- Repeat until no augmenting path exists.
Choosing the augmenting path matters for speed. If you always pick a path with the fewest edges, found by breadth-first search (Unit 4), the method is called the Edmonds–Karp algorithm (1972). It's guaranteed to finish quickly, in time that depends only on the size of the network and not on how large the capacities are.
A neat bonus
If all capacities are whole numbers, every bottleneck is a whole number too, so Ford–Fulkerson finds a maximum flow in which every edge carries a whole number. This "integrality" is what makes flows useful for problems like matching, where you can't send half a worker to a job.
Cuts: finding the bottleneck
How would you prove that a flow is the largest possible? Draw a line that separates the source from the sink.
Definition
An s–t cut splits the vertices into two groups: S, containing s, and T, containing t. Its capacity is the total capacity of the edges going from S to T. Edges going backwards, from T to S, don't count.
Every unit of flow has to cross from S to T at some point. So no flow can be bigger than any cut. If the city is only reachable through pipes totalling 15 litres per second, no clever routing can deliver 16.
Here are some cuts of the pipe network:
| Source side S | Edges crossing from S to T | Capacity |
|---|---|---|
| {s} | s→a (12), s→b (8) | 20 |
| {s, a} | s→b (8), a→b (4), a→c (8) | 20 |
| {s, a, b} | a→c (8), b→d (9) | 17 |
| {s, a, b, c, d} | c→t (10), d→t (7) | 17 |
| {s, a, b, d} | a→c (8), d→t (7) | 15 |
The smallest is 15. So no flow can deliver more than 15 litres per second. And here is a flow that delivers exactly 15:
Check the flow: 8 + 7 = 15 leaves s; at a, 8 in and 8 out; at b, 7 in and 7 out; at c, 8 in and 8 out; at d, 7 in and 7 out; and 8 + 7 = 15 arrives at t. Since 15 is also a cut's capacity, nothing better is possible. The flow and the cut certify each other.
The max-flow min-cut theorem
That wasn't a lucky coincidence. It always happens:
Max-flow min-cut theorem (Ford and Fulkerson, 1956)
In any flow network, the value of a maximum flow equals the capacity of a minimum cut.
Why it's true. Run Ford–Fulkerson until no augmenting path is left. Let S be all the vertices you can still reach from s in the residual network; t isn't among them, or there'd be another augmenting path. Every edge from S to the rest must be completely full (otherwise its far end would be reachable), and every edge coming back into S must be empty (otherwise cancelling its flow would reach further). So the flow crossing the cut is exactly the cut's capacity. That cut is a minimum cut and the flow is a maximum flow.
Ford–Fulkerson therefore gives two answers at once: the best flow, and a bottleneck that proves nothing better exists. If you want to increase the network's capacity, the minimum cut tells you exactly which pipes to upgrade. Widening any other pipe won't help.
Try it. In the pipe network, the company can widen one pipe by 5 litres per second. Which pipe should it choose, and what's the new maximum flow?
Show answer
Widening a pipe off the minimum cut won't help, so choose a → c or d → t. If d → t becomes 12, the cut {s, a, b, d} becomes 8 + 12 = 20, and now the smallest cut is {s, a, b}, with a → c (8) + b → d (9) = 17. The new maximum is 17. Widening a → c to 13 also gives 17: cut {s, a, b, d} becomes 13 + 7 = 20, and {s, a, b} becomes 13 + 9 = 22, leaving {s, a, b, c, d} = 17 as the smallest.
Flow in disguise
Many problems that don't look like pipes at all can be turned into flow problems:
- Matching (Unit 7). Add a source joined to every worker and a sink joined from every job, all with capacity 1, and give each worker–job edge capacity 1. A maximum flow is a maximum matching, and the min-cut theorem becomes König's theorem.
- Robust networks (Unit 2). Give every edge capacity 1. The maximum flow from s to t counts the most routes that share no edges, and the minimum cut is the fewest links an attacker must cut to separate them: Menger's theorem again.
- Evacuation planning. Roads have capacities in people per minute; how many can reach safety in time? Adding a copy of the network for every minute turns the question into a maximum flow.
- Separating foreground from background in photos. Each pixel is a vertex, with edges whose capacities say how strongly neighbouring pixels belong together. A minimum cut separates the object from the background along the "cheapest" boundary. This technique has been widely used in image editing and medical scans.
- Sports elimination. Whether a team can still finish top of a league, given the remaining fixtures, can be decided with a maximum flow, sometimes long before the newspapers notice that a team is out.
Practice set
Mixed questions covering the whole unit. Try each one before opening the answer.
1. At a junction, flows in are 4 and 6. Two pipes leave, with capacities 3 and 5. Can the flow be valid?
Show answer
No. 10 units arrive, but at most 3 + 5 = 8 can leave. Conservation would be broken, so the incoming flows must be reduced.
2. A network's source has outgoing pipes with capacities 7, 4 and 9. What's the most the maximum flow could possibly be?
Show answer
The cut {s} has capacity 7 + 4 + 9 = 20, so the flow can't exceed 20. It might be less, if there's a narrower bottleneck elsewhere.
3. An edge u → v currently carries 6 units and has capacity 10. What edges does it create in the residual network?
Show answer
A forward edge u → v with residual capacity 4 (spare room), and a backward edge v → u with residual capacity 6 (flow that could be cancelled).
4. Someone finds a flow of value 12 and a cut of capacity 12 in the same network. What can you conclude?
Show answer
The flow is a maximum flow and the cut is a minimum cut. Any flow is at most any cut, so a flow and a cut with equal values must both be optimal.
5. In the pipe network, the pipe a → b (capacity 4) bursts and must be closed. Does the maximum flow change?
Show answer
No. The maximum flow shown sends nothing along a → b, so it's still valid without that pipe, and the cut {s, a, b, d} still has capacity 15. The maximum stays at 15.
6. Explain why the greedy method in the small example got stuck at 2, using the idea of a cut.
Show answer
It didn't hit a real bottleneck: the minimum cut is 3 (for example, the two pipes into t: 1 + 2). Greedy got stuck because it can't undo earlier choices. Only when backward edges are allowed does every "stuck" state match a real cut.
Summary and glossary
- A flow network has a source, a sink and edge capacities. A valid flow respects capacities and is conserved at every junction.
- Greedily pushing flow can get stuck. Augmenting paths in the residual network may run backwards, cancelling earlier flow.
- The Ford–Fulkerson method repeats augmenting paths until none remain; the Edmonds–Karp version uses BFS and is always fast.
- A cut separates source from sink. No flow can exceed any cut.
- Max-flow min-cut: the largest flow equals the smallest cut. The minimum cut shows exactly where the bottleneck is.
- Matching, connectivity, evacuation and image segmentation are all flow problems in disguise.
- Flow network
- A directed graph with a source, a sink and capacities on edges.
- Source / sink
- Where the flow starts / where it ends.
- Capacity
- The most an edge can carry.
- Conservation
- At each inner vertex, flow in equals flow out.
- Residual network
- The spare capacity forwards and cancellable flow backwards, given the current flow.
- Augmenting path
- A source-to-sink route in the residual network.
- Bottleneck
- The smallest residual capacity along an augmenting path.
- Cut
- A split of the vertices with the source on one side and the sink on the other.
- Minimum cut
- A cut with the smallest total capacity of forward-crossing edges.