Lesson 4 of 7 · 16 min
Solving practical flow problems
Model roads, pipes and paths as flow networks, find the maximum flow, turn it into times and totals, and decide which upgrade would actually increase the flow.
What you will be able to do
- Draw a flow network from a description or a table, with the source, sink, directions and units.
- Use the maximum flow to answer practical questions about time and quantity.
- Explain which edges are worth upgrading, and work out the new maximum flow after an upgrade.
When a cyclone threatens a coastal town in North Queensland, emergency planners need to know how quickly residents can drive out. The roads become a flow network: the town centre is the source, the highway junction inland is the sink, and each road's capacity is how many vehicles per minute it can carry safely.
The maximum flow tells the planners the best possible rate — and the minimum cut tells them which roads are holding everyone up.
Solving a flow problem
Set up the network
Identify the source and sink, draw each link as a directed edge, and label it with its capacity. Note the units.
List every cut
With at most three middle vertices there are at most 8 cuts. For each, add only the forward edges.
Find the minimum cut and maximum flow
Maximum flow = the smallest cut capacity. Name the edges in the minimum cut: they are the bottleneck.
Answer the question asked
Convert to the quantity asked for (a time, a total, a percentage), with units, and comment on whether it is reasonable.
| From | To | Capacity (people per minute) |
|---|---|---|
| Station () | Park () | 30 |
| Station () | Bridge () | 20 |
| Park () | Bridge () | 10 |
| Park () | Stadium () | 15 |
| Bridge () | Stadium () | 35 |
The table drawn as a flow network: is the station (source) and the stadium (sink). Capacities are in people per minute.
Using the table, find the maximum number of people per minute who can walk from the station to the stadium.
Worked example
Evacuation routes and a road upgrade
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.
Try it yourself first, then check the working one step at a time.
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.
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.
Key idea
Which upgrades help?
Increasing an edge's capacity raises the maximum flow only if that edge is in every minimum cut. Even then, the gain stops as soon as another cut becomes the smallest — so the new maximum flow is the smallest of the new cut capacities, which you must recalculate.
Upgrading an edge outside the minimum cut changes nothing: the bottleneck is still there.
In the network from the lesson on cuts, the minimum cut has source side and crosses , and (capacity 18). Increasing which one edge by 1 would increase the maximum flow?
Common mistake
Assuming the gain equals the upgrade
In the example, widening a road by 5 vehicles per minute raised the maximum flow by only 2, because a different cut took over as the bottleneck. Always recalculate the cuts after an upgrade.
Tip
Is it reasonable?
The maximum flow can never be more than the total leaving the source, or the total arriving at the sink. If your answer is bigger than either, you have counted an edge that points back, or missed a cut.
Summary
Set up the network with direction, capacities and units before you calculate.
The maximum flow is a rate: divide a total by it to get a time, or multiply it by a time to get a total.
The edges of a minimum cut are the bottleneck. Only upgrading an edge in every minimum cut can help.
After an upgrade, recalculate the cuts: the new maximum flow is the new smallest cut, and the gain is often less than the upgrade.
Sanity check: the maximum flow is at most the capacity out of the source and into the sink.
Finished the lesson?
Try the 2 quick checks above and the lesson completes itself, or mark it complete now.