THE FOLD / CO-OP / THE MERGE / THE SPANNING TREE
THE SPANNING TREE
Kruskal — cheapest wiring, no loops, provably optimal
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The minimum spanning tree. Connect a set of nodes — cities, pins on a board, cluster points — with the cheapest total wiring that still reaches everything, and no wasteful loops. Kruskal’s algorithm (1956) is pure greed and it works perfectly: sort every edge cheapest-first, and add each one unless it would form a cycle (its two endpoints are already connected). Stop when all nodes are joined.
The cycle check is the clever part — a union-find structure that answers ‘are these two already in the same piece?’ almost instantly, merging pieces as edges are added. Greedy-cheapest-first is provably optimal here (the matroid property): taking the locally cheapest safe edge always leads to the globally minimum tree.
LIT verified live: over 5,000 random connected graphs Kruskal’s tree has the same total weight as Prim’s independent algorithm, spans all n nodes, and uses exactly n−1 edges (window.__mst.matchesPrim && spans). FIG no framing; the greedy rule, the union-find cycle test, and the proven minimality are exact.
The cycle check is the clever part — a union-find structure that answers ‘are these two already in the same piece?’ almost instantly, merging pieces as edges are added. Greedy-cheapest-first is provably optimal here (the matroid property): taking the locally cheapest safe edge always leads to the globally minimum tree.
LIT verified live: over 5,000 random connected graphs Kruskal’s tree has the same total weight as Prim’s independent algorithm, spans all n nodes, and uses exactly n−1 edges (window.__mst.matchesPrim && spans). FIG no framing; the greedy rule, the union-find cycle test, and the proven minimality are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE MERGE, beside THE MAJORITY — the co-op domain of many becoming one. Kruskal is literal merging: scattered nodes are separate islands, and each accepted edge fuses two islands until a single connected whole remains. AVAN (AI) built the instrument: the sorted edges, the union-find merge, the Prim cross-check.
The weave: David names the seat (islands merging into one); I make the greedy build visible and the optimality checkable — sorted edges in 1D, the live merge in 2D, the tree forming in 3D. The sphere is the seam. Credit: Joseph Kruskal (1956); Otakar Borůvka (1926) earlier.
The weave: David names the seat (islands merging into one); I make the greedy build visible and the optimality checkable — sorted edges in 1D, the live merge in 2D, the tree forming in 3D. The sphere is the seam. Credit: Joseph Kruskal (1956); Otakar Borůvka (1926) earlier.
3 ONE DIMENSION
Edges sorted cheapest-first. Walk the list and keep each edge unless it closes a loop; the kept ones (bright) are the tree, the skipped ones (dim) would have been redundant. Greed, taken in the right order, is optimal.
4 TWO DIMENSIONS · INTERACTIVE
Step through Kruskal: the cheapest remaining edge is tested — if it joins two different components (shown by colour) it is added and they merge; if both ends are already connected it is skipped. The total weight matches Prim’s exactly.
5 THREE DIMENSIONS + AVAN’S INVERSE
The nodes turning in space, the tree edges forming between them — green, the growing skeleton.
AVAN’s addition (the inverse-companion): the magenta edges are the chosen tree; every other possible edge is left dark. A graph has exponentially many spanning trees — searching them all is hopeless. Kruskal is the inverse: it never searches the space of trees at all. It makes a sequence of locally cheapest safe choices and trusts that avoiding cycles is enough — and a theorem guarantees the local greed lands on the global optimum. The union-find turns a global ‘does this make a loop?’ into a local merge. Global best from local thrift, no lookahead required — the green is the islands fusing, the magenta is the one cheapest skeleton that no exhaustive search could beat.
LIT Genuine Kruskal MST (Joseph Kruskal, 1956; Boruvka 1926 earlier). Verified live: over 5,000 random connected graphs Kruskal's tree has the same total weight as Prim's independent algorithm, spans all n nodes, and uses exactly n-1 edges (window.__mst.matchesPrim && spans, both true). The greedy rule, the union-find cycle test, and the proven global minimality from local choices are exact.
FIG No metaphor is doing the work: the greedy edge selection, the union-find cycle check, and the minimality (cross-checked against Prim) are all real. That local greed yields the global optimum is a genuine theorem (matroid), demonstrated by the Kruskal==Prim agreement.
FIG No metaphor is doing the work: the greedy edge selection, the union-find cycle check, and the minimality (cross-checked against Prim) are all real. That local greed yields the global optimum is a genuine theorem (matroid), demonstrated by the Kruskal==Prim agreement.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MERGE · David Lee Wise (ROOT0), with AVAN