minimum spanning tree
   HOME

TheInfoList



OR:

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 In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is no ...
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 In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side. This statement permits the inclusion of Degeneracy (mathematics)#T ...
. 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.


Properties


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.


Classic algorithms

The first algorithm for finding a minimum spanning tree was developed by Czech scientist Otakar Borůvka in 1926 (see Borůvka's algorithm). Its purpose was an efficient electrical coverage of
Moravia Moravia ( ; ) is a historical region in the eastern Czech Republic, roughly encompassing its territory within the Danube River's drainage basin. It is one of three historical Czech lands, with Bohemia and Czech Silesia. The medieval and early ...
. The algorithm proceeds in a sequence of stages. In each stage, called ''Boruvka step'', it identifies a forest consisting of the minimum-weight edge incident to each vertex in the graph , then forms the graph as the input to the next step. Here denotes the graph derived from by contracting edges in (by the Cut property, these edges belong to the MST). Each Boruvka step takes linear time. Since the number of vertices is reduced by at least half in each step, Boruvka's algorithm takes time. A second algorithm is Prim's algorithm, which was invented by Vojtěch Jarník in 1930 and rediscovered by Prim in 1957 and Dijkstra in 1959. Basically, it grows the MST () one edge at a time. Initially, contains an arbitrary vertex. In each step, is augmented with a least-weight edge such that is in and is not yet in . By the Cut property, all edges added to are in the MST. Its run-time is either or , depending on the data-structures used. A third algorithm commonly in use is Kruskal's algorithm, which also takes time. A fourth algorithm, not as commonly used, is the reverse-delete algorithm, which is the reverse of Kruskal's algorithm. Its runtime is . All four of these are greedy algorithms. Since they run in polynomial time, the problem of finding such trees is in FP, and related
decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
s such as determining whether a particular edge is in the MST or determining if the minimum total weight exceeds a certain value are in P.


Faster algorithms

Several researchers have tried to find more computationally-efficient algorithms. In a comparison model, in which the only allowed operations on edge weights are pairwise comparisons, found a linear time randomized algorithm based on a combination of Borůvka's algorithm and the reverse-delete algorithm. The fastest non-randomized comparison-based algorithm with known complexity, by Bernard Chazelle, is based on the soft heap, an approximate priority queue.. Its running time is , where is the classical functional inverse of the 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 linear time.


Linear-time algorithms in special cases


Dense graphs

If the graph is dense (i.e. , then a deterministic algorithm by Fredman and Tarjan finds the MST in time . The algorithm executes a number of phases. Each phase executes Prim's algorithm many times, each for a limited number of steps. The run-time of each phase is . If the number of vertices before a phase is , the number of vertices remaining after a phase is at most \tfrac. Hence, at most phases are needed, which gives a linear run-time for dense graphs. There are other algorithms that work in linear time on dense graphs.


Integer weights

If the edge weights are integers represented in binary, then deterministic algorithms are known that solve the problem in integer operations. Whether the problem can be solved ''deterministically'' for a ''general graph'' in ''linear time'' by a comparison-based algorithm remains an open question.


Decision trees

Given graph where the nodes and edges are fixed but the weights are unknown, it is possible to construct a binary
decision tree A decision tree is a decision support system, decision support recursive partitioning structure that uses a Tree (graph theory), tree-like Causal model, model of decisions and their possible consequences, including probability, chance event ou ...
(DT) for calculating the MST for any permutation of weights. Each internal node of the DT contains a comparison between two edges, e.g. "Is the weight of the edge between and larger than the weight of the edge between and ?". The two children of the node correspond to the two possible answers "yes" or "no". In each leaf of the DT, there is a list of edges from that correspond to an MST. The runtime complexity of a DT is the largest number of queries required to find the MST, which is just the depth of the DT. A DT for a graph is called ''optimal'' if it has the smallest depth of all correct DTs for . For every integer , it is possible to find optimal decision trees for all graphs on vertices by
brute-force search In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of Iteration#Computing, systematically checking all possible candida ...
. This search proceeds in two steps. A. Generating all potential DTs * There are 2^ different graphs on vertices. * For each graph, an MST can always be found using comparisons, e.g. by Prim's algorithm. * Hence, the depth of an optimal DT is less than . * Hence, the number of internal nodes in an optimal DT is less than 2^. * Every internal node compares two edges. The number of edges is at most so the different number of comparisons is at most . * Hence, the number of potential DTs is less than ^ = r^. 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^ \cdot r^ \cdot (r^2+1)!, which is less than :2^.


Optimal algorithm

Seth Pettie and Vijaya Ramachandran have found a optimal deterministic comparison-based minimum spanning tree algorithm.. The following is a simplified description of the algorithm. # Let , where is the number of vertices. Find all optimal decision trees on vertices. This can be done in time (see Decision trees above). # Partition the graph to components with at most vertices in each component. This partition uses a soft heap, which "corrupts" a small number of the edges of the graph. # Use the optimal decision trees to find an MST for the uncorrupted subgraph within each component. # Contract each connected component spanned by the MSTs to a single vertex, and apply any algorithm which works on dense graphs in time to the contraction of the uncorrupted subgraph # Add back the corrupted edges to the resulting forest to form a subgraph guaranteed to contain the minimum spanning tree, and smaller by a constant factor than the starting graph. Apply the optimal algorithm recursively to this graph. The runtime of all steps in the algorithm is , ''except for the step of using the decision trees''. The runtime of this step is unknown, but it has been proved that it is optimal - no algorithm can do better than the optimal decision tree. Thus, this algorithm has the peculiar property that it is '' optimal'' although its runtime complexity is ''unknown''.


Parallel and distributed algorithms

Research has also considered parallel algorithms for the minimum spanning tree problem. With a linear number of processors it is possible to solve the problem in time. The problem can also be approached in a distributed manner. If each node is considered a computer and no node knows anything except its own connected links, one can still calculate the distributed minimum spanning tree.


MST on complete graphs with random weights

Alan M. Frieze showed that given a
complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...
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 In probability theory, the central limit theorem (CLT) states that, under appropriate conditions, the Probability distribution, distribution of a normalized version of the sample mean converges to a Normal distribution#Standard normal distributi ...
for weight of the MST. For uniform random weights in ,1/math>, the exact expected size of the minimum spanning tree has been computed for small complete graphs.


Fractional variant

There is a fractional variant of the MST, in which each edge is allowed to appear "fractionally". Formally, a fractional spanning set of a graph (V,E) is a nonnegative function ''f'' on ''E'' such that, for every non-trivial subset ''W'' of ''V'' (i.e., ''W'' is neither empty nor equal to ''V''), the sum of ''f''(''e'') over all edges connecting a node of ''W'' with a node of ''V''\''W'' is at least 1. Intuitively, ''f''(''e'') represents the fraction of e that is contained in the spanning set. A minimum fractional spanning set is a fractional spanning set for which the sum \sum_ f(e)\cdot w(e) is as small as possible. If the fractions ''f''(''e'') are forced to be in , 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_ 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 In mathematical optimization, the ellipsoid method is an iterative method for convex optimization, minimizing convex functions over convex sets. The ellipsoid method generates a sequence of ellipsoids whose volume uniformly decreases at every ste ...
. However, if we add a requirement that ''f''(''e'') must be half-integer (that is, ''f''(''e'') must be in ), then the problem becomes
NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
, 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 In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...
. * 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 In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
, 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 In the theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exac ...
, so the degree constrained minimum spanning tree is
NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
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 Parsing, syntax analysis, or syntactic analysis is a process of analyzing a String (computer science), string of Symbol (formal), symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal gramm ...
algorithms for natural languages and in training algorithms for conditional random fields. * 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 network A computer network is a collection of communicating computers and other devices, such as printers and smart phones. In order to communicate, the computers and devices must be connected by wired media like copper cables, optical fibers, or b ...
s,
telecommunications network A telecommunications network is a group of Node (networking), nodes interconnected by telecommunications links that are used to exchange messages between the nodes. The links may use a variety of technologies based on the methodologies of circuit ...
s, transportation networks,
water supply network A water supply network or water supply system is a system of engineered hydrologic and hydraulic components that provide water supply. A water supply system typically includes the following: # A drainage basin (see water purification – sour ...
s, and
electrical grid An electrical grid (or electricity network) is an interconnected network for electricity delivery from producers to consumers. Electrical grids consist of power stations, electrical substations to step voltage up or down, electric power tran ...
s (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 In the theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exac ...
, 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 image:Hierarchical clustering diagram.png, 280px, Generalized scheme of taxonomy Taxonomy is a practice and science concerned with classification or categorization. Typically, there are two parts to it: the development of an underlying scheme o ...
. *
Cluster analysis Cluster analysis or clustering is the data analyzing technique in which task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more Similarity measure, similar (in some specific sense defined by the ...
: clustering points in the plane, single-linkage clustering (a method of hierarchical clustering), graph-theoretic clustering, and clustering
gene expression Gene expression is the process (including its Regulation of gene expression, regulation) by which information from a gene is used in the synthesis of a functional gene product that enables it to produce end products, proteins or non-coding RNA, ...
data. * Constructing trees for
broadcasting Broadcasting is the data distribution, distribution of sound, audio audiovisual content to dispersed audiences via a electronic medium (communication), mass communications medium, typically one using the electromagnetic spectrum (radio waves), ...
in computer networks. * Image registration and segmentation – see minimum spanning tree-based segmentation. * Curvilinear
feature extraction Feature may refer to: Computing * Feature recognition, could be a hole, pocket, or notch * Feature (computer vision), could be an edge, corner or blob * Feature (machine learning), in statistics: individual measurable properties of the phenome ...
in
computer vision Computer vision tasks include methods for image sensor, acquiring, Image processing, processing, Image analysis, analyzing, and understanding digital images, and extraction of high-dimensional data from the real world in order to produce numerical ...
. *
Handwriting recognition Handwriting recognition (HWR), also known as handwritten text recognition (HTR), is the ability of a computer to receive and interpret intelligible handwriting, handwritten input from sources such as paper documents, photographs, touch-screens ...
of mathematical expressions. *
Circuit design In electrical engineering, the process of circuit design can cover systems ranging from complex electronic systems down to the individual transistors within an integrated circuit. One person can often do the design process without needing a pl ...
: implementing efficient multiple constant multiplications, as used in
finite impulse response In signal processing, a finite impulse response (FIR) filter is a filter whose impulse response (or response to any finite length input) is of ''finite'' duration, because it settles to zero in finite time. This is in contrast to infinite impuls ...
filters. *
Regionalisation Regionalisation is the tendency to form Decentralization, decentralised regions. Regionalisation or land classification can be observed in various disciplines: *In agriculture, see Agricultural Land Classification. *In biogeography, see Biogeog ...
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 Industrial process control (IPC) or simply process control is a system used in modern manufacturing which uses the principles of control theory and physical industrial control systems to monitor, control and optimize continuous Industrial processe ...
. * Minimum spanning trees can also be used to describe financial markets.Djauhari, M., & Gan, S. (2015)
Optimality problem of network topology in stocks market analysis
Physica A: Statistical Mechanics and Its Applications, 419, 108–114.
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.


References


Further reading



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 ''Introduction to Algorithms'' is a book on computer programming by Thomas H. Cormen, Charles E. Leiserson, Ron Rivest, Ronald L. Rivest, and Clifford Stein. The book is described by its publisher as "the leading algorithms text in universities w ...
'', 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

{{commons category, Minimum spanning trees


The Stony Brook Algorithm Repository - Minimum Spanning Tree codes

Implemented in QuickGraph for .Net
Spanning tree Polynomial-time problems