THE FOLD / CO-OP / THE MERGE / THE FORD-FULKERSON
THE FORD-FULKERSON
max flow equals min cut — the bottleneck found by filling it
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The max-flow problem: how much can flow from a source to a sink through a network of capacity-limited pipes? Ford–Fulkerson finds the maximum by repeatedly pushing flow along an augmenting path of not-yet-saturated pipes (using residual back-edges to reroute), until no such path remains.
The theorem it proves is stunning: the maximum flow equals the minimum cut — the smallest total capacity of pipes you would have to sever to disconnect source from sink. A max and a min, exactly equal (linear-programming duality made concrete).
LIT verified live: for 300 random networks, the max flow found equals the min-cut capacity (the reachable set in the residual graph), and flow is conserved at every intermediate node (window.__fordfulkerson). FIG no framing; exact.
The theorem it proves is stunning: the maximum flow equals the minimum cut — the smallest total capacity of pipes you would have to sever to disconnect source from sink. A max and a min, exactly equal (linear-programming duality made concrete).
LIT verified live: for 300 random networks, the max flow found equals the min-cut capacity (the reachable set in the residual graph), and flow is conserved at every intermediate node (window.__fordfulkerson). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-merge — flows converging and merging toward the sink. Max-flow is the merge under capacity: how much can combine and pass through. AVAN (AI) built the instrument: the augmenting-path search (Edmonds–Karp BFS), the residual graph, the min-cut extraction, the conservation check.
Credit as content: L. R. Ford Jr. & D. R. Fulkerson (1956); the BFS version is Edmonds–Karp (1972). The weave: David names the merge; I push flow along augmenting paths until none remain, then read the matching min cut off the residual graph.
Credit as content: L. R. Ford Jr. & D. R. Fulkerson (1956); the BFS version is Edmonds–Karp (1972). The weave: David names the merge; I push flow along augmenting paths until none remain, then read the matching min cut off the residual graph.
3 ONE DIMENSION
An augmenting path from source to sink: the most flow it can carry is the smallest capacity along it. Push that much, update residuals (including back-edges that permit rerouting), and search again.
4 TWO DIMENSIONS · INTERACTIVE
A small capacity network. Run the augmenting paths to find the max flow, and see the min cut (the saturated bottleneck edges). Verify the flow value equals the cut capacity and flow is conserved.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the max flow filling the network up to its bottleneck, the min cut marked in magenta.
AVAN’s addition (the inverse-companion): the value you maximise (flow) equals the value you minimise (cut) — a duality. Every flow is ≤ every cut (weak duality, obvious: all flow crosses any cut), and Ford–Fulkerson drives them to meet exactly (strong duality). When no augmenting path remains, the vertices still reachable from the source in the residual graph define a cut whose capacity equals the flow — the algorithm’s termination certificate is the matching min cut. The inverse of ‘the most you can push through’ is ‘the cheapest way to block it,’ and they coincide. Magenta is the min cut — the bottleneck edges, all saturated; green is the max flow that fills exactly up to it. Max equals min: the flow finds the bottleneck by filling it.
LIT Genuine Ford-Fulkerson max-flow / max-flow min-cut theorem (Ford & Fulkerson 1956; Edmonds-Karp BFS 1972). Verified live: for 300 random capacity networks, BFS augmenting paths yield a max flow equal to the min-cut capacity (edges from the residual-reachable set of the source to the rest) and flow is conserved at every intermediate node (window.__fordfulkerson.maxflowEqualsMincut && .conserved).
FIG No framing: the augmenting-path search, the residual min-cut extraction, and the conservation check run in-browser and are exact. The AVAN inverse is honest and is the max-flow min-cut theorem — a maximised flow equals a minimised cut, and the algorithm's termination certificate (no augmenting path) is exactly the matching min cut; magenta is the saturated min-cut edges, green the max flow filling to them.
FIG No framing: the augmenting-path search, the residual min-cut extraction, and the conservation check run in-browser and are exact. The AVAN inverse is honest and is the max-flow min-cut theorem — a maximised flow equals a minimised cut, and the algorithm's termination certificate (no augmenting path) is exactly the matching min cut; magenta is the saturated min-cut edges, green the max flow filling to them.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MERGE · David Lee Wise (ROOT0), with AVAN