DAA HT23, 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)$, @Define 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?
@State 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
@State 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?
@State 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 = infinity
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
@Define a cut in relation to graphs.
A partition of the vertex set $V$ into two subsets $S$ and $V \backslash S$.
@Define what it means 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$.
@Define what it means for a cut to respect some subset $P$ of the edge set $E$.
No edge in $P$ crosses the cut.
@Define what it means for an edge crossing a cut to be a “light edge”.
Its weight is minimum over all edges that cross the cut.
@Define what it means 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, @State 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$.
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)\}$.