Lesson 3 of 7 · 18 min

Minimum cut and maximum flow

List every cut of a small flow network systematically, find the minimum cut, and use the maximum flow–minimum cut theorem to state the maximum flow, confirming it with a flow that reaches it.

What you will be able to do

  • Explain why no flow can be larger than the capacity of any cut.
  • List all the cuts of a network with up to three middle vertices (at most 8 cuts).
  • Find the minimum cut and state the maximum flow.
  • Confirm a maximum flow by showing a flow that reaches it.

In the first lesson you built a flow of 13 kL/h through the farm's pipes and wondered whether 14 might be possible. Here is how to settle it.

Every kilolitre that reaches the tank has to cross every cut. So a cut is like a toll gate on the only road into town: whatever its capacity, the flow can't be more. The cut with source side {S,A,B}\{S, A, B\} crosses only ATAT and BTBT, with capacity 6+7=136 + 7 = 13. No flow can beat 13, and you already have a flow of 13 — so 13 kL/h is the maximum.

Key idea

Maximum flow = minimum cut

The minimum cut is the cut with the smallest capacity. For any flow network,

maximum flow=capacity of the minimum cut\text{maximum flow} = \text{capacity of the minimum cut}

This is the maximum flow–minimum cut theorem. The minimum cut is the network's bottleneck.

Why the flow can't exceed any cut

Take any cut and any flow. Every unit of flow starts on the source side and finishes on the sink side, so it must cross from the source side to the sink side at least once. If it ever wandered back along an edge pointing towards the source side, it would have to cross forwards again later.

So the flow from source to sink is at most the total that the forward edges can carry — the cut's capacity. That is true for every cut, so the flow can't be larger than the smallest cut.

The surprising half of the theorem is that the smallest cut can always be filled exactly: you can always find a flow equal to it. You'll see that every time you check an answer by building the flow.

To find the minimum cut, check every cut. A cut is fixed by which middle vertices go on the source side, and each middle vertex goes on one side or the other. With kk middle vertices there are 2k2^k cuts: 2 middle vertices give 4 cuts, and 3 give 8. QCAA questions stay at 8 cuts or fewer.

List them systematically: no middle vertices on the source side, then each one alone, then each pair, then all of them.

Interactive

Every cut, one at a time

Step through all 8 cuts of the network from the last lesson. Watch for edges that point back across a cut: they are shown but not counted. Which cut is smallest, and what flow does it allow?

Worked example

All eight cuts, the minimum cut and the maximum flow

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

6 steps

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

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.

Find the maximum flow from SS to TT through this network. Capacities are in megalitres per day.

in ML/day

Note

More than one minimum cut

Two different cuts can share the smallest capacity. That doesn't change the maximum flow — it is still that smallest capacity — but it means there are two bottlenecks. Upgrading one pipe in one of them won't help while the other is still in the way.

A flow network has a source, a sink and 3 other vertices. How many different cuts does it have?

Common mistake

Stopping at the source

The edges leaving the source give one cut, and it is often not the smallest. In the check above it is 19, but the true limit is 17. Check every cut before you decide.

Exam tip

A full-marks maximum-flow answer has three parts:

  1. a list of the cuts, each with the edges counted and its capacity;
  2. "the minimum cut is … with capacity …, so the maximum flow is …" with units;
  3. ideally, a flow that reaches that value, to show it is achievable.

Summary

  • Every unit of flow crosses every cut, so no flow can exceed any cut's capacity.

  • Maximum flow = capacity of the minimum cut (the maximum flow–minimum cut theorem).

  • With kk middle vertices there are 2k2^k cuts; list them systematically by source side.

  • Leave out edges that point back across a cut in every capacity you calculate.

  • Confirm the answer by building a flow that equals the minimum cut. A network can have more than one minimum cut.

Finished the lesson?

Try the 2 quick checks above and the lesson completes itself, or mark it complete now.

Lesson 3 of 70% read

Save your progress with a free account