Lesson 4: Solving practical flow problems
Evacuation routes and a road upgrade
SkillsFlow network problemsMinimum cut and maximum flow
Worked example
Planners model the roads out of a coastal town as a flow network. is the town centre, is the inland highway, and capacities are in vehicles per minute.
(a) Find the maximum flow of vehicles from to .
(b) About 1980 vehicles need to leave the town. Find the shortest time this could take.
(c) The council can widen road so that its capacity rises from 6 to 11 vehicles per minute. A councillor says this will raise the maximum flow by 5. Evaluate the claim.
Step 1: List the 8 cuts
By source side: : ; : ; : ; : ; : ; : ; : ; : .
In , and , the edges into from the sink side point back and are not counted.
Step 2: State the maximum flow
The minimum cut is with capacity 22, so the maximum flow is 22 vehicles per minute. (Check: , , , , , , is a flow of 22.)
Step 3: Convert to a time
minutes, or hours — the best case, assuming the roads run at capacity the whole time.
Step 4: Recalculate the cuts after the upgrade
Only cuts containing as a forward edge change, each by : becomes 29, 28, 33 and 27. The others stay at 25, 24, 37 and 31.
Step 5: Find the new maximum flow
The new minimum cut is , through , and , with capacity 24. The maximum flow rises from 22 to 24, an increase of only 2.
Once the old bottleneck is widened, a different cut becomes the smallest and limits the flow.
Answer
(a) 22 vehicles per minute (minimum cut through , and ). (b) minutes at best. (c) The claim is wrong: after the upgrade the cut through , and (capacity 24) becomes the minimum, so the maximum flow rises by only 2, to 24 vehicles per minute. The evacuation would then take at least minutes.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
List all the cuts and take the smallest as the maximum flow.
Divide a total by the maximum flow to get the least time.
After an upgrade, recalculate every cut containing that edge, then take the new smallest.
Watch out for
Assuming the increase in an edge's capacity passes straight through to the maximum flow.
Using the flow out of the source (25) as the maximum flow.