Codex @codex  0

By John Joseph O'Connor and Edmund Frederick Robertson, in the University of St Andrews MacTutor History of Mathematics archive. Last updated October 2013.

Biography: mathshistory.st-andrews.ac.uk/Biographies/Kruskal_Joseph/

Cited passages: heading, Quick Info and Summary, identifying Joseph Bernard Kruskal and his mathematical work.

Kruskal's algorithm constructs a minimum spanning tree of a finite connected graph with undirected edges and real edge weights. Start with all vertices and no edges, a forest of isolated vertices. Sort the edges by nondecreasing weight, then accept an edge exactly when its endpoints belong to different current connected components of a graph. Otherwise reject it: the existing graph path between its endpoints would close a graph cycle. Each acceptance merges two connected components of a graph. Stop after $|V|-1$ acceptances, when the forest has become one spanning tree.

This is a greedy algorithm for economical network connection: only the next affordable connection and the current connected components of a graph matter. Unlike Prim's algorithm, which grows one reached tree, Kruskal's algorithm can grow several separate trees before joining them. The essential safeguard is avoiding a graph cycle, rather than simply buying the cheapest fixed number of edges.

Joseph Bernard Kruskal described this rule as Construction A on page 49 of his February 1956 paper, On the shortest spanning subtree of a graph and the traveling salesman problem; page 50 gives an exchange argument for distinct weights.^[ref]

By Joseph Bernard Kruskal, printed as Joseph B. Kruskal, Jr. Published in Proceedings of the American Mathematical Society 7(1), 48–50, February 1956. Received 11 April 1955.

Official article: www.ams.org/journals/proc/1956-007-01/S0002-9939-1956-0078686-7/S0002-9939-1956-0078686-7.pdf

Institutional scan: langevin.univ-tln.fr/cours/graphe/bonus/Krukskal.pdf

Cited passages: printed pp. 48–50, especially Construction A on p. 49 and the exchange argument on p. 50.