Lesson 1: Flow networks: sources, sinks and capacities
Building a flow path by path
SkillReading flow networks
Worked example
The farm network in the figure carries water from the dam to the tank . Capacities are in kilolitres per hour (kL/h).
(a) What is the largest flow that the path –– can carry?
(b) Send as much as possible along ––, then along ––, then along –––. What total flow do you reach?
(c) Check that flow in equals flow out at and at .
Step 1: Find the bottleneck of S–A–T
The capacities along –– are 9 and 6. The smaller one limits the path, so it carries at most 6 kL/h.
Every kilolitre on this path passes through both pipes, so it can't carry more than the narrower one.
Step 2: Send 6 along S–A–T
Spare capacity left: has ; is full.
Step 3: Send 5 along S–B–T
The bottleneck is (as ). Spare capacity left: is full; has .
Step 4: Send 2 along S–A–B–T
Spare capacities on this path are : 3, : 3, : 2. The smallest is 2, so send 2. Now is full too.
Step 5: Add up the flows
kL/h. The edges now carry : 8, : 5, : 2, : 6, : 7.
Step 6: Check conservation
At : in , out ✓. At : in , out ✓.
Answer
(a) 6 kL/h. (b) A total flow of 13 kL/h, with , , , and . (c) Flow in = flow out = 8 at and 7 at .
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
The most a path can carry is its smallest (spare) capacity.
Send that much, reduce the spare capacities, and look for another path with spare capacity.
Check flow in = flow out at every middle vertex.
Watch out for
Adding the capacities along a path () instead of taking the smaller.
Forgetting that flow already sent uses up capacity: after step 2, has only 3 left, not 9.