Spanning Tree

Definition (Cut)

A cut is a partition of the nodes into two nonempty subsets $S$ and $V-S$

The cutset of a cut $S$ is the set of edges with exactly one endpoint in $S$ (removing the cutset would disconnect the partitions).

Claim

A cycle and a cutset intersect in an even number of edges.

Definition (Spanning Tree)

Let $H=(V,T)$ be a subgraph of an undirected graph $G=(V,E)$. $H$ is a spanning tree of $G$ if $H$ is both acyclic and connected.

If $G$ has edge costs, a minimum spanning tree is a spanning tree such that the sum of the edge costs in $T$ is minimized.

Theorem (Cayley's Theorem)

A graph with $n$ nodes has $n^{n-2}$ spanning trees

Greedy Algorithm

Fundamental Cycles

• Fundamental Cycle
  • Let $H=(V,T)$ be a spanning tree of $G=(V,E$).
  • For any non tree-edge $e\in E$, $T\cup \{e\}$ contains a unique cycle, say $C$, the fundamental cycle.
  • For any edge $f\in C$, $(V,T\cup \{e\}-\{f\})$ is a spanning tree.
• Fundamental Cutset
  • Let $H=(V,T)$ be a spanning tree of $G=(V,E)$.
  • For any tree edge $f\in T$, $V,T-\{f\})$ has two connected components.
  • Let $D$ denote corresponding cutset
  • For any edge $e\in D$, $(V,T-\{f\}\cup \{e\})$ is a spanning tree
• Observation: If $c_e<c_f$ then $(V,T)$ is not an MST

Algorithm

• Rules
  • Red rule
    • Let $C$ be a cycle with no red edges
    • Select an uncolored edge of $C$ of max cost and color it red
  • Blue rule
    • Let $D$ be a cutset with no blue edges
    • Select an uncolored edge in $D$ of min cost and color it blue
• Algorithm
  • Apply the red and blue rules (nondeterministically) until all edges are colored. The blue edges form an MST.
  • Note: can stop once $n-1$ edges are colored blue

Correctness

Claim (Color Invariant)

There exists an MST $(V,T^{\ast })$ containing every blue edge and no red edge

Proof: Base Case: No edges colored $\Rightarrow$ every MST contains every blue edge and excludes every red edge (since there are none of either)

Inductive Hypothesis: Assume color invariant when $k$ edges colored for some $k\ge 0$

Inductive Step: $k+1$ edges colored Case 1: Blue rule applied next

• Let $D$ be chosen cutset, and let $f$ be edge colored blue.
• If $f\in T^{\ast }$, then $T^{\ast }$ still satisfies invariant.
• Otherwise, consider fundamental cycle $C$ by adding $f$ to $T^{\ast }$.
• Let $e\in C$ be another edge in $D$.
• $e$ is uncolored and $c_e\ge c_f$ since
  • $e\in T^{\ast }\Rightarrow e$ not red
  • Blue rule $\Rightarrow e$ not blue and $c_e\ge c_f$
• Thus, $T^{\ast }\cup \{f\}-\{e\}$ satisfies invariant.

Case 2: Red rule applied next

• Let $C$ be chosen cycle, and $e$ be edge colored red.
• If $e\notin T^{\ast }$, then $T^{\ast }$ still satisfies invariant.
• Otherwise, consider fundamental cutset $D$ by deleting $e$ from $T^{\ast }$.
• Let $f\in D$ be another edge in $C$.$f$ is uncolored and $c_e\ge c_f$ since
  • $f\notin T^{\ast }\Rightarrow$ not blue
  • red rule $\Rightarrow f$ not red and $c_e\ge c_f$
• Thus, $T^{\ast }\cup \{f\}-\{e\}$ satisfies invariant $\square$

Theorem

The greedy algorithm terminates. Blue edges form an MST.

Proof: We need to show that either the red or blue rule (or both) applies.

• Suppose edge $e$ is left uncolored.
• Blue edges form a forest.
• Case 1: Both endpoints of $e$ are in the same blue tree.
  • Apply red rule to cycle formed by adding $e$ to blue forest.
• Case 2: both endpoints of $e$ are in different blue trees.
  • Apply blue rule to cutset induced by either of two blue trees. $\square$

Prim’s Algoritm

Algorithm

• Initialize $S=\{s\}$ for any node $s$, $T=\{\}$
• Repeat $n-1$ times
  • Add to $T$ a min-cost edge with exactly one endpoint in $S$
  • Add the other endpoint to $S$.

Correctness

Theorem

Prim’s algorithm computes an MST

Proof: Special case of greedy algorithm (blue rule repeatedly applied to S)

Time Complexity

• $O(nm)$ using arrays
• $O(m\log n)$ using priority queues

Kruskal’s Algoritm

Algorithm

• Arrange edges by ascending weights
• Add edges to the the spanning tree as long as they don’t create a cycle using Cycle Detection

Correctness

Theorem

Kruskal’s algorithm computes an MST.

Proof: Special case of greedy algorithm. Case 1: Both endpoints of $e$ are in the same blue tree

• Color $e$ red by applying red rule to unique cycle (all other edges in cycle are blue) Case 2: Both endpoints of $e$ are in different blue trees
• Color $e$ blue by applying blue rule to cutset defined by either tree (no edge in cutset has smaller cost because Kruskal’s chose it first) $\square$

Time complexity

• Using Disjoint Set Cycle Detection: $O(m\log n)$