Coaching Centre
Cuts and the max-flow min-cut theorem
Cuts in a flow network, finding the capacity of a cut (forward edges only), the maximum-flow minimum-cut theorem, and using it to judge upgrades and whether a network can meet demand.
In 9D you built a flow up path by path. But how do you know you've reached the maximum, rather than just run out of ideas? Cuts answer that. They also tell a water authority exactly which pipe to upgrade, and which upgrades would be money down the drain.
What is a cut?
A cut is a set of edges that, if removed, stops all flow from the source to the sink. Draw it as a line through the network that separates the vertices into two groups: the source side (containing S) and the sink side (containing T).
The capacity of a cut is the total capacity of the edges it crosses from the source side to the sink side. Edges that cross the other way, from the sink side back to the source side, are not counted: nothing travelling from S to T needs them to get across the line.
For the network in 9D (S→A $5$, S→B $4$, A→B $2$, A→T $3$, B→T $6$), find the capacity of every cut.
The maximum-flow minimum-cut theorem
Why? Every drop of water going from S to T must cross every cut. So no flow can be bigger than any cut's capacity, and in particular not bigger than the smallest. The theorem says that the best flow always reaches that limit exactly: the minimum cut is the bottleneck of the whole network.
In practice: find a flow by sending it along paths, find a cut with the same value, and you have proved both are optimal. If they don't match, keep looking. Either the flow can go higher or there is a smaller cut.
This is the water network from 9D. Click pipes to cut them. Cut S→A and S→B first and read the capacity. Then clear and cut A→C and B→D. Why does C→B not count, even though it crosses between the two sides?
Press Show the minimum cut, then upgrade B→D one step at a time. Does the network meet the town's demand of $15$ ML/day? What happens to the minimum cut when you upgrade B→D past $9$?
The water network has S→A $9$, S→B $7$, A→B $3$, A→C $6$, C→B $2$, B→D $8$, C→T $7$, D→T $9$ (ML/day). Find the capacity of the cut with source side $\{S, A, B\}$, and show it equals the maximum flow.
Meeting demand and choosing upgrades
If a town needs more than the maximum flow, the network can't meet demand, however the water is routed. To raise the maximum flow you must raise the capacity of every minimum cut, so the upgrade has to be on an edge in the minimum cut. Upgrading any other pipe changes nothing.
The town supplied by the network in Example 2 needs $15$ ML/day. Can the network meet this? If not, which single pipe should be upgraded, and by how much?
Your turn
Traffic flows S→A $10$, S→B $8$, A→C $4$, A→D $7$, B→D $5$, C→T $9$, D→T $9$ (cars per minute). Find the capacity of the cut with source side $\{S, A, B, D\}$, and say whether it is the minimum cut.
Show the working
Edges from $\{S, A, B, D\}$ to $\{C, T\}$: A→C $4$ and D→T $9$. Capacity $= 13$. A flow of $13$ exists (S–A–C–T $4$, S–A–D–T $6$, S–B–D–T $3$), so by the theorem this is the minimum cut and the maximum flow is $13$.
A cut in a flow network is:
A cut separates the source from the sink. Removing its edges leaves no route from S to T.
When finding the capacity of a cut, you add the capacities of:
Only forward edges carry flow across the cut towards the sink. Backward edges are not counted.
A cut crosses four edges. Three go from the source side to the sink side, with capacities $7$, $6$ and $3$. One goes from the sink side to the source side, with capacity $4$. Find the capacity of the cut.
Count only the forward edges: $7 + 6 + 3 = 16$. The backward edge of $4$ is not counted.
The maximum-flow minimum-cut theorem says:
The smallest cut is the bottleneck of the network, and the best possible flow exactly fills it.
For the network S→A $5$, S→B $4$, A→B $2$, A→T $3$, B→T $6$, find the capacity of the cut with source side $\{S, B\}$.
Forward edges from $\{S, B\}$ to $\{A, T\}$: S→A $5$ and B→T $6$. A→B goes from the sink side to the source side, so it is not counted. Capacity $= 11$.
The minimum cut of a network has capacity $20$. What is the maximum flow?
By the maximum-flow minimum-cut theorem, the maximum flow is $20$.
A suburb needs $25$ ML/day. The minimum cut of its supply network is $22$ ML/day. By how much does supply fall short?
Maximum flow $= 22$. Shortfall $= 25 - 22 = 3$ ML/day.
Exam style: Find the maximum flow for S→A $10$, S→B $8$, A→C $4$, A→D $7$, B→D $5$, C→T $9$, D→T $9$, using the minimum cut.
Some cuts: $\{S\}$: $18$. $\{S, A, B\}$: A→C $+$ A→D $+$ B→D $= 16$. $\{S, A, B, D\}$: A→C $+$ D→T $= 4 + 9 = 13$. $\{S, A, B, C, D\}$: $18$. The smallest is $13$, and the flow S–A–C–T $4$, S–A–D–T $6$, S–B–D–T $3$ reaches $13$. Maximum flow $= 13$.
Exam style: In the previous network, only D→T can be widened. What is the smallest capacity of D→T that lets the network carry $15$ cars per minute?
The cut A→C $+$ D→T needs $4 + x \ge 15$, so $x \ge 11$. Check the other cuts at $x = 11$: $\{S, B\}$: S→A $+$ B→D $= 15$; $\{S, A, B\}$: $16$; $\{S\}$: $18$. None is below $15$, so D→T must carry at least $11$.