Understand the idea.
Flow obeys two rules
A feasible flow respects every directed capacity and conserves flow at intermediate vertices: total inflow equals total outflow unless the model explicitly permits storage or loss. The source supplies the flow and the sink receives it.
Use one consistent rate unit, such as litres per second. Capacities are limits rather than amounts that must be used. Several routes may combine, but shared edges cannot carry more than their single stated capacity.
Prove a maximum with a cut
A cut places the source on one side and the sink on the other. Add capacities of edges pointing from the source side to the sink side. This sum bounds the total delivered flow; reverse-pointing edges do not add forward capacity.
To prove a maximum, exhibit a feasible flow and a cut with exactly that capacity. The flow shows the value is achievable; the cut shows it cannot be exceeded. Increasing an unrelated capacity cannot remove a bottleneck that another cut still imposes.
See the method in action.
Reach the bound
Find a maximum S-to-T flow in the displayed capacity network.
Worked solution
- 1
Assign the source outflows.
Both source edges carry their full capacities without exceeding them.
- 2
Conserve flow at A.
A sends out exactly its inflow, and both outgoing capacities are respected.
- 3
Conserve flow at B.
B receives five directly and two through A, matching the B-to-T capacity.
- 4
Calculate the delivered total.
The sink receives four from A and seven from B, giving an achievable flow of eleven.
- 5
Prove no larger flow is possible.
The source cut bounds every possible flow by eleven, matching the constructed feasible flow.
Maximum flow 11 units per time.
Check conservation
A junction receives 8 L/s and sends 5 L/s plus 4 L/s. Is this feasible with no storage?
Worked solution
- 1
Add the two outflows.
Both outgoing branches remove liquid from the junction.
- 2
Compare incoming and outgoing rates.
The junction would send out one litre per second more than it receives.
- 3
Assess feasibility.
With no storage contribution or extra source permitted, the required conservation of flow fails, so the assignment is infeasible.
No; conservation fails.
Try it yourself.
Check your understanding
A cut has forward capacities 4, 6 and 3. State the upper bound.
Show answer & reasoning
13 units per time.
Add the three forward capacities: units per time. Every source-to-sink flow is at most this cut capacity, though feasibility is needed to show thirteen can be achieved.
Keep practising
6 worksheet questions · 12 marks
Read the questions online
- A route S→A→T has capacities 9 and 5 L/s. What is its largest flow?2 marks
- Two edge-disjoint routes have bottlenecks 4 and 7 vehicles/min. Find their total possible flow.2 marks
- A junction receives 6 and 3 L/s. One outgoing edge carries 4. Find the other outflow.2 marks
- A feasible flow equals 18 and a cut has capacity 18. What follows?2 marks
- An edge has capacity 8 vehicles/min but assigned flow 10. Is it feasible?2 marks
- A cut has forward capacities 7 and 5 and a backward capacity 4. Find its forward capacity.2 marks
Read the worked solutions
Equivalent correct methods earn the corresponding marks. Include units where asked.
- A route S→A→T has capacities 9 and 5 L/s. What is its largest flow?2 marks
Both edges carry the same route flow.
The smaller capacity limits it.
5 L/s. - Two edge-disjoint routes have bottlenecks 4 and 7 vehicles/min. Find their total possible flow.2 marks
There is no shared constrained edge.
.
11 vehicles/min. - A junction receives 6 and 3 L/s. One outgoing edge carries 4. Find the other outflow.2 marks
Total inflow is 9.
Conservation gives .
5 L/s. - A feasible flow equals 18 and a cut has capacity 18. What follows?2 marks
Feasibility gives a lower bound of 18.
The cut gives the same upper bound.
The maximum flow is 18. - An edge has capacity 8 vehicles/min but assigned flow 10. Is it feasible?2 marks
It exceeds capacity by 2.
Capacity cannot be exceeded.
No. - A cut has forward capacities 7 and 5 and a backward capacity 4. Find its forward capacity.2 marks
Only forward crossings count.
.
12.
Curriculum reference & lesson scope
SACE Board of South Australia
Stage 1 General Mathematics: matrices and networks. Original learning resources follow the approved Ascent Library chapter map.
Official curriculum source ↗