Minimum Spanning Tree
When finding spanning trees of a graph, we may be interested in those where the total edge weight is minimal among all the possible spanning trees, a so-called minimum weight spanning tree (MST).
A minimum spanning tree of a weighted graph $G$ is a spanning tree of it with the minimum possible total edge weight.
Consider the following weighted graph:
![](/img/29/graph04.png)
Every tree below is a minimum spanning tree of the graph above.
![](/img/29/graph05.png)
As can be seen, an MST is not necessarily unique. There may be several minimum spanning trees of the same total weight. However, if each edge has a distinct weight, there will be only one unique minimum spanning tree.
Minimum Spanning Tree Problem
Given a connected, undirected weighted graph $G = (V, E, w)$, the minimum (weight) spanning tree problem requires finding a spanning tree of minimum weight, where the weight of a tree $T$ is defined as the sum of the wight of all its edges:
$$ w(T) = \sum_{e \in E(T)} w(e) $$
We will look at two algorithms to solve the MST problem:
- Prim's Algorithm
- Kruskal's Algorithm
Resources
- Wikipedia's entry on Minimum Spanning Tree.