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

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.

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.

A systematic way to test cuts

Trial and error on cuts works, but a tidy method avoids missing the bottleneck. Start at the source: every path out of S must cross any valid cut, so the total capacity leaving S is one cut to test. Do the same at the sink. Then look for an obvious narrow point, an edge or small group of edges that every path is forced through, and draw a cut there. Each cut must completely separate S from T, so check that no path sneaks around your dividing line. List each candidate cut with its capacity, then report the smallest. Writing the cuts out in a short table makes your reasoning legible and earns the method marks even if one arithmetic step slips.

Counting only forward edges

The single rule that trips students is which edges to count. A cut divides the vertices into a source side (containing S) and a sink side (containing T). Its capacity is the sum of capacities of edges directed from the source side to the sink side only. An edge directed from the sink side back to the source side crosses the same dividing line but contributes zero, because it cannot carry flow towards T across that cut. Before adding, check the direction of every edge that crosses your line and discard the backward ones. Forgetting this consistently overstates a cut and can make you report the wrong minimum.

Why the theorem holds intuitively

The maximum-flow minimum-cut result says the most you can push from S to T equals the capacity of the tightest cut. The intuition is a bottleneck argument: any flow from S to T must cross every cut, so it can never exceed the capacity of the smallest cut, which gives an upper bound. The deeper half of the theorem, that this bound is always achievable, means there is genuinely a flow pattern reaching that value. For VCE you use the practical consequence: find the minimum cut and report its capacity as the maximum flow, identifying that cut as the bottleneck limiting 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.