Flows, cuts and the max-flow min-cut theorem

Flows, cuts and the max-flow min-cut theorem

Spec DC1–DC3 · AQA A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A feasible flow keeps every arc within its capacity and has flow in equal to flow out at every intermediate node.
  • The capacity of a cut counts only arcs from the source side to the sink side.
  • The value of any flow is at most the capacity of any cut.
  • Max-flow min-cut theorem: the maximum flow equals the capacity of the minimum cut.
  • Several sources or sinks are joined to a supersource or supersink.

Flow networks

A feasible flow stays within every arc's capacity and has flow in equal to flow out at each intermediate node.

A network flow problem uses directed arcs, each with a capacity. Flow enters at a source SS and leaves at a sink TT.

The value of a flow is the total leaving the source, which equals the total arriving at the sink. An arc is saturated when its flow equals its capacity.

  • On every arc0≤0\le flow ≤\le capacity
  • At every intermediate nodeflow in = flow out

Worked example

Arcs carrying 6 and 5 units enter a node. One outgoing arc carries 7. How much does the other outgoing arc carry?

An arc has capacity 8 and flow 8. What is it called?

Cuts and their capacity

A cut splits the nodes into a source side and a sink side, and its capacity counts only arcs going from source side to sink side.

A cut divides the nodes into two sets, XX containing the source and YY containing the sink.

The capacity of a cut is the sum of the capacities of the arcs directed from XX to YY. Arcs from YY to XX are not counted.

The cut {S,B}∣{A,T}\{S,B\}|\{A,T\} has capacity SA+BT=7+8=15SA+BT=7+8=15; arc ABAB is ignored. Every unit of flow must cross every cut, so any flow has value at most any cut's capacity. The minimum cut has the smallest capacity.

cap 7cap 6cap 2cap 4cap 8SABT
Capacities as labelled (not to scale). The cut {S,B}|{A,T} counts SA and BT.

For the same network, what is the capacity of the cut {S,A}∣{B,T}\{S,A\}|\{B,T\}?

The max-flow min-cut theorem

The value of the maximum flow equals the capacity of the minimum cut.

The maximum flow-minimum cut theorem applies to any network.

  • To prove a flow is maximal, find a cut whose capacity equals the flow's value. No flow can exceed that cut.
  • To find the maximum flow, find the minimum cut by listing cuts systematically, for example by growing the source set one node at a time.

The arcs of a minimum cut are the bottleneck: they are all saturated in a maximum flow.

  • Maximum flowcapacity of the minimum cut

A flow of value 12 is found, and a cut of capacity 12 exists. What do you conclude?

Supersources and supersinks

Join several sources to one supersource and several sinks to one supersink, so the usual methods apply.

Add a supersource SS, with a directed arc from SS to each real source, and/or a supersink ZZ, with a directed arc from each real sink to ZZ.

The capacity of each added arc is the most that source can supply or that sink can absorb. If no limit is given, the arc has unlimited capacity.

Example: factories able to supply 10 and 8 units become arcs SF1SF_1 (10) and SF2SF_2 (8); shops able to take 8 and 6 become arcs T1ZT_1Z (8) and T2ZT_2Z (6).

  1. 1

    Add a supersource S

    arc from S to each factory, capacity = its supply

  2. 2

    Keep the real network

    factories, depots and shops with their arc capacities

  3. 3

    Add a supersink Z

    arc from each shop to Z, capacity = what it can take

Converting to a single source and sink

Two sinks can absorb 5 and 9 units. Describe the arcs you add.

Finding the maximum flow

List every cut, find the smallest capacity, and that is the maximum flow; say what the bottleneck means in context.

In context, if the arcs were pipes in litres per second, the answer says what the whole system can deliver. To interpret a cut, say what it means: all flow must pass through those arcs, so their combined capacity limits the whole network.

cap 10cap 6cap 3cap 5cap 4cap 2cap 9SABCT
Capacities as labelled (not to scale).

Worked example

Find the maximum flow from SS to TT by considering cuts.

Why does the capacity of a cut limit the whole flow?

Try an exam question

A network has arcs SASA 8, SBSB 5, ABAB 2, ATAT 4 and BTBT 7, all directed away from SS towards TT. Find the capacity of each of the four cuts {S}\{S\}, {S,A}\{S,A\}, {S,B}\{S,B\} and {S,A,B}\{S,A,B\} (the set containing SS), and state the maximum flow.

[5 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Find the capacity of the cut that separates {S,B}\{S,B\} from {A,T}\{A,T\}.

1 mark, marked against the mark scheme

Revision notes