VICGeneral MathematicsSyllabus dot point

How do you find the greatest flow a network can carry from source to sink, and how does the minimum cut prove the maximum flow?

Model a directed capacitated network with a source and sink, find the maximum flow from source to sink, identify cuts and their capacities, and use the minimum cut to confirm the maximum flow

A focused answer to the VCE General Mathematics Unit 4 Networks key-knowledge point on flow. Capacities, source and sink, finding the maximum flow, defining a cut and its capacity, counting only forward edges, and the maximum-flow minimum-cut result.

Generated by Claude Opus 4.77 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

Jump to a section

What this dot point is asking
Capacities, source and sink
Cuts and their capacity
The maximum-flow minimum-cut result
Why this matters for the exams

What this dot point is asking

VCAA wants you to find the greatest rate at which something (water, traffic, data) can flow through a directed network from a source to a sink when each edge has a capacity. You find the maximum flow, define a cut that separates source from sink, calculate a cut's capacity, and use the minimum cut to prove the maximum flow. The key theorem is that the maximum flow equals the minimum cut capacity.

Capacities, source and sink

Each directed edge carries a capacity, the maximum it can pass per unit time. Flow enters at the source and leaves at the sink. The amount entering the source equals the amount leaving the sink, and at every other vertex the flow in equals the flow out. The maximum flow is the largest total the network can sustain.

Cuts and their capacity

A cut chops the network into a source side and a sink side. To find its capacity, add the capacities of only the edges that point from the source side to the sink side. Edges pointing the other way (from sink side back to source side) do not count toward the cut capacity.

Worked example

Finding the maximum flow from cuts

Water flows from source S to sink T. The pipes and capacities are S to A $= 6$ , S to B $= 4$ , A to T $= 5$ , B to T $= 7$ , and a cross pipe A to B $= 2$ .

Consider the cut just after the source: edges leaving S are S to A $= 6$ and S to B $= 4$ , total capacity $6 + 4 = 10$ .

Consider the cut just before the sink: edges entering T are A to T $= 5$ and B to T $= 7$ , total capacity $5 + 7 = 12$ .

Consider a cut separating {S, A} from {B, T}: forward edges crossing are S to B $= 4$ , A to B $= 2$ and A to T $= 5$ , total $4 + 2 + 5 = 11$ .

The smallest cut capacity found is $10$ , so the maximum flow from S to T is $10$ units. The minimum cut sits at the source, which limits the whole network.

The maximum-flow minimum-cut result

The maximum flow you can push through the network always equals the capacity of the minimum cut. In practice you test a handful of sensible cuts, find the one with the smallest capacity, and report that value as the maximum flow. The minimum cut identifies the bottleneck that limits the network.

Why this matters for the exams

Maximum-flow questions are a Networks staple and reward systematically testing cuts and identifying the minimum. Markers want the cut capacities shown and the maximum flow stated as the minimum cut value. The technique is purely about capacities and direction, distinct from the spanning tree and shortest path problems, and it leads naturally into bipartite matching and allocation.