Theorem 5.18: Kruskal's algorithm produces a minimum spanning tree of a connected weighted graph. g Proof: Let g be a connected weighted graph, and T be the graph which is produced by Kruskal algorithm ☆ By theorem5.14 &T is a spanning tree of g
❖ Theorem 5.18: Kruskal’s algorithm produces a minimum spanning tree of a connected weighted graph. ❖ Proof: Let G be a connected weighted graph, and T be the graph which is produced by Kruskal’s algorithm. ❖ By theorem 5.14 ❖ T is a spanning tree of G
&o Now we prove T is a minimum spanning tree Suppose t that is not a minimum spanning tree. Thus there is a spanning tree s of G such that W(S<w(T). w(e1)sw(e2)≤sw(ek)≤…sw(en1) Suppose ek that is the first edges, ie el,e2,.sek-I are common edges of T and s There is a simple circuit C that is in E(sUek Then there is an edge e of c that e'Es and eT. 令e1e2y…,ek-1,e'∈S, thus e1,e2…,ek-1ande'≠any circuit By Kruskal's algorithm, w(eksw(e)
❖ Now we prove T is a minimum spanning tree ❖ Suppose T that is not a minimum spanning tree. Thus there is a spanning tree S of G such that w(S)<w(T). ❖ w(e1 ) ≤w(e2 ) ≤≤w(ek ) ≤≤w(en-1 ) ❖ Suppose ek that is the first edgeS, i.e. e1 ,e2 ,,ek-1 are common edges of T and S. ❖ There is a simple circuit C that is in E(S∪{ek }. Then there is an edge e' of C that e'S and e'T. ❖ e1 ,e2 ,,ek-1 , e'S, thus e1 ,e2 ,,ek-1 and e' any circuit. ❖ By Kruskal’s algorithm, w(ek )≤w(e')