D2 3.2, 3.3 - Labelling and the max-flow min-cut theorem | Edexcel A-Level Further Mathematics

You will label spare capacity and potential backflow, augment a feasible directed flow, and prove that a final flow is maximum by finding a matching cut.

Read excess capacity and potential backflow

Could sending less down one pipe increase the total delivered? Yes. In our example, reducing AB's flow from $3$ to $1$ helps total flow rise from $7$ to $9$ . The labelling procedure keeps track of exactly which earlier choices can be adjusted.

You already know

A feasible flow stays within capacities and conserves flow at intermediate nodes. Its value is the net source outflow. Every directed cut gives an upper bound; a cut capacity alone does not prove the bound is achieved.

For now, every lower capacity is zero. Beside each original directed arc, Pearson's labelling procedure records two arrows: one in the original direction and one in the opposite direction.

Residual labels on an original arc

For original arc $u\to v$ with capacity $c$ and current flow $f$ ,

\begin{array}{c|c|l} \text{Label direction}&\text{Available amount}&\text{Meaning}\\\hline u\to v&c-f&\text{increase the original flow}\\ v\to u&f&\text{reduce the original flow} \end{array}

These are residual capacities: forward excess and potential backflow. A zero label permits no positive adjustment in that direction.

Not in the formula booklet: learn it.

The backward arrow is permission to undo part of an allocation. It does not add a physical reverse pipe to the original network.

Worked example 1: label both directions

Question. An original arc $U\to V$ has capacity $7$ and flow $3$ . Give its residual labels.

Plan. Subtract the flow from capacity in the original direction; use the current flow in the reverse direction.

U\to V:\ 7-3=4,\qquad V\to U:\ 3

Why can the reverse adjustment be as large as $3$ ? That would reduce the original flow to zero, but no further.

Answer. Forward excess $4$ ; potential backflow $3$ .

Check. Increasing by $4$ gives flow $7$ , its capacity. Decreasing by $3$ gives zero. The two labels sum to the original capacity $7$ .

Worked example 2 changes only the current flow, from $3$ to $5$ , keeping capacity $7$ .

Worked example 2: a fuller arc has less forward room

Question. Find the residual labels when the current flow is $5$ .

Plan. Recalculate both labels from the same capacity.

U\to V:\ 7-5=2,\qquad V\to U:\ 5

Why do the labels change in opposite directions? Sending two more units uses two units of forward room and creates two more units that could later be removed.

Answer. Forward excess $2$ ; potential backflow $5$ .

Check. Both labels remain non-negative and sum to $7$ .

For a zero-lower-bound arc, its current flow equals the reverse label. With positive lower limits, that equality needs adjusting; the later restricted-capacity lesson supplies the rule.

Watch out

Wrong: call the backward label a second physical flow, or label both directions with $c-f$ . Right: the original direction records room to increase, and the opposite direction records room to decrease.

Fill the same arc completely.

Find a route and update its original flows

Use this new network, whose original middle arc is $A\to B$ . All rates are litres per second.

Original directed arc	Capacity	Current flow
$S\to A$	$5$	$5$
$S\to B$	$4$	$2$
$A\to B$	$3$	$3$
$A\to T$	$4$	$2$
$B\to T$	$5$	$5$

The current value is $7$ . It is feasible: A receives $5$ and sends $3+2$ , while B receives $2+3$ and sends $5$ .

Flow-augmenting route

A flow-augmenting route goes from S to T through residual arrows with positive labels. The largest permitted increase along that route is its smallest residual label.

Increase original flows on forward steps and decrease original flows on reverse steps by the same amount. Update both labels on every affected original arc.

Each internal route node gains and loses the same net adjustment, so conservation is preserved. Limiting the amount by every residual label preserves all capacity conditions.

Not in the formula booklet: learn it.

[DIAGRAM: asset_name: Forward excess and potential backflow on the network; asset_slug: 9fm0-d2-186-residual-labels; caption: The residual route S,B,A,T has available amounts2,3,2, so it augments by2.; description: Original grey arrows SA,SB,AB,AT,BT, with paired blue forward-excess and sage reverse-backflow arrows; labels SA0/5,SB2/2,AB0/3,AT2/2,BT0/5, with every original direction clear.]

Worked example 3: reduce an internal flow to deliver more

Question. Use residual route $S,B,A,T$ to improve the displayed current flow.

Plan. Read each residual direction carefully, take the route minimum and update the corresponding original arcs.

Residual step	Available amount	Original-flow change
$S\to B$	$4-2=2$	Increase SB
$B\to A$	$3$	Decrease AB
$A\to T$	$4-2=2$	Increase AT

The bottleneck is $\min(2,3,2)=2$ . Hence

f_{SB}:2\to4,\qquad f_{AB}:3\to1,\qquad f_{AT}:2\to4

SA remains $5$ , and BT remains $5$ .

Why subtract on AB? The route travels from B to A, opposite to the original A-to-B arrow.

Answer. The new flows are SA $5$ , SB $4$ , AB $1$ , AT $4$ , BT $5$ , with value $7+2=9$ .

Check. At A, $5=1+4$ ; at B, $4+1=5$ . Source outflow and sink inflow both equal $9$ . AB now has forward label $2$ and reverse label $1$ .

Worked example 4 changes only AT's capacity, from $4$ to $3$ , retaining the displayed starting flows.

Worked example 4: one smaller capacity limits the adjustment

Question. Use the same residual route $S,B,A,T$ when $c_{AT}=3$ .

Plan. Recalculate the changed residual label before taking the route minimum.

The route labels are now $2,3,3-2=1$ . Thus the increase is

\min(2,3,1)=1

Update SB from $2$ to $3$ , AB from $3$ to $2$ , and AT from $2$ to $3$ .

Why not retain the old increase $2$ ? It would put $4$ units through AT, exceeding its new capacity $3$ .

Answer. The new flow pattern is SA $5$ , SB $3$ , AB $2$ , AT $3$ , BT $5$ , of value $8$ .

Check. A has $5=2+3$ , B has $3+2=5$ , and the sink receives $3+5=8$ .

After an augmentation, do not search using stale residual labels. Each forward increase reduces its forward label and increases its reverse label by the same amount; a reverse adjustment does the opposite.

Watch out

Wrong: add to every original arc mentioned in the route, or take the smallest original capacity as the increase. Right: use residual labels, and subtract from an original flow whenever the route follows its reverse arrow.

Reduce the same outlet capacity one step further.

Continue the labelling procedure to completion

A route that helps now can require rerouting later. The reverse labels preserve that flexibility, so an early choice does not permanently block the best final flow.

The labelling procedure

Start with a feasible flow. Label each original arc with forward excess and reverse potential backflow.

Find an S-to-T route using only positive residual arrows.
Increase the flow value by the smallest label on that route, updating original flows and both residual labels.
Repeat from the updated labels until T cannot be reached from S through positive residual arrows.

Record every augmenting route and its amount, and give a final feasible flow pattern.

There is no requirement to select a unique route order. Different valid orders can take different numbers of steps. Always include the final original arc flows, rather than leaving only residual numbers.

Not in the formula booklet: learn it.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Core Pure Mathematics

Further Pure Mathematics 1

Further Pure Mathematics 2

Further Statistics 1

Further Statistics 2

Further Mechanics 1

Further Mechanics 2

Decision Mathematics 1

Decision Mathematics 2

D2 3.2, 3.3 - Labelling and the max-flow min-cut theorem

Read excess capacity and potential backflow

Find a route and update its original flows

Continue the labelling procedure to completion

Continue this lesson.

Learn faster with Nova