Minimum spanning tree

A minimum spanning tree is a tree formed from a subset of the edges in a given graph, with two properties:

• It spans the graph - it includes every vertex in the graph
• It is a minimum - the total weight of all the edges is as low as possible

One example would be a cable TV company laying cable to a new neighborhood. If it is constrained to bury the cable only along certain paths, then there would be a graph representing which points are connected by those paths. Some of those paths might be more expensive, because they are longer, or require the cable to be buried deeper. A spanning tree for that graph would be a subset of those paths that has no cycles but still connects to every house. There might be several spanning trees possible. A minimum spanning tree would be one with the lowest total cost. In case of a tie, there could be several minimum spanning trees.

The first algorithm for finding a minimum spanning tree was developed by Czech scientist Otakar Boruvka in 1926. Its purpose was an efficient electrical coverage of Bohemia. There are now two algorithms commonly used, Prim's algorithm and Kruskal's algorithm. Both are greedy algorithms. Both run in polynomial time, so the problem of finding such trees is in P.

References

• Otakar Boruvka on Minimum Spanning Tree Problem (translation of the both 1926 papers, comments, history) (2000) Jaroslav Nesetril, Eva Milková, Helena Nesetrilová (section 7 gives his algorithm, which looks like a cross between Prim's and Kruskal's)