Lesson 1: Flow networks: sources, sinks and capacities

Building a flow path by path

SkillReading flow networks

Worked example

  • Simple familiar

The farm network in the figure carries water from the dam SS to the tank TT. Capacities are in kilolitres per hour (kL/h).

(a) What is the largest flow that the path SS–AA–TT can carry?

(b) Send as much as possible along SS–AA–TT, then along SS–BB–TT, then along SS–AA–BB–TT. What total flow do you reach?

(c) Check that flow in equals flow out at AA and at BB.

1 of 6 steps
  1. Step 1: Find the bottleneck of S–A–T

    The capacities along SS–AA–TT are 9 and 6. The smaller one limits the path, so it carries at most 6 kL/h.

    6 kL/h6\ \text{kL/h}

Try a similar one

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

Method

  1. The most a path can carry is its smallest (spare) capacity.

  2. Send that much, reduce the spare capacities, and look for another path with spare capacity.

  3. Check flow in = flow out at every middle vertex.

Watch out for

  • Adding the capacities along a path (9+6=159 + 6 = 15) instead of taking the smaller.

  • Forgetting that flow already sent uses up capacity: after step 2, SASA has only 3 left, not 9.

Save your progress with a free account