When no augmenting path remains, the set of vertices still reachable from the source in the residual network is a cut, every arc leaving it is full, and no arc comes back into it carrying anything. So the capacity of that cut equals the value of the flow — and since no flow can exceed any cut, both are optimal. The algorithm produces its own proof, and the lab checks it against an enumeration of every cut there is.
Core ideas
The hard idea is that the certificate is free: it is the failed search's own reachable set. The asymmetry of a cut's capacity is what makes it work.
For a set S containing the source but not the sink, the capacity is the total capacity of the arcs from S to the outside. Arcs coming back into S contribute nothing at all. On the lab's backwards preset the set {1, 2} has capacity 6 with 9 units of capacity pointing back into it, and that 9 is simply not part of the number. Readers who add it get a cut capacity that no flow ever approaches.
Everything reaching the sink must cross from S to the outside at some point, and it can cross no faster than the capacity allows. So the value of ANY flow is at most the capacity of ANY cut. That one inequality is what makes an equality decisive: a flow and a cut of the same size prove each other optimal, with no further argument.
Let S be the vertices reachable from the source in the final residual network. The sink is not in it, or the search would have succeeded. Every arc from S to the outside is full, or its forward residual arc would have extended the search. Every arc from outside into S carries nothing, or its backward residual arc would have. So the net flow across the cut is exactly the cut's capacity, and it is also the value of the flow.
The material
What a cut is, the easy inequality, the theorem, what the lab enumerates, and the arc that is full and in no cut.
An s-t cut is a partition of the vertices into a set S containing the source and its complement containing the sink. Its capacity is the sum of c(a) over arcs a whose tail is in S and whose head is not. Arcs in the other direction are not counted.
For any flow f and any s-t cut S, the value of f is at most the capacity of S.
The value of f equals the net flow across the cut: summing conservation over every vertex of S cancels every arc with both ends inside, and leaves the total on arcs out of S minus the total on arcs into it.
The first sum is at most the capacity of S, because each arc's flow is at most its capacity. The second is at least 0, because flows are non-negative. So the value is at most the capacity.
□
The maximum value of a flow equals the minimum capacity of an s-t cut. Moreover, when the augmenting-path method stops, the set of vertices reachable from the source in the residual network is a cut of exactly that capacity.
Let f be the flow when no augmenting path remains, and let S be the set reachable from the source in the residual network. The sink is not in S, so S is a cut.
Take an arc from u in S to v outside. If it were not full, its forward residual arc would have taken the search from u to v, so v would be in S. Hence every such arc is full. Take an arc from v outside to u in S. If it carried anything, its backward residual arc would run from u to v and again put v in S. Hence every such arc carries nothing.
So the net flow across the cut is the total capacity out of S minus zero, which is the capacity of S; and the net flow across any cut is the value of f. By weak duality no flow exceeds this cut and no cut is below this flow, so both are optimal.
□
The lab opens on 1>2 16, 1>3 13, 2>3 10, 3>2 4, 2>4 12, 3>5 14, 4>3 9, 5>4 7, 4>6 20, 5>6 4 with source 1 and sink 6. The shortest-path rule reaches 23 in three augmentations. The reachable set afterwards is {1, 2, 3, 5}, and the arcs leaving it are 2>4 at 12, 5>4 at 7 and 5>6 at 4 — capacity 23, and all three are full. Separately, all 16 sets containing 1 and not 6 are enumerated; the smallest capacity among them is 23, attained by exactly one set, and it is the one the algorithm returned.
Three numbers reached by three different routes: the flow's value, the capacity of the cut read off the failed search, and the smallest capacity among every cut there is, found without any flow at all. The theorem says they are one number, and the panel computes them separately and compares.
A full arc is not automatically part of a minimum cut, and this is the misconception the lab's second preset exists for. On 1>2 1, 2>3 1, 3>4 5, 1>4 1 the maximum flow is 2, and three arcs end up full: 1>2, 2>3 and 1>4. The cut is only {1>2, 1>4}, the two arcs out of the reachable set {1}. Deleting 2>3 leaves the sink perfectly reachable; deleting the two cut arcs does not.
The reason is that 2>3 is full because of what happens downstream of it, not because it is a bottleneck between the two sides. Being full is a local fact about one arc; being in a cut is a statement about a partition. The lab prints both the saturated set and the cut set so the difference is visible rather than argued.
On a chain of three unit arcs, 1>2 1, 2>3 1, 3>4 1, there are 4 sets containing the source and not the sink, and 3 of them have capacity 1. The algorithm returns one of them — the reachable set, which is {1} — and the enumeration confirms that it is among the smallest. “The minimum cut” names a value and picks out a set only when the value is attained once, which on the opening network it is.
And the asymmetry of the definition is worth one concrete number. On 1>2 5, 2>3 5, 3>2 9, 3>4 5, 2>4 1 the maximum flow is 5. The set {1, 2, 3} leaves 5 and 1, so its capacity is 6, with nothing coming back. The set {1, 2} also has capacity 6 — and 9 units of capacity pointing back into it, from 3>2, which count for nothing. A definition that counted them would make that cut 15 and would break the theorem.
Measured against proved. The enumeration is exhaustive and it is also small: 16 cuts on six vertices, because only the four vertices that are neither source nor sink can be placed freely, and it is refused above the size it states. So the equality is read off a complete list on a network you can type and proved by the reachable-set argument everywhere else. This is the one lesson on the course where the measurement and the proof answer exactly the same question, which is what makes it the strongest result here.
Interactive
The residual-reachable set is a cut of the same capacity, and every other cut is at least as large
Method
The cut is the failed search's own output. Take it, check it, and report both numbers.
Reachability in the original network would reach the sink. The set you want is what the last, failed search touched: forward along arcs with spare capacity and backward along arcs carrying flow. Recording it costs nothing because the search computed it already.
Arcs from S to the outside, at full capacity, summed. Arcs pointing back in are excluded, and excluded is not the same as subtracted. The lab's backwards preset has 9 units pointing back into a cut of capacity 6, and both treatments of that 9 give the wrong number.
The value and the capacity should be equal. If they are not, one of them is wrong — usually the cut, from a mis-signed backward arc during augmentation. This is a free correctness check on the whole run and it is the reason to compute the cut even when only the value is wanted.
Check it: delete exactly those arcs and see whether the sink is still reachable. On the lab's saturated preset three arcs are full and only two of them separate the two sides, and the third can be deleted without disconnecting anything.
The network is 1>2 16, 1>3 13, 2>3 10, 3>2 4, 2>4 12, 3>5 14, 4>3 9, 5>4 7, 4>6 20, 5>6 4, source 1, sink 6, under the shortest-path rule.
Three augmentations and three bottlenecks that add to the answer: 12, 4 and 7. That is arithmetic about the run. The three 23s are the result, and they were produced by three methods that share nothing — pushing along paths, reading a reachable set, and enumerating every subset of four vertices.
The third path is the interesting one. It is four arcs long where the first two were three, and it uses 5>4 to get to the sink through 4>6 after 5>6 has filled. The shortest-path rule takes the shortest path that exists at the time, and what exists changes as arcs fill.
For a faded rehearsal, raise the capacity of 5>6 from 4 to 40 and predict the new value and the new cut before running it. The supplied first move is this: 5>6 is one of the three cut arcs, so relaxing it can only raise the minimum cut — but the arcs into 5 are limited by 3>5 at 14, and 1>3 at 13 limits that in turn. Say what the new maximum is, and which set attains it.
You should be able to compute a cut's capacity counting only the arcs that leave it, state and prove weak duality in one line, take the reachable set as the cut when the search fails, explain why every arc leaving it is full and every arc entering it is empty, and separate saturation from membership of a cut.
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.