DC3, DC5 - Maximum flow and minimum cut

DC3, DC5 - Maximum flow and minimum cut

A poor first route need not prevent a good final flow: you can cancel part of an earlier choice and redirect it. DC5 develops residual networks and flow augmentation. DC3 explains how a feasible flow and an equal-valued cut give a complete proof that delivery is as large as possible.

Residual paths and reverse arcs

A network has only the arcs SA,SB,AB,AT,BTSA,SB,AB,AT,BT, each of capacity 4, and sends 4 units per minute along S→A→B→TS\to A\to B\to T. Can its delivery increase even though every original forward route is blocked by a saturated arc? Yes: you may need to undo part of an earlier route. A residual network records changes that remain possible, rather than the material currently moving.

Recall that feasibility means meeting every capacity limit and conserving flow at intermediate nodes. For an ordinary arc A→BA\to B with capacity cc and flow ff, you can increase its flow by up to c−fc-f, or decrease it by up to ff.

Residual arc and augmenting path

An original arc A→BA\to B gives a forward residual capacity c−fc-f from AA to BB, and a reverse residual capacity ff from BB to AA. Omit residual arcs of capacity zero. An augmenting path goes from source to sink through positive residual capacities. Its greatest permitted augmentation is the smallest residual capacity along the path.

Using a reverse residual arc reduces the corresponding original flow. It does not add a new physical pipe or send material the wrong way along the original one. If the original network also has a genuine opposite arc, keep the two original flows distinct; record which flow each residual step changes.

Augmenting a flow

For an augmenting path, choose

δ=min⁡(residual capacities on the path)\delta=\min(\text{residual capacities on the path})

Add δ\delta to each original flow traversed forwards and subtract δ\delta from each original flow traversed backwards. The flow value rises by δ\delta. At intermediate nodes the paired changes preserve conservation.

Not in the formula booklet: learn it.

The smallest residual capacity is the bottleneck. A path does not have to use all the spare capacity on every arc.

Worked example 1: a forward augmentation

Question. A network has only the arcs SA,SB,AB,AT,BTSA,SB,AB,AT,BT, each of capacity 4. Initially all flows are zero. Augment along S→A→B→TS\to A\to B\to T.

Plan. Find the path's bottleneck, then increase each original flow on it by that amount.

δ=min⁡(4,4,4)=4unused capacity on the pathfSA=fAB=fBT=4increase these three flowsfSB=fAT=0other arcs unchangedv=4new source outflow\begin{aligned} \delta&=\min(4,4,4)=4 && \text{unused capacity on the path}\\ f_{SA}=f_{AB}=f_{BT}&=4 && \text{increase these three flows}\\ f_{SB}=f_{AT}&=0 && \text{other arcs unchanged}\\ v&=4 && \text{new source outflow} \end{aligned}

Answer. The augmentation is 4 and the new flow value is 4.

Check. AA receives and sends 4; so does BB. All three used arcs meet, rather than exceed, their capacities.

Keep the network fixed and use that flow as the new starting point. Every original forward source-to-sink route is now blocked, but a residual reverse arc repairs the initial routing choice.

[DIAGRAM: asset_name: Cancelling an earlier flow; asset_slug: aqa7367-reverse-residual; caption: A reverse residual step cancels flow on AB and makes a larger delivery possible; description: Two panels show the same four-node network. The left panel labels original arcs with flow slash capacity: SA 4 slash 4, SB 0 slash 4, AB 4 slash 4, AT 0 slash 4 and BT 4 slash 4. The right panel shows the positive residual path S to B to A to T, each step of capacity 4. The reverse step B to A is clay and explicitly labelled as cancellation of A to B. Increasing SB and AT by 4 and decreasing AB by 4 raises the value from 4 to 8.]
A reverse residual step cancels flow on AB and makes a larger delivery possible

Worked example 2: cancelling on a reverse step

Question. Starting from the flow in Worked example 1, augment along the residual path S→B→A→TS\to B\to A\to T.

Plan. Use unused capacity on SBSB and ATAT, but cancel existing flow on ABAB.

δ=min⁡(4−0,4,4−0)=4forward, reverse, forwardfSB=0+4=4increase original SBfAB=4−4=0cancel original ABfAT=0+4=4increase original ATv=4+4=8old value plus augmentation\begin{aligned} \delta&=\min(4-0,4,4-0)=4 && \text{forward, reverse, forward}\\ f_{SB}&=0+4=4 && \text{increase original }SB\\ f_{AB}&=4-4=0 && \text{cancel original }AB\\ f_{AT}&=0+4=4 && \text{increase original }AT\\ v&=4+4=8 && \text{old value plus augmentation} \end{aligned}

The flows SA=4SA=4 and BT=4BT=4 stay unchanged. Why does conservation survive at BB? An extra 4 enters along SBSB, while cancelling ABAB removes 4 of its old inflow: the net inflow is unchanged.

Answer. The flow value becomes 8, with AB=0AB=0.

Check. AA receives 4 from SS and sends 4 to TT; BB does the same. Source outflow and sink inflow are both 8, and every original flow is between 0 and 4.

This is why a greedy path choice can be repaired. You need not discard the whole feasible flow and restart.

Watch out

Wrong: using residual B→AB\to A means increasing ABAB. Correct: it decreases ABAB. Rebuild residual capacities after each augmentation; the previous bottlenecks and available reverse steps may change.

Try the same cancellation with new capacities.

Proving a maximum with an equal cut

Finding a large flow proves what can be delivered. A cut proves what cannot be exceeded. When those numbers meet, there is no remaining gap to investigate.

Maximum flow–minimum cut theorem

In a finite directed network with nonnegative finite upper capacities, zero lower bounds, one source and one sink,

max⁡(feasible flow values)=min⁡(cut capacities)\max(\text{feasible flow values})=\min(\text{cut capacities})

In particular, a feasible flow of value kk and a cut of capacity kk prove simultaneously that the flow is maximum and the cut is minimum.

Not in the formula booklet: learn it.

The certificate works because every feasible flow value is at most every cut capacity. A feasible value kk gives a lower bound on the maximum, and the cut gives an upper bound kk. You do not have to calculate every other cut. However, a capacity calculation does not establish that your proposed arc flows are feasible: check them first.

Continue this lesson.

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

Create free account