What is the greatest amount that can flow through a network from source to sink?
Determine the maximum flow through a network using the maximum-flow minimum-cut theorem.
Sources, sinks, edge capacities, cuts, and the maximum-flow minimum-cut theorem for finding the greatest flow through a network in TCE Mathematics Applications.
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
Flow networks model anything that moves through a capacity-limited system: water through pipes, traffic through roads, or data through cables. Each edge can carry only so much, and the question is how much can get from start to end overall.
Cuts
A cut divides the network into two groups of vertices, one containing the source and the other containing the sink, by cutting through some edges. The capacity of the cut is the total capacity of the edges that go from the source side to the sink side.
Only edges pointing from the source side to the sink side count toward a cut's capacity. Edges pointing back the other way are not added in, because they do not carry flow toward the sink across that division.
Why the minimum cut limits the flow
No flow can cross a cut faster than the cut's total capacity, because every drop reaching the sink must pass through the cut edges. So the smallest cut is the tightest bottleneck, and it caps the whole network. Finding it gives the maximum flow without tracing every individual route.
Reporting the answer
State the minimum cut you found, list its edges and their capacities, and give the maximum flow as that cut's total. Interpreting it in context, for example litres per minute, shows you understand the result rather than just the arithmetic.
A complete answer identifies the source and sink, tests sensible cuts, applies the maximum-flow minimum-cut theorem to set the maximum flow equal to the minimum cut, and states that flow in the units of the problem.
Exam-style practice questions
Practice questions written in the style of TASC exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.
2024 TASC General Mathematics5 marksFigure 12 shows water pipes through a Marine Research Laboratory; numbers are capacities in litres per minute. a) i. Label the source and sink on the diagram. ii. Add another cut to the diagram. iii. What is the capacity of cut A? iv. What is the capacity of cut B? b) i. What is the maximum water flow through this system? ii. Which three pipes are possibilities for upgrade to improve the total flow?Show worked answer →
a) i. (1 mark) The source is the vertex where all water enters (no flow in); the sink is where all water leaves (no flow out).
a) ii. (1 mark) Draw any line that separates the source from the sink, cutting only forward-directed edges.
a) iii and iv. (2 marks) The capacity of a cut is the sum of the capacities of the edges crossing it in the source-to-sink direction only (ignore edges pointing back). Add those capacities for cut A and for cut B. Remember to include the units L/min.
b) i. (about 1 mark) By the maximum-flow minimum-cut theorem, the maximum flow equals the capacity of the smallest cut. Find the cut with the lowest total capacity; that value is the maximum flow.
b) ii. The three pipes worth upgrading are the edges that lie on (are crossed by) the minimum cut, since these are the bottleneck pipes limiting the flow.
2021 TASC General Mathematics3 marksA graph shows how much gas (in L/min) can flow through pipes joining places in a factory; management wants the maximum flow of gas from X to Y. a) What is meant by the terms source and sink? Explain with reference to the graph. d) Determine the maximum flow from X to Y.Show worked answer →
a) (1 mark) The source (X) is the vertex from which all the gas originates and where flow only leaves; the sink (Y) is the destination vertex where all gas ends up and where flow only enters.
d) (2 marks) By the maximum-flow minimum-cut theorem, the maximum flow from X to Y equals the capacity of the minimum cut. Make cuts separating X from Y, find the capacity of each (sum of forward edge capacities crossing it), and the smallest of these cut capacities is the maximum flow in L/min.