The minimum spanning tree of a weighted graph is a set of edges of minimum total weight which form a spanning
tree of the graph. When a graph is unweighted, any spanning
tree is a minimum spanning tree.
The minimum spanning tree can be found in polynomial time. Common algorithms include those due to Prim (1957) and Kruskal's algorithm
(Kruskal 1956). The problem can also be formulated using matroids
(Papadimitriou and Steiglitz 1982). A minimum spanning tree can be found in the Wolfram Language using the command FindSpanningTree[g].
The Season 1 episodes "Vector"
and "Man Hunt"
(2005) and Season
2 episode "Rampage"
(2006) of the television crime drama NUMB3RS feature minimal spanning trees.
Fredman, M. L. and Tarjan, R. E. "Fibonacci Heaps and Their Uses in Network Optimization." J. ACM34, 596-615,
1987.Graham, R. L. and Hell, P. "On the History of the Minimum
Spanning Tree Problem." Ann. History Comput.7, 43-57, 1985.Kruskal,
J. B. "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman
Problem." Proc. Amer. Math. Soc.7, 48-50, 1956.Papadimitriou,
C. H. and Steiglitz, K. Combinatorial
Optimization: Algorithms and Complexity. Englewood Cliffs, NJ: Prentice-Hall,
1982.Pemmaraju, S. and Skiena, S. "Minimum Spanning Trees."
§8.2 in Computational
Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge,
England: Cambridge University Press, pp. 335-336, 2003.Prim, R. C.
"Shortest Connection Networks and Some Generalizations." Bell System
Tech. J.36, 1389-1401, 1957.Skiena, S. "Minimum Spanning
Tree." §6.2 in Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, pp. 232-236, 1990.
