The idea, step by step
Flow obeys two rules
Every directed edge has a maximum capacity. A feasible flow never exceeds it. At an intermediate vertex, total inflow equals total outflow unless storage or loss is explicitly permitted. The source supplies flow and the sink receives it.
Use consistent units such as litres per second. A large capacity on one edge does not guarantee a high source-to-sink flow: a smaller downstream edge can be a bottleneck.
Prove a maximum with a cut
Divide vertices into a source side containing S and a sink side containing T. Add capacities crossing from the source side to the sink side. Every delivered unit must cross this cut, so its forward capacity is an upper bound. Backward edges do not add to that bound.
Show both a feasible flow and an equal-capacity cut to certify a maximum. A large feasible flow alone is not proof. Upgrading an edge helps only if the relevant bottleneck changes; another cut may still limit the total.
A common trap
Add every edge capacity to get maximum flow.
Instead: The same delivered units pass through several edges. Use feasible flow and a limiting cut.
See the thinking
Reach the bound
Find a maximum S-to-T flow in the displayed capacity network.
- Send 6 along S→A and 5 along S→B.
- At A send 4 to T and 2 to B.
- B receives and sends 7 to T.
- The total is .
- The source cut has capacity , proving no greater flow is possible.
Check conservation
A junction receives 8 L/s and sends 5 L/s plus 4 L/s. Is this feasible with no storage?
- Outflow is L/s.
- Outflow exceeds inflow by 1 L/s.
Check your understanding
A cut has forward capacities 4, 6 and 3. State the upper bound.
Show answer
13 units per time.
.
Your turn
6 questions · 12 marks · Work at your own pace.
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 ↗