Please see github.com/anusha-murali for all of my repositories.
Motivating Problem
We can model the above problem as a graph:
A tree is connected, acyclic, and has $|V|-1$ edges (any two implies the third).
A spanning tree is a subgraph of a connected, undirected graph that includes all the vertices of the graph.
A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together without any cycles and with the minimum possible total edge weight.
An MST is a spanning tree whose sum of edge weights is as small as possible.
Example: In the following example, there is more than one MST. (Replace edge $(e, f)$ with $(c,e)$).
Properties of an MST
Building an MST
def genericMST(G, w)
A = []
while A does not form a spanning tree:
find an edge (u,v) that is safe for A
A.append({u,v})
return A
We can use the loop invariant to show that this generic algorithm works.
How to find a safe edge?
Consider an arbitrary edge $(u, v) \in E$. Let $S \subset V$ be any proper subset of vertices that includes $u$, but not $v$. In other words $v \in V - S$. In any MST, there has to be one edge (at least) that connects $S$ with $V-S$. Therefore, intuitively, we must choose the edge between $S$ and $V-S$ such that it has the minimum weight.
Let $A \in E$ a set that grows to become an MST (Please see the above function genericMST()
).
Cut Property: For any cut of a connected, undirected graph, the minimum weight edge that crosses the cut belongs to MST.
Theorem: Let $A$ be a subset of some MST, $(S, V - S)$ be a cut that respects $A$, and $(u, v)$ be a light edge crossing $(S, V-S)$. Then $(u,v)$ is safe for $A$.
Proof: Let $T$ be an MST that includes $A$.
If $T$ contains $(u, v)$, we’re done.
So, let’s assume that $T$ does not contain $(u,v)$. Construct a different MST $T’$ that includes $A \cup {(u,v)}$.
Recall: a tree has unique path between each pair of vertices. Since $T$ is an MST, it contains a unique path $p$ between $u$ and $v$. Path $p$ must cross the cut $(S, V-S)$ at least once. Let $(x, y)$ be an edge of $p$ that crosses the cut. From how we chose $(u,v)$, we know that $w(u,v) \leq w(x, y)$.
Since the cut respects $A$, edge $(x, y)$ is not in $A$.
To form $T’$ from $T$
So, $T’ = T - {(x,y)} \cup {(u,v)}$.
$T’$ is a spanning tree. It’s weight is $w(T’) = w(T) - w(x, y) + w(u,v) \leq w(T)$ since $w(u,v) \leq w(x,y)$.
Since $T’$ is a spanning tree, $w(T’) \leq w(T)$, and $T$ is an MST, then $T’$ must be an MST.
We will now show that $(u,v)$ is safe for $A$.
Two popular algorithms for finding MST in a graph are:
Data Structures and Algorithms Table of Contents