Minimum spanning tree

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 n-1 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
B-spline
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)