Minimum Spanning Tree Section 4 5 Minimum Spanning Tree p Minimum Spanning Tree Given a connected graph G V E with positive edge costs ce an MST is a sub graph V T such that T is a spanning tree with the minimum total edgecost 1 PDF created with pdfFactory trial version www pdffactory com Minimum Spanning Tree p Minimum Spanning Tree Given a connected graph G V E with positive edge costs ce an MST is a sub graph V T such that T is a spanning tree with the minimum total edgecost Applications p Network Design n n p Telephone electrical water cable computer road Steiner network connect only a subset of nodes Indirect applications n n n n Max bottleneck paths Error correction Data compression 2 PDF created with pdfFactory trial version www pdffactory com Greedy algorithms for MST p Start with T Consider edges in ascending order of their cost Insert edge in T unless doing so would create a cycle Greedy algorithms for MST Start with T Consider edges in ascending order of their cost Insert edge in T unless doing so would create a cycle p Start with T E Consider edges in descending order of cost Delete e from T unless doing so would disconnect T p 3 PDF created with pdfFactory trial version www pdffactory com Greedy algorithms for MST p p p Start with T Consider edges in ascending order of their cost Insert edge in T unless doing so would create a cycle Start with T E Consider edges in descending order of cost Delete e from T unless doing so would disconnect T Start with some root node s and greedily grow a tree from s outward Let the current set of nodes in the tree be S At each step add the cheapest edge to T such that e has one end point in S and another outside S All three are optimal 4 PDF created with pdfFactory trial version www pdffactory com All three are optimal p p p Kruskal s Algo Start with T Consider edges in ascending order of their cost Insert edge in T unless doing so would create a cycle Reverse Delete Algo Start with T E Consider edges in descending order of cost Delete e from T unless doing so would disconnect T Prim s Algo Start with some root node s and greedily grow a tree from s outward Let the current set of nodes in the tree be S At each step add the cheapest edge to T such that e has one end point in S and another outside S Demo p http www b2 is tokushimau ac jp ikeda suuri kruskal Kruskal shtm l 5 PDF created with pdfFactory trial version www pdffactory com Snapshot of Prim s and Kruskal s Algos Analysis When is it safe to include an edge in the MST p When can we guarantee an edge is not in the MST p 6 PDF created with pdfFactory trial version www pdffactory com Analysis p When is it safe to include an edge in the MST n p Whenever an edge satisfies the cut property When can we guarantee an edge is not in the MST n Whenever an edge satisfies the cycle property Cycles p Cycle n 1 A cycle is a set of edges of the form a b b c c d z a 2 3 6 Path 1 2 3 4 5 6 1 Cycle 1 2 2 3 3 4 4 5 5 6 6 1 4 5 7 8 7 PDF created with pdfFactory trial version www pdffactory com Cuts p Cut n The cut induced by a subset of nodes S is the set of all arcs with exactly one endpoint in S 1 2 3 6 S 4 5 8 Cut 5 6 5 7 3 4 3 5 7 8 4 5 7 8 Cut Cycle Intersection p CCC Cut Cycle Claim A cycle and a cut intersect in an even number of edges 8 PDF created with pdfFactory trial version www pdffactory com Cycle Cut Intersection 1 2 3 6 4 Intersection 3 4 5 6 5 8 7 S Cut and Cycle Property 4 17 Cut Property Let S be any proper subset of nodes and let e be the min cost edge with exactly one point in S Then every MST contains e p 4 20 Cycle Property Let C be any cycle and let e be the max cost edge belonging to C Then no MST contains e p 9 PDF created with pdfFactory trial version www pdffactory com Cycle and Cut property 2 3 g 1 6 f 4 5 9 7 e 8 Simplifying assumption p All edge costs ce are distinct and positive 0 10 PDF created with pdfFactory trial version www pdffactory com Incorrect proof of the Cut property p p p p p p Let e v w be the minimum cost edge with one end point in S and another in V S Let T be a minimum spanning tree that does not contain e T must have an edge e with one end point in S and another in V S why Since e is the min cost edge with this property ce ce Create a new spanning tree T T e e Cost of T Cost of T a contradiction Incorrect proof of the cut property 11 PDF created with pdfFactory trial version www pdffactory com Proof of the cut property p p p p p p p Let e v w be the minimum cost edge with one end point in S and another in V S Let T be a minimum spanning tree that does not contain e Create T T e this creates a cycle C in T which contains the edge e C must have another edge e e with exactly one end point in S from cut cycle claim Since e is the min cost edge with this property ce ce Create a new spanning tree T T e e Cost of T Cost of T a contradiction Exchange argument for cut property 12 PDF created with pdfFactory trial version www pdffactory com Proof of cycle property p p p p p p Let C be a cycle and let e v w be the max cost edge in C Let T be an MST containing e Delete e from T This creates two components S and V S each of which contains an end point of e C must have another edge e e with exactly one end point in S from cut cycle claim Since e is the max cost edge in cycle C ce ce Create a new spanning tree T T e e Cost of T Cost of T a contradiction Exchange argument for cycle property 13 PDF created with pdfFactory trial version www pdffactory com Optimality of Prim s Kruskal s and Reverse Delete Algos All three algos produce a spanning tree p Prim s and Kruskal s algos always add only those edges which satisfy the cut property Hence they produce MSTs …