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

  1. 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.

  2. List every cut

    With at most three middle vertices there are at most 8 cuts. For each, add only the forward edges.

  3. Find the minimum cut and maximum flow

    Maximum flow = the smallest cut capacity. Name the edges in the minimum cut: they are the bottleneck.

  4. 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.

Walking routes from the train station to a stadium on a game night. The routes are one-way for crowd safety. Capacities are in people per minute.
FromToCapacity (people per minute)
Station (SS)Park (AA)30
Station (SS)Bridge (BB)20
Park (AA)Bridge (BB)10
Park (AA)Stadium (TT)15
Bridge (BB)Stadium (TT)35

The table drawn as a flow network: SS is the station (source) and TT 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.

in people per minute

Worked example

Evacuation routes and a road upgrade

  • Complex unfamiliar

Planners model the roads out of a coastal town as a flow network. SS is the town centre, TT is the inland highway, and capacities are in vehicles per minute.

(a) Find the maximum flow of vehicles from SS to TT.

(b) About 1980 vehicles need to leave the town. Find the shortest time this could take.

(c) The council can widen road ATAT 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.

5 steps

Try it yourself first, then check the working one step at a time.

Method

  1. List all the cuts and take the smallest as the maximum flow.

  2. Divide a total by the maximum flow to get the least time.

  3. 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 {S,A,B}\{S, A, B\} and crosses ACAC, BCBC and BTBT (capacity 18). Increasing which one edge by 1 would increase the maximum flow?

Choose one answer

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.

Lesson 4 of 70% read

Save your progress with a free account