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

Back to Graph theory tutorials

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?

Work through the sections in order, then try the linked Year 12 skill quizzes after each section.

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.

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.

Cut (a)

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

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.

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.

No cut is smaller than 81, so the maximum flow is 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).

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:

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.

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.