Lesson 4: Solving practical flow problems

Evacuation routes and a road upgrade

SkillsFlow network problemsMinimum cut and maximum flow

Worked example

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

1 of 5 steps
  1. Step 1: List the 8 cuts

    By source side: {S}\{S\}: 15+10=2515 + 10 = 25; {S,A}\{S, A\}: SB+AC+AT=10+8+6=24SB + AC + AT = 10 + 8 + 6 = 24; {S,B}\{S, B\}: SA+BC+BT=15+5+4=24SA + BC + BT = 15 + 5 + 4 = 24; {S,C}\{S, C\}: SA+SB+CT=37SA + SB + CT = 37; {S,A,B}\{S, A, B\}: AC+AT+BC+BT=23AC + AT + BC + BT = 23; {S,A,C}\{S, A, C\}: SB+AT+CT=28SB + AT + CT = 28; {S,B,C}\{S, B, C\}: SA+BT+CT=31SA + BT + CT = 31; {S,A,B,C}\{S, A, B, C\}: AT+BT+CT=6+4+12=22AT + BT + CT = 6 + 4 + 12 = 22.

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

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.

Save your progress with a free account