Maximum Flow - Minimum Cut
Master the maximum-flow minimum-cut theorem for NSW Year 12 Mathematics Standard 2. You learn that the greatest flow from a source \(S\) to a sink \(T\) in a directed network equals the capacity of the minimum cut — the smallest set of edges that separates them.
This topic shows you how to find the maximum flow by locating the minimum cut, identify the bottleneck edges, work out the effect of increasing or reducing an edge capacity, and check whether the flow meets a stated demand — a core Standard 2 networks skill for water, power, traffic, data and freight problems.
Theory
The maximum-flow minimum-cut theorem states that the greatest flow through a directed network equals the capacity of its smallest cut. This Year 12 Standard 2 (NSW) guide shows how to find the minimum cut to get the maximum flow, name the bottleneck edges, judge the effect of changing an edge capacity, and decide whether a network meets demand.
In a directed network with a single source \(S\) and a single sink \(T\), each edge has a capacity — the most it can carry. The flow is how much actually travels from \(S\) to \(T\).
A cut is a division of the nodes that puts \(S\) on one side and \(T\) on the other. Its capacity is the sum of the capacities of the edges that cross from the source side to the sink side. Because every unit of flow must cross every cut, no flow can beat the smallest cut.
The maximum-flow minimum-cut theorem makes this exact: the maximum flow from \(S\) to \(T\) equals the capacity of the minimum cut. This Year 12 Standard 2 (NSW) skill lets you find the maximum flow, spot the bottleneck edges, and check whether a network meets demand.
The theorem links the two quantities exactly:
The capacity of any single cut is the sum of the capacities of the edges that cross it in the forward direction:
How to find the maximum flow
- Mark the source \(S\) and sink \(T\).
- List cuts that separate \(S\) from \(T\) — start with the edges leaving \(S\) and the edges entering \(T\).
- Add capacities for each cut, counting only edges crossing from the source side to the sink side.
- Choose the smallest cut — this is the minimum cut. By the theorem the maximum flow equals its capacity.
- Interpret: name the bottleneck edges, or compare the maximum flow with a stated demand to decide whether it is met.
Test cuts and take the smallest — that capacity is the maximum flow.
| \(\{SA, SB\}\) | \(:\) | \(4+6=10\) |
| \(\{AT, BT\}\) | \(:\) | \(7+8=15\) |
| \(\text{min cut}\) | \(=\) | \(10\) |
The minimum cut is \(\{SA, SB\}\), so the maximum flow is 10 L/s.
Compare cuts across the network; the smallest names the bottleneck.
| \(\{SA, SB\}\) | \(:\) | \(7+5=12\) |
| \(\{AC, BC, BT\}\) | \(:\) | \(6+4+3=13\) |
| \(\{CT, BT\}\) | \(:\) | \(8+3=11\) |
| \(\text{min cut}\) | \(=\) | \(11\) |
The minimum cut is \(\{CT, BT\}\), so the maximum flow is 11 Gb/s.
Recompute the minimum cut after the change — the bottleneck may move.
| \(\text{before } \{AC, BT\}\) | \(:\) | \(5+4=9\) |
| \(\text{after } \{AC, BT\}\) | \(:\) | \(8+4=12\) |
| \(\{CT, BT\}\) | \(:\) | \(7+4=11\) |
| \(\text{new min cut}\) | \(=\) | \(11\) |
The flow rises from \(9\) to 11 people/min — not \(12\), because \(\{CT, BT\}\) is now the bottleneck.
Find the maximum flow, then compare it with the demand.
| \(\{SA, SB\}\) | \(:\) | \(9+7=16\) |
| \(\{CT, DT\}\) | \(:\) | \(8+4=12\) |
| \(\text{max flow}\) | \(=\) | \(12\) |
| \(12\) | \(\ge\) | \(10\) |
Yes — the maximum flow of \(12\) kL/h exceeds the \(10\) kL/h demand.
Common pitfalls
Frequently asked questions
What is the maximum-flow minimum-cut theorem?
It says that in a directed network with one source and one sink, the maximum flow you can send from the source to the sink is exactly equal to the capacity of the minimum cut. So finding the smallest cut immediately gives you the greatest possible flow.
What is a cut and how do I find its capacity?
A cut splits the network into two groups, one containing the source and the other containing the sink. Its capacity is the sum of the capacities of the edges that cross from the source side to the sink side. Only forward-crossing edges are counted; edges pointing back are ignored.
How do I find the maximum flow without trial and error?
List the cuts that separate the source from the sink, starting with the edges leaving the source and the edges entering the sink. Add the forward capacities of each cut and pick the smallest. By the theorem that smallest cut capacity is the maximum flow.
Which edges are the bottleneck?
The edges that form the minimum cut are the bottleneck. Together their capacities add up to the maximum flow, so they are the links that limit the whole network. To raise the flow you must increase the capacity of a minimum-cut edge.
If I make one pipe bigger, does the maximum flow always increase?
No. Increasing an edge that is not on the minimum cut has no effect, because a different cut still limits the flow. Even upgrading a bottleneck edge only helps until another cut becomes the new smallest one.
How do I check whether a network meets demand?
Find the maximum flow using the minimum cut, then compare it with the required demand. If the maximum flow is greater than or equal to the demand, the network meets it; if it is less, the demand cannot be satisfied without upgrading a bottleneck edge.