Minimum cost spanning trees

explain the minimum spanning trees and its applications and minimum cost spanning trees
Dr.BenjaminClark Profile Pic
Dr.BenjaminClark,United States,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
Comment
ROBERT SEDGEWICK KEVIN WAYNE Algorithms 4.3 MINIMUM SPANNING TREES introduction ‣ greedy algorithm ‣ edge-weighted graph API ‣ Algorithms FOUR TH EDITION Kruskal's algorithm ‣ Prim's algorithm ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu context ‣4.3 MINIMUM SPANNING TREES introduction ‣ greedy algorithm ‣ edge-weighted graph API ‣ Algorithms Kruskal's algorithm ‣ Prim's algorithm ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu context ‣Minimum spanning tree Def. A spanning tree of G is a subgraph T that is: Connected. Acyclic. Includes all of the vertices. graph G 3Minimum spanning tree Def. A spanning tree of G is a subgraph T that is: Connected. Acyclic. Includes all of the vertices. not connected 4Minimum spanning tree Def. A spanning tree of G is a subgraph T that is: Connected. Acyclic. Includes all of the vertices. not acyclic 5Minimum spanning tree Def. A spanning tree of G is a subgraph T that is: Connected. Acyclic. Includes all of the vertices. not spanning 6Minimum spanning tree Given. Undirected graph G with positive edge weights (connected). Goal. Find a min weight spanning tree. 24 4 23 9 6 18 5 11 16 8 7 10 14 21 edge-weighted graph G 7Minimum spanning tree Given. Undirected graph G with positive edge weights (connected). Goal. Find a min weight spanning tree. 24 4 23 9 6 18 5 11 16 8 7 10 14 21 minimum spanning tree T (cost = 50 = 4 + 6 + 8 + 5 + 11 + 9 + 7) Brute force. Try all spanning trees? 8Network design MST of bicycle routes in North Seattle http://www.flickr.com/photos/ewedistrict/21980840 9Models of nature MST of random graph http://algo.inria.fr/broutin/gallery.html 10Medical image processing MST describes arrangement of nuclei in the epithelium for cancer research http://www.bccrc.ca/ci/ta01_archlevel.html 11Medical image processing MST dithering http://www.flickr.com/photos/quasimondo/2695389651 12Applications MST is fundamental problem with diverse applications. Dithering. Cluster analysis. Max bottleneck paths. Real-time face verification. LDPC codes for error correction. Image registration with Renyi entropy. Find road networks in satellite and aerial imagery. Reducing data storage in sequencing amino acids in a protein. Model locality of particle interactions in turbulent fluid flows. Autoconfig protocol for Ethernet bridging to avoid cycles in a network. Approximation algorithms for NP-hard problems (e.g., TSP, Steiner tree). Network design (communication, electrical, hydraulic, computer, road). http://www.ics.uci.edu/eppstein/gina/mst.html 134.3 MINIMUM SPANNING TREES introduction ‣ greedy algorithm ‣ edge-weighted graph API ‣ Algorithms Kruskal's algorithm ‣ Prim's algorithm ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu context ‣Simplifying assumptions Graph is connected. Edge weights are distinct. Consequence. MST exists and is unique. 5 7 2 10 no two edge 4 6 weights are equal 13 1 9 3 8 12 14 16 20 15Cut property Def. A cut in a graph is a partition of its vertices into two (nonempty) sets. Def. A crossing edge connects a vertex in one set with a vertex in the other. Cut property. Given any cut, the crossing edge of min weight is in the MST. crossing edge separating gray and white vertices minimum-weight crossing edge must be in the MST 16Cut property: correctness proof Def. A cut in a graph is a partition of its vertices into two (nonempty) sets. Def. A crossing edge connects a vertex in one set with a vertex in the other. Cut property. Given any cut, the crossing edge of min weight is in the MST. Pf. Suppose min-weight crossing edge e is not in the MST. Adding e to the MST creates a cycle. Some other edge f in cycle must be a crossing edge. Removing f and adding e is also a spanning tree. Since weight of e is less than the weight of f, f that spanning tree is lower weight. Contradiction. ▪ e the MST does not contain e adding e to MST creates a cycle 17Greedy MST algorithm demo Start with all edges colored gray. Find cut with no black crossing edges; color its min-weight edge black. Repeat until V - 1 edges are colored black. 0-7 0.16 2-3 0.17 1 1-7 0.19 3 0-2 0.26 5 5-7 0.28 7 1-3 0.29 2 1-5 0.32 2-7 0.34 0 4-5 0.35 1-2 0.36 6 4 4-7 0.37 0-4 0.38 6-2 0.40 an edge-weighted graph 3-6 0.52 6-0 0.58 6-4 0.93 18Greedy MST algorithm demo Start with all edges colored gray. Find cut with no black crossing edges; color its min-weight edge black. Repeat until V - 1 edges are colored black. 1 3 5 7 2 0 6 4 MST edges 0-2 5-7 6-2 0-7 2-3 1-7 4-5 19Greedy MST algorithm: correctness proof Proposition. The greedy algorithm computes the MST. Pf. Any edge colored black is in the MST (via cut property). Fewer than V- 1 black edges ⇒ cut with no black crossing edges. (consider cut whose vertices are any one connected component) a cut with no black crossing edges fewer than V-1 edges colored black fewer than V-1 edges colored black fewer than V-1 edges colored black a cut with no black crossing edges a cut with no black crossing edges 20