Minimum spanning tree
|
|
Given a connected, undirected graph, a spanning tree of that graph is a subgraph which is a tree and connects all the vertices together. A single graph can have many different spanning trees. We can also assign a weight to each edge, which is a number representing how unfavorable it is, and use this to assign a weight to a spanning tree by computing the sum of the weights of the edges in that spanning tree. A minimum spanning tree or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree. More generally, any undirected graph has a minimum spanning forest.
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; these paths would be represented by edges with larger weights. 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. However, one theorem states that if each edge has a distinct weight, the minimum spanning tree is unique. This is true in many realistic situations, such as the one above, where it's unlikely any two paths have exactly the same cost. This generalizes to spanning forests as well.
| Contents |
Algorithms
The first algorithm for finding a minimum spanning tree was developed by Czech scientist Otakar Borůvka in 1926 (see Boruvka's algorithm). 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.
The fastest minimum spanning tree algorithm to date was developed by Bernard Chazelle, and based on Borůvka's. Its running time is O(m α(m,n)), where m is the number of edges, n refers to the number of vertices and α is the classical functional inverse of Ackermann function. The function α grows extremely slowly, so that for all practical purposes it may be considered a constant no greater than 4; thus Chazelle's algorithm takes very close to O(m) time.
What is the fastest possible algorithm for this problem? That is one of the oldest open questions in computer science. If the edge weights are integers with a bounded bit length, then deterministic algorithms are known with linear running time, O(m). For general weights, randomized algorithms are known that run in linear expected time. Whether there exists a deterministic algorithm with linear running time for general weights is still an open question.
MST on complete graphs
It has been shown by J. Michael Steele based on work by A. M. Frieze that given a complete graph on n vertices, with edge weights chosen from a continuous random distribution <math>f<math> such that <math>f'(0) > 0<math>, as n approaches infinity the size of the MST approaches <math>\zeta(3)/f'(0)<math>, where <math>\zeta<math> is the Riemann zeta function.
For uniform random weights in <math>[0,1]<math>, the exact expected size of the minimum spanning tree has been computed for small complete graphs.
| Vertices | Expected size |
|---|---|
| 2 | 1/2 |
| 3 | 3/4 |
| 4 | 31/35 |
| 5 | 893/924 |
| 6 | 278/273 |
| 7 | 30739/29172 |
| 8 | 199462271/184848378 |
| 9 | 126510063932/115228853025 |
Related problems
A related graph is the k-minimum spanning tree (k-MST) which is the tree that spans some subset of k vertices in the graph with minimum weight.
A geometrically related problem is the Euclidean minimum spanning tree.
References
- Otakar Boruvka on Minimum Spanning Tree Problem (translation of the both 1926 papers, comments, history) (2000) Jaroslav Nesetril, Eva Milková, Helena Nesetrilová (http://citeseer.ist.psu.edu/nesetril00otakar.html) (section 7 gives his algorithm, which looks like a cross between Prim's and Kruskal's)
- A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity (http://www.cs.princeton.edu/~chazelle/pubs.html), Bernard Chazelle, 1999
- [1] (http://www.mts.jhu.edu/~fill/papers/mst.pdf)