Push flow along paths in the residual network — forward where there is spare capacity, backward where flow can be undone — until no path remains. The set of nodes still reachable from the source is then a cut whose capacity equals the flow value, which proves both optimal at once. And the reason a cut bounds a flow is not an analogy: every cut is a zero-one feasible point of the dual programme.
Core ideas
The theorem is famous and the bound half of it is easy. The two ideas that repay attention are the backward arc and the sense in which a cut is a dual solution.
Everything reaching the sink must cross from the source's side to the other side at some point, and the arcs crossing can carry at most their total capacity. So each cut gives a bound, immediately, with no computation beyond an addition. The lab enumerates every cut of the network — four on its first instance, sixteen on its widest — and checks that each one bounds the current flow.
The residual network holds a forward arc wherever spare capacity remains and a backward arc wherever flow has already been sent. A path using a backward arc un-sends flow on that arc and re-routes it, and without that the algorithm can strand itself at a non-maximum flow. On the lab's first instance the third augmentation does exactly this: it routes through b, undoes a unit that had gone from a to b, and sends it to the sink instead.
The maximum-flow programme has one equality row per interior node and one bound row per arc, so its dual has one variable per interior node and one per arc. Set the node variable to one for nodes inside S and the arc variable to one for arcs crossing out of S, and that point is dual feasible with objective exactly the cut's capacity. The lab checks this for every cut it enumerates, which is why “a cut bounds a flow” is weak duality rather than a resemblance.
The material
Cuts and the bound first, then augmentation on the residual network, then the theorem and the dual reading that explains it.
An s-t cut is a set of nodes S containing the source and not the sink. Its capacity is the total capacity of the arcs whose tail is in S and whose head is not — arcs running the other way do not count.
The value of a flow is the net amount leaving the source. Every unit of it must cross every cut, so the value of any flow is at most the capacity of any cut.
That is the easy half and it is worth having on its own: any cut you can write down is a bound on every flow that will ever be found, and an arithmetic check that takes seconds. The hard half is that the bound is attained — that some cut has exactly the capacity of the largest flow — and the algorithm proves it by producing the cut.
Notice the third augmentation. The path runs from s to b on a forward arc, then from b to a on a backward arc — there is no arc from b to a in the network at all; what exists is a unit already sent from a to b, which this path un-sends — and then from a to t. The net effect is to reroute a unit that had been sent the wrong way. Without backward arcs the algorithm would have stopped at 4.
In any network the maximum value of an s-t flow equals the minimum capacity of an s-t cut.
When no augmenting path remains, let S be the set of nodes reachable from the source in the residual network. Every arc out of S must be saturated, or its forward residual arc would extend the reachable set; every arc into S must be empty, or its backward residual arc would. So the flow across that cut is exactly its capacity, and since flow value is at most any cut's capacity, both are optimal.
The proof is the algorithm's stopping condition read as a statement about the cut, which is why the certificate costs nothing extra: it is the set the search had already computed when it failed to find a path. The lab shades it and prints its capacity beside the flow value.
The maximum-flow programme on the four-node network above has five variables — one per arc — and seven rows: two conservation equalities at the interior nodes a and b, and five capacity bounds. Its dual therefore has seven variables, one for each of those rows: a potential for each interior node and an indicator for each arc.
The cut S = {s} becomes the point with both node potentials at zero and the indicators on s>a and s>b at one, everything else zero. The cut S = {s, a, b} becomes both potentials at one and the indicators on a>t and b>t at one.
The lab checks both against the dual's constraints row by row: each is feasible, and each has dual objective 5 — exactly its own capacity. It then does the same for every cut of the network, including the two of capacity 6, and every one is a feasible dual point whose objective is its capacity. That is why a cut bounds a flow: it is weak duality with different nouns.
And the exact simplex on the primal programme returns 5. A feasible primal point worth 5, a feasible dual point worth 5, and the simplex agreeing with both: strong duality, exhibited on the instance rather than cited.
The four-node instance has two minimum cuts out of four. A second instance has exactly one, {s, b} at capacity 5, and it is the reachable set the algorithm lands on. A six-node instance has sixteen cuts, four of them minimum at capacity 7, and the augmenting loop still finishes at a flow of 7.
The reachable set is one minimum cut and the algorithm names it; the others are just as valid as certificates. What the theorem asserts is about the number 7, not about which set attains it.
What is deliberately not here is the choice of augmenting path. Take them in a bad order and the algorithm still terminates on integer capacities, but the number of augmentations can be much larger than it needs to be; bounding it is the Algorithms path's business, in its treatment of graph algorithms. The lab lets you pick any residual path from a list precisely so that the choice is visible as a choice.
Interactive
Any cut bounds any flow; the minimum cut is the optimal dual solution, and it is 0/1 because the matrix is
Method
The proof arrives with the algorithm; the work is in not throwing it away.
A forward arc with uᵢⱼ − fᵢⱼ wherever there is spare capacity, and a backward arc with fᵢⱼ wherever something has been sent. The backward arcs are not optional and they are not arcs of the original network.
The bottleneck is the smallest residual capacity on the path. Push that much: add it on forward arcs, subtract it on backward arcs. Any path will do for correctness; which one you take affects only how many pushes you make.
On integer capacities each push increases the value by at least one, so this terminates. The stopping condition is the absence of a path, not the exhaustion of any particular arc.
Every arc out of it is saturated and every arc into it is empty, so its capacity equals the flow value. This is the certificate, and it is free: the search that failed to find a path has already computed the set.
A flow of value v and a cut of capacity v. Anyone can verify the cut by adding up a handful of capacities, and that verification proves no flow exceeds v without re-running anything.
Every residual network, every path offered, every bottleneck and every cut below is what the lab computes as the flow is pushed.
Push 3 is the lesson. There is no arc from b to a in the network; the path uses one anyway, because a unit had already been sent from a to b and sending it back is allowed. Delete the backward arcs from the residual network and the algorithm stops at 4 and reports it as maximum.
For a rehearsal, restart and take the paths in a different order — s, a, t first, then s, b, t, then whatever remains. You will reach 5 again, in a different number of pushes, and quite possibly without ever needing a backward arc. The order affects the work and not the answer.
The harder rehearsal: open the six-node instance. It has sixteen cuts and four of them are minimum at capacity 7. Find a second minimum cut by hand, check it against the lab's enumeration, and satisfy yourself that it certifies the same 7 as the reachable set does. A certificate does not have to be the one the algorithm found.
You should be able to build a residual network including its backward arcs, push along a path and update, recognise the stopping condition, take the reachable set as a minimum cut and verify its capacity, and write a cut as a zero-one point of the dual programme.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.