Lesson 3: Minimum cut and maximum flow

All eight cuts, the minimum cut and the maximum flow

SkillsMinimum cut and maximum flowCapacity of a cut

Worked example

  • Complex familiar

Stormwater drains carry water from a catchment SS to a creek TT. Capacities are in litres per second (L/s).

(a) List all the cuts and their capacities.

(b) State the minimum cut and the maximum flow.

(c) Show a flow that reaches the maximum.

1 of 6 steps
  1. Step 1: Count the cuts

    There are 3 middle vertices (AA, BB, CC), so 23=82^3 = 8 cuts. List them by source side: none of the middle vertices, one, two, then all three.

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 2k2^k cuts by source side.

  2. For each, add only the edges from the source side to the sink side.

  3. Maximum flow = the smallest capacity. Confirm with a flow that reaches it.

Watch out for

  • Counting backward edges, which makes cuts such as {S,C}\{S, C\} look much larger than they are (45 instead of 35) — and can hide the true minimum in other networks.

  • Stopping after the "obvious" cuts at the source (21) and the sink (22) and missing the minimum, 18.

Save your progress with a free account