Year 12 General Mathematics: Flow networks, cuts and maximum flow

A flow network is a directed graph where each edge has a capacity: the most that can pass along it per unit of time. Everything enters at one vertex and leaves at another, and the question is almost always the same — how much can get from one end to the other at once?

Maximum-flow minimum-cut theorem. The largest possible flow from the source to the sink equals the capacity of the smallest cut.

maximum flow = min_{all cuts} capacity of the cut

So you never have to hunt for the flow by trial and error. Find the weakest cut, and you have the answer.

The network

A school farm pumps water from a bore at S to its sports fields at Z. Capacities are in litres per minute. Two candidate cuts are drawn as dashed curves.

Water flow capacities in L/min across the irrigation network.

Step 1: name the source and the sink

The source is the vertex where all the flow starts — edges leave it and none arrive. Here that is S, the bore.

The sink is where all the flow ends — edges arrive and none leave. Here that is Z, the sports fields.

Step 2: work out the capacity of a cut

A cut splits the vertices into two groups: one holding the source, one holding the sink. Its capacity is the total capacity of the edges crossing it in the direction source-side → sink-side.

An edge crossing backwards — from the sink side to the source side — contributes nothing. It cannot carry water away from the sink. This is the single most common place to drop marks.

Cut (a)

Cut (a) puts S on its own. All four edges leaving it cross forwards.

capacity of cut (a) = \underset{S→P}{35} + \underset{S→Q}{25} + \underset{S→R}{12} + \underset{S→W}{20} = 92 L/min

Cut (b)

Cut (b) leaves S, P, Q, R, T and W on the source side, with U, V, M and Z on the sink side. Seven edges cross the dashed curve. Only six of them count.

Edges crossing cut (b)
Edge	Capacity	Direction across the cut	Counts?
T → V	45	source side → sink side	Yes
Q → U	16	source side → sink side	Yes
R → U	14	source side → sink side	Yes
R → Z	12	source side → sink side	Yes
W → U	9	source side → sink side	Yes
W → M	16	source side → sink side	Yes
U → T	15	sink side → source side	No — points backwards

capacity of cut (b) = 45 + 16 + 14 + 12 + 9 + 16 = 112 L/min

Step 3: find the maximum flow

Neither drawn cut is the smallest, and that is the point of the exercise. Cutting just after P is tighter, because P's only way onward is the 24 pipe.

capacity = \underset{S→Q}{25} + \underset{S→R}{12} + \underset{S→W}{20} + \underset{P→T}{24} = 81 L/min

No cut is smaller than 81, so the maximum flow is 81 L/min.

A flow that reaches it: send 24 along S→P→T, 25 into Q, 12 into R and 20 into W. From W, 9 goes to U and 16 to M; M passes 8 straight to Z and 8 on to V. Into Z altogether: 81 L/min.

Step 4: decide what to upgrade

Only the pipes on the minimum cut hold the flow back. Those are S–Q (25), S–R (12), S–W (20) and P–T (24).

Why widening U–V would achieve nothing. The 20 pipe from U to V is not on the minimum cut. Enlarge it and the cut through S–Q, S–R and S–W and P–T is still only 81, so the flow is still 81. Money spent anywhere but the bottleneck buys nothing.

Step 5: how far is an upgrade worth taking?

Suppose the budget stretches to one pipe, and P–T is chosen. Raising it lifts every cut that contains it, so the flow rises with it — but only until a different cut becomes the smallest. The next one to bind is the pair of pipes that actually reach Z:

\underset{V→Z}{70} + \underset{R→Z}{12} + \underset{M→Z}{8} = 90 L/min

So the flow can climb from 81 to at most 90, a gain of 9, and that needs P–T taken from 24 up to 33.

largest useful increase = 33 - 24 = 9 L/min

Beyond 33 the extra capacity is stranded: the water cannot leave through Z's three feeding pipes any faster. The new maximum flow is 90 L/min.

Common mistakes

Counting an edge that crosses the cut backwards. In cut (b) the 15 on U→T is tempting and wrong.
Assuming a cut drawn on the paper is the minimum. Cuts (a) and (b) are 92 and 112; the real bottleneck is 81 and is not drawn at all.
Adding the capacities leaving the source and calling it the maximum flow. That is one cut, and rarely the smallest.
Upgrading a pipe that is not on the minimum cut.
Upgrading one pipe without limit, when another cut takes over as the bottleneck.