Minimum Spanning Trees

Spanning Tree Definition #

A spanning tree $T$ is a subgraph of a graph $G$ where $T$:

• Is connected (there’s a path to every vertex)
• Is acyclic (no cycles)
• Includes every vertex (spanning property)

Notice: the first two properties defines a tree structure, and the last property makes the tree spanning.

A minimum spanning tree is a spanning tree with minimum total edge weight.

Example: I want to connect an entire town with wiring and would like to find the optimal wiring connection that connects everyone but uses the least wire.

MST vs. Shortest Path Tree #

In contrast to a shortest path tree, which is essentially the solution tree to running Dijkstra’s with root node = source vertex, a MST has no source. However, it is possible for the MST to be the same as the SPT.

We can think of the MST as a global property for the entire graph, as opposed to SPT which depends on which node is the source node.

If the edges of the graph are not unique, there’s a chance that the MST is not unique.

Cuts Property #

• A cut is defined as assigning the nodes in a graph into two sets.
• A crossing edge is an edge that connects two nodes that are in different sets
• The smallest crossing edge is the crossing edge with smallest weight

The Cut Property states that the smallest crossing edge is always going to be in the MST, no matter how the cut is made.