Flow Networks - TCE Mathematics Applications (Tasmania)
“Determine the maximum flow through a network using the maximum-flow minimum-cut theorem.”
You must model a network with a source, a sink, and edge capacities, then find the maximum flow from source to sink by finding the minimum cut, since the maximum-flow minimum-cut theorem says these two numbers are always equal.
What this dot point is asking
Flow networks model anything that moves through a capacity-limited system: water through pipes, traffic through roads, or data through cables. Each edge can carry only so much, and the question is how much can get from start to end overall.
The source is where flow originates and the sink is where it ends. Each directed edge has a capacity, the maximum it can carry. A valid flow never exceeds any edge capacity, and at every other vertex the flow in equals the flow out.
Cuts
A cut divides the network into two groups of vertices, one containing the source and the other containing the sink, by cutting through some edges. The capacity of the cut is the total capacity of the edges that go from the source side to the sink side.
The maximum possible flow from source to sink equals the capacity of the minimum cut, the cut with the smallest total capacity. To find the maximum flow, find the cheapest place to sever the network so that source and sink are separated.
Only edges pointing from the source side to the sink side count toward a cut's capacity. Edges pointing back the other way are not added in, because they do not carry flow toward the sink across that division.
Water flows from source S to sink T. The pipes and capacities are: S-A 6, S-B 4, A-T 3, B-T 5, A-B 2.
Try some cuts
Cut isolating S only: edges S-A (6) and S-B (4), capacity .
Cut isolating T only: edges A-T (3) and B-T (5), capacity .
A cut separating {S, A} from {B, T}: edges A-T (3), A-B (2) and S-B (4), capacity .
Take the minimum
The smallest cut capacity found is 8 (isolating T). By the theorem the maximum flow is 8 units, limited by the two pipes feeding the sink.
Why the minimum cut limits the flow
No flow can cross a cut faster than the cut's total capacity, because every drop reaching the sink must pass through the cut edges. So the smallest cut is the tightest bottleneck, and it caps the whole network. Finding it gives the maximum flow without tracing every individual route.
Often the minimum cut is the set of edges leaving the source or the set entering the sink. Compute those two cuts first; the smaller of them is frequently the answer, and any internal cut you test only needs to beat it.
A network feeds the sink T through just two pipes of capacity 3 and 5. Whatever the capacities upstream, no more than units can ever reach T.
Conclude
The cut around T has capacity 8, so the maximum flow cannot exceed 8 regardless of how generous the earlier pipes are. The narrowest point of the system controls the total.
Reporting the answer
State the minimum cut you found, list its edges and their capacities, and give the maximum flow as that cut's total. Interpreting it in context, for example litres per minute, shows you understand the result rather than just the arithmetic.
When computing a cut's capacity, only count edges crossing from the source side to the sink side. An edge running from the sink side back to the source side does not add to the cut. Including it inflates the capacity and can make you miss the true minimum cut.
Counting a cut's capacity correctly
The single skill examiners test most is counting a cut's capacity. Draw a line that separates the source side from the sink side, then add only the capacities of edges that cross from the source side to the sink side. Edges that run back the other way, from the sink side to the source side, contribute nothing to that cut. A cut may slice through edges anywhere in the network, not just those at the source or sink, so be systematic about which side each endpoint lies on before deciding whether an edge counts.
Using the network S-A 6, S-B 4, A-T 3, B-T 5, A-B 2, take the cut that puts {S, B} on the source side and {A, T} on the sink side.
Identify crossing forward edges
S-A (6) crosses from source side to sink side: count it. B-T (5) crosses: count it. A-B (2) runs from A (sink side) to B (source side), so it is a back edge: do not count it. S-B is internal to the source side.
Add the forward capacities
Capacity .
This cut has capacity 11, larger than the minimum cut of 8 found earlier, so it does not limit the flow. Only the smallest cut sets the maximum flow.
Improving the flow
Once you know the minimum cut, you also know how to increase the maximum flow: enlarge a bottleneck edge that lies on the minimum cut. Upgrading an edge that is not on the minimum cut achieves nothing, because the bottleneck is elsewhere. This is why TASC questions that ask which pipes to upgrade are really asking you to name the edges crossed by the minimum cut.
A complete answer identifies the source and sink, tests sensible cuts, counts each cut by adding only forward-crossing capacities, applies the maximum-flow minimum-cut theorem to set the maximum flow equal to the minimum cut, and states that flow in the units of the problem.