Notes - 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?
Can you give pseudocode for the most generic minimum spanning tree algorithm?
GENERIC-MST(G, w):
A = empty
while A does not form a spanning tree
find an edge (u, v) safe for A
A += {(u, v)}
return A
Can you give pseudocode for Kruskal’s algorithm, assuming the existence of a disjoint-set data structure?
MST-KRUSKAL(G, w):
A = empty
for each vertex v in G.V:
MAKE-SET(v)
create a single list of edges in G.E
sort in increasing order by weight
for each edge (u, v) taken from the sorted list in order
if FIND-SET(u) != FIND-SET(v)
A += {(u, v)}
UNION(u, v)
return A
Can you summarise Prim’s algorithm for creating minimum spanning trees?
Repeatedly pick light edges connecting the current set of edges to the rest of the tree.
What is the running time of Prim’s algorithm?
Can you give pseudocode for Prim’s algorithm, also stating how the set $A$ is implicitly maintained?
MST-PRIM(G, w, r):
for each vertex u in G.V:
u.key = infinty
u.pi = null
r.key = 0
Q = empty
for each vertex u in G.V:
INSERT(Q, u)
while Q != empty:
u = EXTRACT-MIN(Q)
for each vertex v in G.Adj[u]:
if v in Q and w(u, v) < v.key:
v.pi = u
v.key = w(u, v)
DECREASE-KEY(Q, v, w(u, v))
And $A$, the actual MST is implicitly maintained by
\[A = \\{(v, v.\pi) : v \in V - \\{r\\} - Q\\}\]Cuts
What is a cut in relation to graphs?
A partition of the vertex set $V$ into two subsets $S$ and $V \backslash S$.
What does it mean for an edge $(u, v) \in E$ to cross a cut $(S, V \backslash S)$?
One endpoint is in $S$ and the other is in $V \backslash S$.
What does it mean for a cut to respect some subset $P$ of the edge set $E$?
No edge in $P$ crosses the cut.
What does it mean for an edge crossing a cut to be a “light edge”?
Its weight is minimum over all edges that cross the cut.
What does it mean for an edge $e$ to be “safe” for some subset $P \subseteq E$ of the edge set?
$P \cup \{e\}$ is a subset of some MST.
An edge $e$ is said to be “safe” for some subset $P \subseteq E$ of the edge set if $P \cup \{e\}$ is a subset of some MST. Given this, what is the Cut Lemma?
If $(S, V \backslash S)$ is a cut that respects $P \subseteq E$, and $e$ is a light edge crossing the cut, then $e$ is safe for $P$.
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)\}$.