Materials

The raw L13 slides (pdf) and here are Monday’s annotated slides.

Topics

• Minimum Spanning Tree
  • Kruskal’s algorithm
  • The Cut theorem
  • Prim’s algorithm
  • Binary heaps

The Cut Theorem

Let $G=(V,E)$ be a graph, let $A$ be a set of edges that is part of some minimum spanning tree $A\subseteq T$ for $G$, and let $(S,V-S)$ be some cut that $A$ respects. Let $e=(u,v)$ be the lightest edge that crosses the cut $S$. Then $A\union {e}$ is part of some minimum spanning tree of $G$.

To prove this theorem, we start with the observation that if $A\union{e}$ is already part of $T$, then the theorem holds.

Otherwise, we construct a new tree $T’$ such that $A\union{e} \subseteq T’$ and $T’$ is also a minimum spanning tree of graph $G$.

To do so, lets add the edge $e$ to the tree $T$. Because $T$ is a minimum spanning tree, this means that $T$ already connects nodes $u$ and $v$, and therefore, adding the edge $e=(u,v)$ creates a cycle $u,v,\ldots,u$. Since $e$ crosses $S$, then $u\in S$, and $v\not\in S$, and furthermore, since $A$ respects $S$, then none of the edges in $A$ have one endpoint in $S$ and another in $V-S$.

Now consider the heaviest edge $e’$ along the cycle $u,v,\ldots,u$ that crosses the cut $S$.

Now consider the tree $T’=(T \cup {e}) - {e’}$. Note that $w(T’)\leq w(T)$ because $w(e) \leq w(e’)$ because $e’$ is the heaviest edge on the cycle. Next, note that $T’$ will also be a spanning tree, since it contains $V-1$ edges and has no cycles.