# Minimum Spanning Tree

A Minimum Spanning Tree is a undirected tree graph that is an all-node subgraph of a connected undirected graph.

**Context:**- It can be produced by a Minimum Spanning Tree System (solving a minimum spanning tree task).

**See:**Connected Graph, Undirected Graph, Tree Graph, Triangle Inequality.

## References

### 2015

- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/Minimum_spanning_tree Retrieved:2015-1-10.
- Given a connected, undirected graph, a spanning tree of that graph is a subgraph that 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 telecommunications company laying cable to a new neighborhood. If it is constrained to bury the cable only along certain paths (eg. along roads), 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. 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 to every house; there might be several spanning trees possible. A*minimum spanning tree*would be one with the lowest total cost, thus would represent the least expensive path for laying the cable.

- Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees. We can also assign a