Cuts, labelling procedure and max-flow min-cut

Cuts, labelling procedure and max-flow min-cut

Spec 3.1–3 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A feasible flow keeps 0≤flow≤capacity0\le\text{flow}\le\text{capacity} and has flow in == flow out at every vertex except S and T.
  • The capacity of a cut counts only arcs directed from XX (with S) to YY (with T).
  • The labelling procedure finds a route with spare capacity and increases the flow by the smallest label on it.
  • When T cannot be labelled, the flow is maximum.
  • Max-flow min-cut: the maximum flow equals the capacity of the minimum cut.

Networks and flows

A flow sends material from the source S to the sink T along directed arcs, within each arc's capacity and conserving flow at every other vertex.

A network of directed arcs has a source S, where flow starts, and a sink T, where it ends. Each arc has a capacity, the greatest flow it can carry.

A feasible flow obeys two rules: on every arc 0≤flow≤capacity0\le\text{flow}\le\text{capacity}, and at every other vertex flow in = flow out.

The value of a flow is the amount leaving S, which equals the amount entering T. An arc is saturated when its flow equals its capacity.

SA 7SB 5AB 3AT 4BT 6SABT
Capacities: SA 7, SB 5, AB 3, AT 4, BT 6.

At vertex A, flow in is 5 along one arc. Flow out goes along two arcs, one carrying 2. How much does the other carry?

Cuts and their capacity

A cut splits the vertices into XX (with S) and YY (with T). Its capacity is the total capacity of arcs from XX to YY.

A cut divides the vertices into two sets, XX containing the source S and YY containing the sink T.

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

Every flow is at most the capacity of every cut, because all the flow must cross from XX to YY. So the value of a flow is at most the minimum cut.

cap 5cap 4cap 2cap 3cap 6SABT
Network with capacities. The cut {S, A, B} | {T} (dashed) has capacity 3 + 6 = 9: only arcs from X to Y count.
  • Capacity of a cutarcs from XX to YY only

Worked example

In the network above, find the capacity of the cuts X={S,A}X=\{S,A\}, Y={B,T}Y=\{B,T\} and X={S,A,B}X=\{S,A,B\}, Y={T}Y=\{T\}.

A cut has X={S}X=\{S\}. Which arcs count?

The labelling procedure

Label vertices reachable from S using spare capacity forwards or flow that can be reduced backwards. If T is labelled, augment along the route.

The labelling procedure finds a flow-augmenting route from S to T and the amount to increase the flow by.

Each arc carries two numbers. The one in the arc's direction is the amount the flow can be increased (capacity minus flow). The one in the opposite direction is the amount it can be reduced (the current flow).

From S, label vertices reachable by a forward arc with spare capacity or a backward arc with flow. If T is labelled, trace back a route and increase the flow by the smallest number on it. Repeat until T cannot be labelled.

  1. 1

    Label from S

    forward arcs with spare capacity, backward arcs with flow

  2. 2

    Is T labelled?

    if not, the flow is maximum

  3. 3

    Trace the route

    back from T to S

  4. 4

    Find the increase

    the smallest label on the route

  5. 5

    Update the flow

    add on forward arcs, subtract on backward arcs

The labelling procedure

A route has spare capacities 4, 2 and 7. By how much can the flow increase?

A worked example

Augment along routes with spare capacity until T cannot be reached, then find a cut equal to the flow.

Arcs have capacities SA 9, SB 7, AB 4, AC 5, BC 6, BT 4, CT 8. The current flow is SA 5, SB 3, AB 2, AC 3, BC 3, BT 2, CT 6, with value 8.

Find the maximum flow, then prove it is maximum.

Increase the flow by the smallest label on the route, never the largest: the tightest arc limits the route.

SA 9SB 7AB 4AC 5BC 6BT 4CT 8SABCT
Capacities: SA 9, SB 7, AB 4, AC 5, BC 6, BT 4, CT 8.

Worked example

Increase the flow of value 8 to the maximum and prove it is maximum.

After the second augmentation, why is the flow of 12 maximum?

Max-flow min-cut

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

Max-flow min-cut theorem: the maximum value of a flow in a network equals the capacity of the minimum cut.

To prove a flow is maximum, find a cut whose capacity equals the value of the flow. No flow can exceed any cut, so the flow cannot be larger and the cut is a minimum cut. The cut's arcs from XX to YY are all saturated, and arcs from YY to XX carry no flow.

Increasing the capacity of an arc not in the minimum cut does not raise the maximum flow.

5/54/42/23/36/6SABT
Flow/capacity on each arc. The arcs across the dashed cut are saturated: flow 3 + 6 = 9 equals the cut capacity, so 9 is maximum.
  • Maximum flowcapacity of the minimum cut

A flow has value 15 and a cut has capacity 15. What can you conclude?

Try an exam question

A network has arcs SA (capacity 6), SB (4), AB (2), AT (3) and BT (5), all directed as written. (a) Find a feasible flow of value 8. (b) Use a cut to prove that 8 is the maximum flow.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

What is the capacity of the cut that separates {S,A}\{S,A\} from {B,T}\{B,T\}?

1 mark, marked against the mark scheme

Revision notes