Reading

These notes and closely review Unit 5 Section 4.1.

Quiz questions

None.

Undirected Graphs

Spanning Trees

Minimum Spanning Tree

Algorithm: Prim's MST
Input : G, a connected, weighted, undirected graph with n vertices and e edges
        r, a vertex in G 
Output: T a minimum weight spanning tree for G

0. mark each vertex's parent as "unknown" except r, which has parent nil ← i.e. only r is in the current MST
1. select vertex v with parent "unknown" with edge (u,v), where u's parent is 
   not "unknown",  such that (u,v) has minimum weight amongst all such edges

2. set v's parent to u  ← i.e. add v to thecurrent MST by connecting it to u

3. goto Step 1
      

Proof that Prim's algorithm gives a minimum spanning tree

First we have to prove that the greedy algorithm is always part of some optimum solution.

Theorem: If $T'$ is a subtree of a minimum spanning tree for $G$, then there is a complete minimum spanning tree for $G$, call it $T$, that contains $T'$ and contains the edge $(u,v)$ that is the minimum weight edge from a vertex in $T'$ to a vertex not in $T'$.
Proof: Let $T^*$ be a spanning tree that contains $T'$ but does not contain the edge $(u,v)$. We will show how to "repair" it to create a tree that still contains $T'$, but also contains $(u,v)$, without increasing the total weight of the resulting tree. The unique path from $u$ to $v$ in $T^*$ leaves $T'$ along some edge $(y,z)$, i.e. $y$ is in $T'$, but $z$ is not. If we delete $(y,z)$ we have two disconnected trees, the one containing $u$ and the one containing $v$. If we then add the edge $(u,v)$, we reconnect the two trees, resulting in a new spanning tree, call it $T$. Since the weight of $(u,v)$ $\le$ the weight of $(y,z)$, the overall weight of $T$ is $\le$ the overall weight of $T^*$.

Second, we have to prove that finding an optimum solution to the smaller subproblem yields an optimum solution to the original problem. At first this is a bit confusing, because the way we've phrased Prim's algorithm, it's not clear that we have a "smaller problem of the same kind" to solve. So let's imagine specifying the problem Prim's algorithm is solving in a slightly different way:

Problem: Minimum Weighted Spanning Tree (containing proscribed subtree)
Given: a connected Graph G (V is the set of vertices, E the set of edges)
       a subtree T' of G spanning the vertex set R, which is a subset of V
Find : a spanning tree T of the graph G that contains T' as a subtree
       and has minimum weight over all such spanning trees.
	
Hopefully you see that Prim's algorithm can be viewed as solving a sequence of such problems, where $|V-R|$ gets smaller at each step. Now what we have to prove is trivial, because a solution to the "smaller sub-problem" is a solution to the original problem, and therefore finding an optimal solution to the smaller subproblem is indeed the right thing to do.