Minimum Spanning Tree

Summarized notes on Introduction to Algorithms, Chapter 23

• tree - is an undirected graph with no cycles, i.e. connected graph with $N$ nodes and $N-1$ edges
• spanning tree - acyclic subset $T\in E$ that connects all vertices
• minimum-spanning tree problem - process of determining $T$
• greedy algorithm - perform locally optimal choices → solution not guaranteed to be globally optimal

Growing a Minimum Spanning Tree

Generic algorithm that grows the MST one edge at a time - manages a set od edges $A$ maintaining the following loop invariant:

prior to each iteration, $A$ is a subset of some minimum spanning tree - at each step, determine safe edge $(u,v)$ that can be added to $A$ without violating this invariant - algorithm terminates as soon as $A$ forms a MST

Finding a safe edge

• looking for $(u,v)\in T$ such that $(u,v)\notin A$ → one must exist since $A\in T$
• cut $(S,V-S)$ of undirected graph $G=(V,E)$ is a partition of $V$
• edge crosses the cut if one endpoint is in $S$ and other is in $V-S$
• cut respects edges of $A$ if no edge in $A$ crosses the cut
• light edge is the minimum weight edge crossing a cut → multiple may exist
• $A$ is always acyclic
• asymptotic time not given, but $|V|-1$ iterations over edges → $\mathrm{\Omega }(V+E)$

Theorem for identifying safe edge

Let $G=(V,E)$ be connected, undirected graph with real-valued weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$, left $(S,S-V)$ be any cut of $G$ that respects $A$, and let $(u,v)$ be a light edge crossing $(S,V-S)$. Then edge $(u,v)$ is safe for $A$.