=========================================================================== CSC 373H1 Lecture Notes -- Proof of Prim's Alg. Winter 2016 =========================================================================== A proof of Prim's algorithm showing that each step "is promising". Theorem: Given a connected undirected graph G = (V, E), with edge weights w(e), Prim's algorithm constructs a MST of G. Proof: We use the loop invariant: L(k): Let T_k = (S_k, F_k) be the subgraph that Prim has constructed with k = |S_k| (after the execution of the loop (k-1) times). Then there exists an MST T=(V,F) of G=(V, E) s.t. T_k is a subgraph of T. That is, T_k "is promising". We prove L(k) is true for k = 1 to |V| using induction. For the base case, k=1, T_1 = ({v}, {}). Given the existence of an MST T for G, T_1 must be a subgraph of T. We leave the existence of an MST for G to the reader. Let 1< k <= |V|. Assume L(k-1) is true. We need to prove L(k) is true. Since L(k-1) is assumed true, let T_(k-1) = (S_(k-1), F_(k-1)) be the subgraph generated during the execution of the algorithm with |S_(k-1)| = k-1. And let T be an MST of G which contains T_(k-1). (Such a T exists according to L(k-1).) Let e = (u, v), with u in S_(k-1) and v in V \ S_{k-1), be the k-th edge added by Prim. If edge e is in the MST T = (V, F), then L(k) follows. So we are left with considering the case e is not in F. Suppose e = (u,v) is not in F. Since T is a spanning tree, there exists a simple path P = (u, a(2), a(3), ... a(j), v) in T, from u to v. Let f = (a(i),a(i+1)) be the first edge on this path that has a(i) in S_(k-1) and a(i+1) in V\S_(k-1). Note u is in S_(k-1) and v is in the complement, so such an edge must exist. Also, all the edges in P are in T and e is not in T, so f does not equal e. Claim: The graph Tp = (V, (F\{f})U{e})) is a tree. Pf: Note Tp has the right number of edges for a tree, namely |V|-1. And we will show next that Tp is connected. Together these imply Tp is a tree (Property 2 in the MST slides.) To show Tp is connected, we first construct a path P' in Tp connecting the endpoints a(i) and a(i+1) of f (i.e., without using the edge f). To do this consider the simple cycle C = (u, a(2), a(3), ... a(j), v, u) in the graph (V, FU{e}), which is formed by concatenating the edge (v,u), the reverse of edge e, to the path P above. Recall that f is the edge (a(i), a(i+1)). Cut this cycle C and reverse it to form the desired simple path P' between a(i) and a(i+1), namely P' = (a(i), a(i-1), ... ,a(2), u, v, a(j), ... , a(i+1)). It follows that P' is in Tp = (V, (F\{f})U{e})). Next, given any two vertices x and y in V, suppose X is the simple path in T between x and y. If X contains the edge f (or its reverse) then this edge can be replaced by P' (or its reverse, respectively). The result is a path X' (perhaps not a simple path, but that's not important here) in Tp which connects x and y. This completes argument that Tp is connected and also the proof of the claim. Finally consider the weight of this tree Tp, (*) w(Tp) = w(T) - w(f) + w(e) There are three cases: a) w(f) < w(e): Impossible, since Prim's alg would not have chosen e in the presence of the edge f, for which f = (a(i), a(i+1)) with w(f) < w(e), a(i) in S_(k-1), and a(i+1) in V\S_(k-1). b) w(f) = w(e): Then (*) implies w(Tp) = w(T) and, since we know T is a MST, then Tp must be an MST too. Therefore L(k) holds with this modified MST Tp. c) w(f) > w(e): Impossible, since in this case (*) implies w(Tp) < w(T), but this contradicts T being a MST. Therefore L(k) must be true. It follows by induction that L(k) is true for k = 1 to |V|. Finally, L(|V|) implies that the computed subgraph is an MST for G. ===== Note: At each stage of Prim's algorithm T_k is a subtree. We carefully didn't make use of this above (and we didn't prove it). Because of this, the same loop invariant (with "Prim" replaced by Kruskal) applies to Kruskal's algorithm. The proof of Kruskal's algorithm then requires only a small modification.