SCSA WACE 2022-style practice: Water flows from source S to sink T. Pipe capacities (litres/min) are S→ A = 10, S→ B = 8, A→ C = 6, A→ B = 3, B→ C = 9, C→ T = 12. (a) Find the capacity of the cut separating \S, A, B\ from \C, T\. (b) State the maximum flow from S to T and justify it.

A cut's capacity sums the forward edges crossing it. (a) Edges crossing from \S, A, B\ to \C, T\ are A→ C = 6 and B→ C = 9, so the cut capacity is 6 + 9 = 15 litres/min. (3 marks) (b) Test the cut at T: only C→ T = 12 enters T, giving a cut capacity of 12. The flow out of S is at most 10 + 8 = 18, but the bottleneck C→ T = 12 limits the flow. The minimum cut is 12, so by the maximum-flow minimum-cut theorem the maximum flow is 12 litres/min. (4 marks) Markers reward summing the forward edges of each cut and identifying the minimum cut as the maximum flow.

§-Syllabus dot point

WAMathematics ApplicationsSyllabus dot point

How much can flow from a source to a sink through a capacitated network?

Model flow in a directed network, find the maximum flow, and use the maximum-flow minimum-cut relationship.

How to model flow in a directed capacitated network, find the maximum flow from source to sink, identify cuts, and apply the maximum-flow minimum-cut theorem.

Generated by Claude Opus 4.88 min answerUpdated 2026-06-02

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section

What this dot point is asking
Flow networks
Cuts
The maximum-flow minimum-cut theorem
Finding the minimum cut systematically
Checking a proposed flow

What this dot point is asking

You must model flow in a directed network, find the maximum flow, identify cuts, and apply the maximum-flow minimum-cut theorem.

Flow networks

A flow network carries a quantity (water, traffic, data) along directed edges, each with a maximum capacity. Flow enters at the source and leaves at the sink.

Cuts

A cut partitions the vertices into two groups, one containing the source and the other the sink. The capacity of a cut is the sum of the capacities of the edges directed from the source side to the sink side (forward edges only; backward edges are ignored).

The maximum-flow minimum-cut theorem

To find the maximum flow by hand: identify several cuts, compute each cut's forward capacity, and the smallest of these is the maximum flow. The edge or edges forming the minimum cut are the bottleneck that limits the network.

Worked example

Finding the maximum flow

Traffic flows from $S$ to $T$ with capacities $S\to A = 7$ , $S\to B = 5$ , $A\to T = 4$ , $A\to B = 3$ , $B\to T = 8$ .

Step 1: Identify a systematic set of cuts to evaluate.

A cut partitions all vertices into a group containing $S$ and a group containing $T$ ; its capacity is the total of only the forward edges crossing from the source side to the sink side. We try three natural cuts to bracket the maximum flow: one near the source, one near the sink, and one isolating an intermediate vertex.

Step 2: Compute the capacity of each candidate cut.

The cut separating $\{S\}$ from $\{A, B, T\}$ contains the edges $S\to A = 7$ and $S\to B = 5$ , giving a capacity of $7 + 5 = 12$ . The cut separating $\{S, A, B\}$ from $\{T\}$ contains the edges $A\to T = 4$ and $B\to T = 8$ , giving a capacity of $4 + 8 = 12$ . The cut placing $A$ on the sink side with $\{S, B\}$ on the source side contains $S\to A = 7$ and $B\to T = 8$ , giving a capacity of $7 + 8 = 15$ .

Step 3: Identify the minimum cut.

The smallest capacity found across all candidate cuts is $12$ , achieved by both the source-side cut and the sink-side cut. No other partition produces a smaller value, so the minimum cut has capacity $12$ .

Step 4: Apply the theorem to state the maximum flow and verify it.

By the maximum-flow minimum-cut theorem, the maximum flow from $S$ to $T$ equals the minimum cut capacity, which is $12$ units. We can verify this by constructing a valid flow: route $7$ units through $A$ (with $4$ continuing to $T$ and $3$ crossing to $B$ ) and $5$ units directly from $S$ to $B$ . Then $B\to T$ carries $3 + 5 = 8$ and $A\to T$ carries $4$ , totalling $12$ units into $T$ , confirming that the capacity bound is achievable.

Finding the minimum cut systematically

For the small networks in this course, list the natural cuts and compute each one's forward capacity, then take the smallest. A reliable set of cuts to try is: the edges leaving the source, the edges entering the sink, and cuts that isolate each intermediate vertex on one side. The smallest of these forward-capacity totals is the minimum cut, and by the theorem it equals the maximum flow. The edges crossing that minimum cut are the bottleneck, and increasing only those capacities is the way to raise the maximum flow.

Checking a proposed flow

To confirm a flow is valid: check no edge exceeds its capacity, that flow is conserved at every intermediate vertex, and that the value out of the source equals the value into the sink. To confirm it is maximum, find a cut whose capacity equals the flow value; matching them proves optimality by the theorem.

Exam-style practice questions

Practice questions written in the style of SCSA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

WACE 20227 marksWater flows from source

S

to sink

T

. Pipe capacities (litres/min) are

S\to A = 10

S\to B = 8

A\to C = 6

A\to B = 3

B\to C = 9

C\to T = 12

. (a) Find the capacity of the cut separating

\{S, A, B\}

from

\{C, T\}

. (b) State the maximum flow from

S

T

and justify it.

Show worked answer →

A cut's capacity sums the forward edges crossing it.

(a) Edges crossing from $\{S, A, B\}$ to $\{C, T\}$ are $A\to C = 6$ and $B\to C = 9$ , so the cut capacity is $6 + 9 = 15$ litres/min. (3 marks)

(b) Test the cut at $T$ : only $C\to T = 12$ enters $T$ , giving a cut capacity of $12$ . The flow out of $S$ is at most $10 + 8 = 18$ , but the bottleneck $C\to T = 12$ limits the flow. The minimum cut is $12$ , so by the maximum-flow minimum-cut theorem the maximum flow is $12$ litres/min. (4 marks)

Markers reward summing the forward edges of each cut and identifying the minimum cut as the maximum flow.

WACE 20244 marksState the maximum-flow minimum-cut theorem and explain why a cut gives an upper bound on the flow through a network.

Show worked answer →

The theorem equates the largest flow with the smallest cut.

The maximum-flow minimum-cut theorem states that the maximum flow from source to sink equals the capacity of the minimum cut (the cut with the smallest total forward capacity). (2 marks)

A cut separates the source from the sink, so every unit of flow must cross it on some forward edge. The total flow can therefore never exceed the sum of the forward capacities of the cut, making each cut an upper bound; the smallest such bound is the maximum flow. (2 marks)

Markers reward stating the theorem and the "all flow must cross the cut" upper-bound argument.