DAA HT23, Minimum spanning trees
Spanning trees
Why does every spanning tree have exactly $ \vert V \vert - 1$ edges?
- Every connected graph has at least $ \vert V \vert - 1$ edges
- Every acyclic graph has at most $ \vert V \vert - 1$ edges
Given a graph $G = (V, E)$, what is a spanning tree?
A connected, acyclic subgraph $T$ that includes all vertices of $V$.
Can you summarise Kruskal’s algorithm for creating minimum spanning trees?
Repeatedly pick edges with the smallest weights as long as they do not create cycles.
What’s the difficulty implementing Kruskal’s algorithm, and what data structure do we use to solve it?
Detecting whether adding an edge creates a cycle, disjoint-set data structure.
What is the running time of Kruskal’s algorithm when using a smart implementation of a collection of disjoint sets?
Quickly prove the cut lemma, i.e.
Suppose $G = (V, E)$, $A$ is a subset of some MST, $(S, V-S)$ is a cut that respects $A$, and $(u, v)$ is a light edge crossing the cut. Then $(u, v)$ is safe for $A$.
Suppose $G = (V, E)$, $A$ is a subset of some MST, $(S, V-S)$ is a cut that respects $A$, and $(u, v)$ is a light edge crossing the cut. Then $(u, v)$ is safe for $A$.
Let $T$ be an MST that includes $A$. Let $(x, y)$ be the edge in $T$ that crosses the cut and is on the simple path from $u$ to $v$. Consider $T’ = (T- \{(x, y)\}) \cup \{ (u, v)\}$. Then $T’$ is a spanning tree. Now
\[\begin{aligned} w(T') &= w(T) - w(x, y) + w(u, v) \\\\ &\le w(T) \end{aligned}\]Hence $T’$ is a MST. Also note $(x, y) \notin A$, so $T \supseteq A \implies T’ \supseteq A \cup \{(u, v)\}$.