Lesson 3: Minimum cut and maximum flow
All eight cuts, the minimum cut and the maximum flow
SkillsMinimum cut and maximum flowCapacity of a cut
Worked example
Stormwater drains carry water from a catchment to a creek . Capacities are in litres per second (L/s).
(a) List all the cuts and their capacities.
(b) State the minimum cut and the maximum flow.
(c) Show a flow that reaches the maximum.
Step 1: Count the cuts
There are 3 middle vertices (, , ), so cuts. List them by source side: none of the middle vertices, one, two, then all three.
Step 2: The cuts with zero or one middle vertex on the source side
- :
- :
- : ( points back)
- : (, point back)
Step 3: The cuts with two or three middle vertices on the source side
- :
- : ( points back)
- : (, point back)
- :
For each cut, an edge counts only if its tail is on the source side and its head is on the sink side.
Step 4: Choose the smallest
The minimum cut is , through , and , with capacity 18. So the maximum flow is 18 L/s.
Step 5: Build a flow of 18
Send 7 along –––, 8 along ––, 1 along ––– and 2 along ––––. Edge flows: , , , , , , — none over capacity.
Step 6: Check conservation
At : in 9, out ✓. At : in , out ✓. At : in , out 10 ✓. Total into : ✓.
Answer
(a) The capacities are 21, 20, 23, 35, 18, 27, 34 and 22 L/s for source sides , , , , , , and . (b) The minimum cut is with capacity 18, so the maximum flow is 18 L/s. (c) For example , , , , , , .
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
List all cuts by source side.
For each, add only the edges from the source side to the sink side.
Maximum flow = the smallest capacity. Confirm with a flow that reaches it.
Watch out for
Counting backward edges, which makes cuts such as look much larger than they are (45 instead of 35) — and can hide the true minimum in other networks.
Stopping after the "obvious" cuts at the source (21) and the sink (22) and missing the minimum, 18.