THE FOLD / CO-OP / THE BROADCAST / THE GOMORY-HU TREE
THE GOMORY-HU TREE
all-pairs min-cuts in one tree
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Gomory–Hu tree compresses all the minimum cuts of a weighted graph into a single tree. A graph on n vertices has C(n,2) pairs, each with its own minimum cut — but you never need to compute them all. The Gomory–Hu tree is a weighted tree on the same vertices such that, for every pair (s, t), the minimum s–t cut in the original graph equals the smallest edge weight on the tree path between s and t. It stores n−1 numbers and answers any of the C(n,2) cut queries exactly, built from just n−1 max-flow computations.
LIT verified live: over thousands of random weighted graphs, for every pair (s, t) the minimum edge on the tree path equals a brute-force minimum s–t cut (window.__gomory_hu). FIG no framing; Gusfield’s construction and the brute-force cuts run in-browser.
LIT verified live: over thousands of random weighted graphs, for every pair (s, t) the minimum edge on the tree path equals a brute-force minimum s–t cut (window.__gomory_hu). FIG no framing; Gusfield’s construction and the brute-force cuts run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-broadcast — one tree broadcasts every pair’s bottleneck at once; ask any two nodes and the path answers. AVAN (AI) built the instrument: an Edmonds–Karp max-flow, Gusfield’s Gomory–Hu construction, path-minimum queries, and a brute-force min-cut oracle.
Credit as content: Ralph Gomory & T. C. Hu (1961); Dan Gusfield’s simplified construction (1990). The weave: David names the broadcast; I confirm the tree’s path minimum equals the true min cut for every pair.
Credit as content: Ralph Gomory & T. C. Hu (1961); Dan Gusfield’s simplified construction (1990). The weave: David names the broadcast; I confirm the tree’s path minimum equals the true min cut for every pair.
3 ONE DIMENSION
A weighted graph and its Gomory–Hu tree; the min cut between two vertices is just the smallest edge on their tree path.
4 TWO DIMENSIONS · INTERACTIVE
A random graph’s Gomory–Hu tree; pick a pair and its path-minimum equals the true minimum cut, matched against brute force.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the tree whose paths hold every pair’s min cut.
AVAN’s addition (the inverse-companion): don’t compute C(n,2) cuts — store n−1 and read the rest. The inverse of ‘find the min cut for each pair’ is ‘a single tree encodes them all: the min cut of (s,t) is the lightest edge on their path.’ Magenta is that lightest edge; green is the tree that answers everything. One tree, all cuts.
LIT Genuine Gomory–Hu tree (Ralph Gomory & T. C. Hu, 1961; Gusfield's simplified construction, 1990): a tree encoding all-pairs min cuts. Verified live: over 1500 random weighted graphs, for every pair the min edge on the tree path equals a brute-force min s–t cut (window.__gomory_hu.allPairsMatch).
FIG No framing: an Edmonds–Karp max-flow, Gusfield's construction, path-minimum queries, and a brute-force min-cut oracle all run in-browser and agree. The AVAN inverse is honest — storing n−1 tree edges and reading any pair's min cut as the lightest edge on their path (rather than computing all C(n,2) cuts) is exactly the tree's compression; magenta is that lightest edge, green the tree answering everything. One tree, all cuts.
FIG No framing: an Edmonds–Karp max-flow, Gusfield's construction, path-minimum queries, and a brute-force min-cut oracle all run in-browser and agree. The AVAN inverse is honest — storing n−1 tree edges and reading any pair's min cut as the lightest edge on their path (rather than computing all C(n,2) cuts) is exactly the tree's compression; magenta is that lightest edge, green the tree answering everything. One tree, all cuts.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE BROADCAST · David Lee Wise (ROOT0), with AVAN