
related topics 
{math, number, function} 
{rate, high, increase} 
{style, bgcolor, rowspan} 
{system, computer, user} 
{specie, animal, plant} 
{line, north, south} 
{build, building, house} 

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 (MST) 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 (not necessarily connected) has a minimum spanning forest, which is a union of minimum spanning trees for its connected components.
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.
Contents
Properties
Possible multiplicity
There may be several minimum spanning trees of the same weight having a minimum number of edges; in particular, if all the edge weights of a given graph are the same, then every spanning tree of that graph is minimum. If there are n vertices in the graph, then each tree has n1 edges.
Uniqueness
If each edge has a distinct weight then there will only be one, unique minimum spanning tree. This can be proved by induction or contradiction. This is true in many realistic situations, such as the cable TV company example above, where it's unlikely any two paths have exactly the same cost. This generalizes to spanning forests as well.
Full article ▸


related documents 
Parameter 
A* search algorithm 
Optimization (mathematics) 
Pseudorandom number generator 
Banach space 
Geometric series 
Associative array 
Document Type Definition 
Topological vector space 
Bspline 
Universal quantification 
Expander graph 
Algebraically closed field 
Stokes' theorem 
Normal space 
LL parser 
Free group 
Henri Lebesgue 
Partially ordered set 
Sheffer stroke 
Ordered pair 
Integer factorization 
Haskell (programming language) 
Graph theory 
Topology 
Net (mathematics) 
Line integral 
Knapsack problem 
Direct product 
NP (complexity) 
