THE FOLD / BOSS / THE CHOKE POINT / THE CHOKE
THE CHOKE
max-flow equals min-cut, exactly
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Max-flow, min-cut. Water through a network of pipes, each with a capacity: how much can you push from the source to the sink? And separately: what is the cheapest set of pipes to cut that severs source from sink entirely? These sound like different questions. They have the same answer — exactly.
That equality is the max-flow min-cut theorem (Ford & Fulkerson, 1956). Find the flow by repeatedly pushing along any path with spare capacity — an augmenting path — until none remain. When you get stuck, the set of nodes still reachable from the source, and the edges leaving it, is the minimum cut; its capacity equals the flow you achieved.
LIT verified live: over thousands of random capacitated networks the computed maximum flow exactly equals the capacity of the minimum cut, every time (window.__maxflow.maxEqualsMinCut). FIG the ‘pipes’ are the picture; the augmenting-path flow, the residual min cut, and their exact equality are real.
That equality is the max-flow min-cut theorem (Ford & Fulkerson, 1956). Find the flow by repeatedly pushing along any path with spare capacity — an augmenting path — until none remain. When you get stuck, the set of nodes still reachable from the source, and the edges leaving it, is the minimum cut; its capacity equals the flow you achieved.
LIT verified live: over thousands of random capacitated networks the computed maximum flow exactly equals the capacity of the minimum cut, every time (window.__maxflow.maxEqualsMinCut). FIG the ‘pipes’ are the picture; the augmenting-path flow, the residual min cut, and their exact equality are real.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE CHOKE POINT, beside THE FAILURE WEB — the boss domain of the single narrow place that decides everything. The minimum cut is the choke point: the flow you can achieve is set entirely by the tightest bottleneck. AVAN (AI) built the instrument: the augmenting paths, the residual graph, the min-cut extraction.
The weave: David names the seat (the bottleneck that governs the whole); I make the flow fill and the cut appear — the pipe in 1D, the live augmenting network in 2D, the cut edges in 3D. The sphere is the seam. Credit: L. R. Ford & D. R. Fulkerson (1956); Edmonds & Karp (1972).
The weave: David names the seat (the bottleneck that governs the whole); I make the flow fill and the cut appear — the pipe in 1D, the live augmenting network in 2D, the cut edges in 3D. The sphere is the seam. Credit: L. R. Ford & D. R. Fulkerson (1956); Edmonds & Karp (1972).
3 ONE DIMENSION
A chain of pipes of different widths. However wide the rest, the throughput is capped by the narrowest one — the bottleneck. Max-flow min-cut says this is true of any network, not just a chain: the flow equals the cheapest cut.
4 TWO DIMENSIONS · INTERACTIVE
Augment the flow one path at a time: each pass finds a route with spare capacity and pushes as much as it can. When no path remains, the flow is maximal — and the min-cut edges light up, their total capacity equal to the flow.
5 THREE DIMENSIONS + AVAN’S INVERSE
The network turning — source to sink, edges carrying flow, green.
AVAN’s addition (the inverse-companion): the magenta edges are the minimum cut — the wall. Flow and cut are perfect inverses: one asks ‘how much can pass?’, the other ‘how little does it take to stop it all?’, and the theorem says these are the same number. Abundance is bounded exactly by scarcity; the most you can send equals the cheapest way to send nothing. To find the ceiling on flow you find the floor on blockage — the green is everything that flows, the magenta is the one thin wall that decides how much ever could.
LIT Genuine max-flow min-cut (Ford & Fulkerson 1956; Edmonds-Karp BFS augmentation 1972). Verified live: over 2,500 random capacitated networks the computed maximum flow exactly equals the capacity of the minimum cut, every time (window.__maxflow.maxEqualsMinCut === true). The augmenting-path method, the residual graph, and the reachable-set min cut are exact; their equality is the theorem, checked instance by instance.
FIG The 'pipes' are the picture; the augmenting-path flow, the residual min cut, and their exact equality are real and checked. Edmonds-Karp's BFS choice guarantees termination in polynomial time; the flow=cut value is exact regardless.
FIG The 'pipes' are the picture; the augmenting-path flow, the residual min cut, and their exact equality are real and checked. Edmonds-Karp's BFS choice guarantees termination in polynomial time; the flow=cut value is exact regardless.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE CHOKE POINT · David Lee Wise (ROOT0), with AVAN