Minimum spanning tree
and its minimum spanning tree.
≈ 13 min read
Minimum spanning tree. encyclopegia.org, snapshot enwiki-001371401929. /a/minimum-spanning-tree
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
and its minimum spanning tree. Each edge is labeled with its weight, which here is roughly proportional to its length. In graph theory, a minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components. There are many use cases for minimum spanning trees.
One example is a telecommunications company trying to lay cable in a new neighborhood. If it is constrained to bury the cable only along certain paths (e.g. roads), then there would be a graph containing the points (e.g. houses) connected by those paths.
Some of the 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. Currency is an acceptable unit for edge weight – there is no requirement for edge lengths to obey normal rules of geometry such as the triangle inequality.
A spanning tree for that graph would be a subset of those paths that has no cycles but still connects every house; there might be several spanning trees possible. A minimum spanning tree would be one with the lowest total cost, representing the least expensive path for laying the cable.
Possible multiplicity
If there are vertices in the graph, then each spanning tree has edges. There may be several minimum spanning trees of the same weight; in particular, if all the edge weights of a given graph are the same, then every spanning tree of that graph is minimum.
Uniqueness
If each edge has a distinct weight then there will be only one, unique minimum spanning tree. This is true in many realistic situations, such as the telecommunications company example above, where it's unlikely any two paths have exactly the same cost. This generalizes to spanning forests as well.
Proof: Assume the contrary, that there are two different MSTs and . Since and differ despite containing the same nodes, there is at least one edge that belongs to one but not the other. Among such edges, let be the one with least weight; this choice is unique because the edge weights are all distinct.
Without loss of generality, assume is in . As is an MST, must contain a cycle with . As a tree, contains no cycles, therefore must have an edge that is not in .
Since was chosen as the unique lowest-weight edge among those belonging to exactly one of and , the weight of must be greater than the weight of . As and are part of the cycle , replacing with in therefore yields a spanning tree with a smaller weight. This contradicts the assumption that is an MST.
More generally, if the edge weights are not all distinct then only the (multi-)set of weights in minimum spanning trees is certain to be unique; it is the same for all minimum spanning trees.
Minimum-cost subgraph
If the weights are positive, then a minimum spanning tree is, in fact, a minimum-cost subgraph connecting all vertices, since if a subgraph contains a cycle, removing any edge along that cycle will decrease its cost and preserve connectivity.
Cycle property
For any cycle in the graph, if the weight of an edge of is larger than any of the individual weights of all other edges of , then this edge cannot belong to an MST. Proof: Assume the contrary, i.e. that belongs to an MST . Then deleting will break into two subtrees with the two ends of in different subtrees.
The remainder of reconnects the subtrees, hence there is an edge of with ends in different subtrees, i.e., it reconnects the subtrees into a tree with weight less than that of , because the weight of is less than the weight of .
Cut property
For any cut of the graph, if the weight of an edge in the cut-set of is strictly smaller than the weights of all other edges of the cut-set of , then this edge belongs to all MSTs of the graph. Proof: Assume that there is an MST that does not contain . Adding to will produce a cycle, that crosses the cut once at and crosses back at another edge .
Deleting we get a spanning tree of strictly smaller weight than . This contradicts the assumption that was a MST. By a similar argument, if more than one edge is of minimum weight across a cut, then each such edge is contained in some minimum spanning tree.
Minimum-cost edge
If the minimum cost edge of a graph is unique, then this edge is included in any MST. Proof: if was not included in the MST, removing any of the (larger cost) edges in the cycle formed after adding to the MST, would yield a spanning tree of smaller weight.
Contraction
If is a tree of MST edges, then we can contract into a single vertex while maintaining the invariant that the MST of the contracted graph plus gives the MST for the graph before contraction.
Algorithms
In all of the algorithms below, is the number of edges in the graph and is the number of vertices. {(r^4)}^{(2^{r^2})} = r^{2^{(r^2+2)}}. B. Identifying the correct DTs To check if a DT is correct, it should be checked on all possible permutations of the edge weights. The number of such permutations is at most .
For each permutation, solve the MST problem on the given graph using any existing algorithm, and compare the result to the answer given by the DT. The running time of any MST algorithm is at most , so the total time required to check all permutations is at most .
Hence, the total time required for finding an optimal DT for all graphs with vertices is: 2^{r \choose 2} \cdot r^{2^{(r^2+2)}} \cdot (r^2+1)!, which is less than 2^{2^{r^2+o(r)}}.
MST on complete graphs with random weights
Alan M. Frieze showed that given a complete graph on n vertices, with edge weights that are independent identically distributed random variables with distribution function F satisfying F'(0) > 0 , then as n approaches +∞ the expected weight of the MST approaches \zeta(3)/F'(0) , where \zeta is the Riemann zeta function (more specifically is \zeta(3) Apéry's constant). Frieze and Steele also proved convergence in probability.
Svante Janson proved a central limit theorem for weight of the MST. For uniform random weights in [0,1] , the exact expected size of the minimum spanning tree has been computed for small complete graphs.
If the fractions f(e) are forced to be in {0,1}, then the set T of edges with f(e)=1 are a spanning set, as every node or subset of nodes is connected to the rest of the graph by at least one edge of T. Moreover, if f minimizes \sum_{e\in E} f(e)\cdot w(e) , then the resulting spanning set is necessarily a tree, since if it contained a cycle, then an edge could be removed without affecting the spanning condition. So the minimum fractional spanning set problem is a relaxation of the MST problem, and can also be called the fractional MST problem.
The fractional MST problem can be solved in polynomial time using the ellipsoid method. However, if we add a requirement that f(e) must be half-integer (that is, f(e) must be in {0, 1/2, 1}), then the problem becomes NP-hard, since it includes as a special case the Hamiltonian cycle problem: in an n -vertex unweighted graph, a half-integer MST of weight n/2 can only be obtained by assigning weight 1/2 to each edge of a Hamiltonian cycle.
Other variants
The Steiner tree of a subset of the vertices is the minimum tree that spans the given subset. Finding the Steiner tree is NP-complete. The k-minimum spanning tree (k-MST) is the tree that spans some subset of k vertices in the graph with minimum weight.
A set of k-smallest spanning trees is a subset of k spanning trees (out of all possible spanning trees) such that no spanning tree outside the subset has smaller weight. (Note that this problem is unrelated to the k-minimum spanning tree.)
The Euclidean minimum spanning tree is a spanning tree of a graph with edge weights corresponding to the Euclidean distance between vertices which are points in the plane (or space). The rectilinear minimum spanning tree is a spanning tree of a graph with edge weights corresponding to the rectilinear distance between vertices which are points in the plane (or space).
The distributed minimum spanning tree is an extension of MST to the distributed model, where each node is considered a computer and no node knows anything except its own connected links. The mathematical definition of the problem is the same but there are different approaches for a solution.
The capacitated minimum spanning tree is a tree that has a marked node (origin, or root) and each of the subtrees attached to the node contains no more than c nodes. c is called a tree capacity. Solving CMST optimally is NP-hard, but good heuristics such as Esau-Williams and Sharma produce solutions close to optimal in polynomial time.
The degree-constrained minimum spanning tree is a MST in which each vertex is connected to no more than d other vertices, for some given number d. The case d = 2 is a special case of the traveling salesman problem, so the degree constrained minimum spanning tree is NP-hard in general. An arborescence is a variant of MST for directed graphs.
It can be solved in O(E + V \log V) time using the Chu–Liu/Edmonds algorithm. A maximum spanning tree is a spanning tree with weight greater than or equal to the weight of every other spanning tree. Such a tree can be found with algorithms such as Prim's or Kruskal's after multiplying the edge weights by −1 and solving the MST problem on the new graph.
A path in the maximum spanning tree is the widest path in the graph between its two endpoints: among all possible paths, it maximizes the weight of the minimum-weight edge. Maximum spanning trees find applications in parsing algorithms for natural languages and in training algorithms for conditional random fields.
The ultrametric backbone is the smallest possible distance backbone of positive weighted directed and undirected graphs. The ultrametric backbone is the union of minimum spanning forests in undirected (positive weight) graphs and provides a generalization of minimum spanning trees to directed graphs that, unlike minimum equivalent graphs and minimum spanning arborescences, preserves all max-min shortest paths and De Morgan's law consistency.
The dynamic MST problem concerns the update of a previously computed MST after an edge weight change in the original graph or the insertion/deletion of a vertex. The minimum labeling spanning tree problem is to find a spanning tree with least types of labels if each edge in a graph is associated with a label from a finite label set instead of a weight.
A bottleneck edge is the highest weighted edge in a spanning tree. A spanning tree is a minimum bottleneck spanning tree (or MBST) if the graph does not contain a spanning tree with a smaller bottleneck edge weight. A MST is necessarily a MBST ( by the cut property), but a MBST is not necessarily a MST.
A minimum-cost spanning tree game is a cooperative game in which the players have to share among them the costs of constructing the optimal spanning tree. The optimal network design problem is the problem of computing a set, subject to a budget constraint, which contains a spanning tree, such that the sum of shortest paths between every pair of nodes is as small as possible.
Applications
Minimum spanning trees have direct applications in the design of networks, including computer networks, telecommunications networks, transportation networks, water supply networks, and electrical grids (which they were first invented for, as mentioned above). They are invoked as subroutines in algorithms for other problems, including the Christofides algorithm for approximating the traveling salesman problem, approximating the multi-terminal minimum cut problem (which is equivalent in the single-terminal case to the maximum flow problem), and approximating the minimum-cost weighted perfect matching.
Other practical applications based on minimal spanning trees include: Taxonomy. Cluster analysis: clustering points in the plane, single-linkage clustering (a method of hierarchical clustering), graph-theoretic clustering, and clustering gene expression data. Constructing trees for broadcasting in computer networks.
Image registration and segmentation – see minimum spanning tree-based segmentation. Curvilinear feature extraction in computer vision. Handwriting recognition of mathematical expressions.
Circuit design: implementing efficient multiple constant multiplications, as used in finite impulse response filters. Regionalisation of socio-geographic areas, the grouping of areas into homogeneous, contiguous regions. Comparing ecotoxicology data.
Topological observability in power systems. Measuring homogeneity of two-dimensional materials. Minimax process control.
Minimum spanning trees can also be used to describe financial markets. A correlation matrix can be created by calculating a coefficient of correlation between any two stocks. This matrix can be represented topologically as a complex network and a minimum spanning tree can be constructed to visualize relationships.
Further reading
Otakar Boruvka on Minimum Spanning Tree Problem (translation of both 1926 papers, comments, history) (2000) Jaroslav Nešetřil, Eva Milková, Helena Nesetrilová. (Section 7 gives his algorithm, which looks like a cross between Prim's and Kruskal's.) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition.
MIT Press and McGraw-Hill, 2001. . Chapter 23: Minimum Spanning Trees, pp. 561–579. Eisner, Jason (1997).
State-of-the-art algorithms for minimum spanning trees: A tutorial discussion. Manuscript, University of Pennsylvania, April. 78 pp. Kromkowski, John David.
"Still Unmelted after All These Years", in Annual Editions, Race and Ethnic Relations, 17/e (2009 McGraw Hill) (Using minimum spanning tree as method of demographic analysis of ethnic diversity across the United States).
External links
Implemented in BGL, the Boost Graph Library The Stony Brook Algorithm Repository - Minimum Spanning Tree codes Implemented in QuickGraph for .Net
Text derived from https://en.wikipedia.org/w/index.php?oldid=1371401929 under CC BY-SA 4.0; modifications have been made.