TAILIEUCHUNG - Lecture Data structures and algorithms in Java (6th edition): Chapter 14.6 - Goodrich, Tamassia, Goldwasser
This chapter provides knowledge of mst. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Minimum Spanning Tree 3/25/14 15:52 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Minimum Spanning Trees © 2014 Goodrich, Tamassia, Goldwasser Minimum Spanning Trees 1 Minimum Spanning Trees Spanning subgraph n ORD Subgraph of a graph G containing all the vertices of G Spanning tree n Spanning subgraph that is itself a (free) tree DEN Minimum spanning tree (MST) n q Spanning tree of a weighted graph with minimum total edge weight 10 1 PIT 9 6 STL 4 8 7 3 DCA 5 2 Applications n n Communications networks Transportation networks © 2014 Goodrich, Tamassia, Goldwasser DFW Minimum Spanning Trees ATL 2 1 Minimum Spanning Tree 3/25/14 15:52 Cycle Property Cycle Property: Let T be a minimum spanning tree of a weighted graph G n Let e be an edge of G that is not in T and C let be the cycle formed by e with T n For every edge f of C, weight(f) ≤ weight(e) Proof: n By contradiction n If weight(f) > weight(e) we can get a spanning tree of smaller weight by replacing e with f 6 2 9 3 e 8 Replacing f with e yields a better spanning tree 8 f 6 2 4 C 9 3 e 8 7 7 Minimum Spanning Trees 3 U f Partition Property: Consider a partition of the vertices of G into subsets U and V n Let e be an edge of minimum weight across the partition n There is a minimum spanning tree of G containing edge e Proof: n Let T be an MST of G n If T does not contain e, consider the cycle C formed by e with T and let f be an edge of C across the partition n By the cycle property, weight(f) ≤ weight(e) n Thus, weight(f) = weight(e) n We obtain another MST by replacing f with e 7 7 Partition Property n © 2014 Goodrich, Tamassia, Goldwasser 4 C n © 2014 Goodrich, Tamassia, Goldwasser 8 f V 7 4 9 5 2 8 8 3 e 7 Replacing f with e yields another MST U 2 Minimum Spanning .
đang nạp các trang xem trước
