QLDGeneral MathematicsSyllabus dot point

Topic 3: Networks and decision mathematics - how much can flow from a source to a sink through a capacitated network?

Model a flow problem on a directed network with edge capacities, find the maximum flow from source to sink by inspection, identify cuts and their capacities, and use the maximum-flow minimum-cut theorem to confirm the maximum flow

A focused answer to the QCE General Mathematics Unit 4 dot point on flow networks. Covers modelling flow on a directed capacitated network, finding maximum flow by inspection, defining a cut and its capacity, and the maximum-flow minimum-cut theorem to confirm the answer, with arithmetic-verified worked examples for IA3 and the external assessment.

Generated by Claude Opus 4.76 min answerUpdated 2026-05-29

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

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

What this dot point is asking

QCAA wants you to work out the greatest amount of something (water, traffic, data) that can pass from a source to a sink through a network where each edge has a maximum capacity. You model the situation as a directed network, find the maximum flow, and verify it by finding the minimum cut, because the maximum-flow minimum-cut theorem guarantees these two numbers are equal. This is a distinct sub-topic of Unit 4 Topic 3 and a regular extended-response item in IA3 and the external assessment.

The answer

Flow networks

A flow network is a directed graph with a single source (where flow starts) and a single sink (where flow ends). Each edge has a capacity, the maximum flow it can carry in the direction of its arrow. The flow along any edge cannot exceed its capacity, and at every intermediate vertex the flow in must equal the flow out (nothing is created or stored).

Maximum flow by inspection

The maximum flow is the largest total that can travel from source to sink while respecting every capacity. On a small network you find it by inspection: trace paths from source to sink, send as much as the smallest capacity on each path allows, reduce the remaining capacities, and repeat with other paths until no more flow can be pushed through. The total sent is the maximum flow.

Cuts and cut capacity

A cut divides the network into two groups of vertices: one containing the source, the other containing the sink. The capacity of a cut is the sum of the capacities of the edges that cross the cut from the source side to the sink side. Edges pointing back from the sink side to the source side are not counted. Every cut gives an upper limit on the flow, because all flow must cross it.

The maximum-flow minimum-cut theorem

The theorem states that the maximum flow from source to sink equals the capacity of the minimum cut, the cut with the smallest capacity. This gives a powerful method: find the minimum cut, and its capacity is the maximum flow. On larger networks where inspection is hard, locating the bottleneck cut is the reliable way to confirm the answer.

Worked example

Maximum flow via the minimum cut

Water flows from source S to sink T. The pipes and capacities are: S-A $= 6$ , S-B $= 4$ , A-T $= 5$ , B-T $= 7$ , A-B $= 2$ (directed A to B). Find the maximum flow.

Step 1: Check the capacity out of the source.

\text{S-A} + \text{S-B} = 6 + 4 = 10.

Step 2: Check the capacity into the sink.

\text{A-T} + \text{B-T} = 5 + 7 = 12.

Step 3: Consider the cut around the source (edges S-A and S-B crossing forward).

\text{capacity} = 6 + 4 = 10.

Step 4: Consider the cut around the sink (edges A-T and B-T crossing forward).

\text{capacity} = 5 + 7 = 12.

Step 5: Take the minimum cut. The smaller cut capacity is $10$ (around the source). By the maximum-flow minimum-cut theorem the maximum flow is $10$ .

Verify by pushing flow: send $5$ along S-A-T and $1$ along S-A-B-T (using A-B then B-T), giving $6$ out of S-A; send $4$ along S-B-T, giving $4$ out of S-B. Total $6 + 4 = 10$ , matching the minimum cut.

Common traps

Counting backward edges in a cut: Only edges crossing the cut from the source side to the sink side count towards the cut capacity. Including return edges overstates the cut.
Forgetting flow conservation: At an intermediate vertex the flow in must equal the flow out. Pushing more out of a vertex than enters it is invalid.
Exceeding an edge capacity: No edge can carry more than its capacity. Sending the source's full output down one undersized pipe breaks the rule.
Taking the maximum cut instead of the minimum: The theorem uses the minimum cut. Picking a larger cut gives an upper bound that is not tight, overstating the maximum flow.
Assuming the source or sink capacity alone is the answer: The bottleneck can be an interior cut, not the edges at the source or sink. Always check cuts across the middle of the network too.

Exam-style practice questions

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

2021 QCAA4 marksThe network diagram shows the flow of water from the tank (source) to the kitchen tap (sink), with four dashed lines L1, L2, L3 and L4 drawn across it. a) Explain which dashed line (L1, L2, L3 or L4) is not a valid cut. [1 mark] b) Calculate the capacity of each dashed line that is a valid cut. [3 marks] (L1 crosses edges of capacity 20, 22, 15; L2 crosses 18, 19, 22, 15; L3 crosses 18, 8, 10.)

Show worked answer →

a) Invalid cut (1 mark). A valid cut must separate the source from the sink, with the source on one side and the sink on the other. L4 is not valid because the tank (source) and the tap (sink) lie on the same side of the line, so it does not separate them.

b) Capacities of the valid cuts (3 marks). The capacity of a cut is the sum of the capacities of the edges it crosses that carry flow from the source side to the sink side.

L1 capacity = 20 + 22 + 15 = 57 (1 mark).

L2 capacity = 18 + 19 + 22 + 15 = 74 (1 mark).

L3 capacity = 18 + 8 + 10 = 36 (1 mark).

Only edges directed from the source side to the sink side are counted; an edge pointing back the other way contributes 0 to the cut capacity. By the maximum-flow minimum-cut theorem the maximum flow equals the smallest of these cut capacities, so here it would be 36 (the L3 value), the minimum cut.