Minimum Spanning Tree

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.

REFERENCES

Fredman, M. L. and Tarjan, R. E. "Fibonacci Heaps and Their Uses in Network Optimization." J. ACM 34, 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.