Minimal Spanning TreesSpanning TreeSpanning treesProperty 1 of spanning treesProof of Property 1Useful lemma about treesSlide 7Property 2 of spanning treesProof of Property 2 - OutlineProof of Property 2Building BFS/DFS spanning treesWeighted Spanning TreesExampleCaution: in general, SSSP tree is not MSTProperty 3 of minimal spanning treesSlide 16Building Minimal Spanning TreesPrim’s MST algorithmSteps of Prim’s algorithmProperty of Prim’s algorithmProof of correctness (part 1)Proof (contd.)Slide 23Complexity of Prim’s AlgorithmEditorial notesMinimal Spanning TreesSpanning Tree•Assume you have an undirected graph G = (V,E) •Spanning tree of graph G is tree T = (V,ET E, R)–Tree has same set of nodes–All tree edges are graph edges–Root of tree is R•Think: “smallest set of edges needed to connect everything together”Spanning treesA BCDEFGHIBreadth-first Spanning Tree012A BCDEFGHI123456789Depth-first spanning treeProperty 1 of spanning trees •Graph: G = (V,E) , Spanning tree: T = (V,ET,R)•For any edge c in G but not in T, there is a simple cycle containing only edge c and edges in spanning tree.A BCDEFGHIedge (I,H): simple cycle is (I,H,G,I)edge (H,C): simple cycle is (H,C,B,A,G,H)Proof?Proof of Property 1•Edge is c goes u v•If u is ancestor of v, result is easy (u v, then v u form a cycle)•Otherwise, there are paths root u and root v (b/c it is a tree). Let p be the node furthest from root on both of these paths. Now p u, then u v, then v p form a cycle.A BCDEFGHIedge (I,H): p is node G simple cycle is (I,H,G,I)edge (H,C): p is node A simple cycle is (H,C,B,A,G,H)Useful lemma about trees• In any tree T = (V,E), |E|=|V| -1 - Proof?Useful lemma about trees• In any tree T = (V,E), |E|=|V| -1 - Proof: (by induction on |V|) * If |V| = 1, we have the trivial tree containing a single node, and the result is obviously tree. * Assume result is true for all trees for which 1 <= |V| <n, and consider a tree S=(ES, VS) with |V| = n. Such a tree must have at least one leaf node; removing the leaf node and edge incident on that node gives a smaller tree T with less than n nodes. By inductive assumption, |ET| = |VT|+1. Since |ES| = |ET|+1 and |VS|=|VT|+1, the required result follow.• Converse also true: an undirected graph G = (V,E) which(1) has a single connected component, and (2) has |E| = |V|-1 must be a tree.Property 2 of spanning trees •Graph: G = (V,E), Spanning tree: T = (V,ET,R)•For any edge c in G but not in T, there is a simple cycle Y containing only edge c and edges in spanning tree.•Moreover, inserting edge c into T and deleting any edge in Y gives another spanning tree T’.A BCDEFGHIedge (H,C): simple cycle is (H,C,B,A,G,H) adding (H,C) to T and deleting (A,B) gives another spanning treeProof of Property 2 - Outline• T’ is a connected component. - Proof?• In T’, numbers of edges = number of nodes –1 - Proof ?• Therefore, from lemma earlier, T’ is a tree.Proof of Property 2• T’ is a connected component. - Otherwise, assume node a is not reachable from node b in T’. In T, there must be a path from b to a that contains edge (s→t). In this path, replace edge (s→t) by the path in T’ obtained by deleting (s→t) from the cycle Y, which gives a path from b to a. Contradiction, thus a must be reachable from b• In T’, numbers of edges = number of nodes –1 - Proof: by construction of T’ and fact that T is a tree. T’ is same as T, with one edge removed, one edge added.• Therefore, from lemma, T’ is a tree.Building BFS/DFS spanning trees•Use sequence structure as before, but put/get edges, not nodes–Get edge (s,d) from structure–If d is not in done set, •add d to done set•(s,d) is in spanning tree•add out-edges (d,t) to seq structure if t is not in done set•Example: BFS (Queue)A BCDEFGHI012[(dummy,A)][(A,B),(A,G),(A,F)][(A,G),(A,F),(B,G),(B,C)]…..dummyWeighted Spanning Trees•Assume you have an undirected graph G = (V,E) with weights on each edge•Spanning tree of graph G is tree T = (V,ET E)–Tree has same set of nodes–All tree edges are graph edges–Weight of spanning tree = sum of tree edge weights•Minimal Spanning Tree (MST)–Any spanning tree whose weight is minimal–In general, a graph has several MST’s–Applications: circuit-board routing, networking, etc.ExampleA BCDEFGHI242169 562 5451A BCDEFGHI242169 562 5451A BCDEFGHI242169 562 5451333111Graph SSSP treeMinimal spanning treeCaution: in general, SSSP tree is not MST•Intuition:–SSSP: fixed start node –MST: at any point in construction, we have a bunch of nodes that we have reached, and we look at the shortest distance from any one of those nodes to a new node4 414 4 41SSSP TreeMSPProperty 3 of minimal spanning trees•Graph: G = (V,E) , Spanning tree: T = (V,ET,R)•For any edge: c in G but not in T, there is a simple cycle Y containing only edge c and edges in spanning tree (already proved).•Moreover, weight of c must be greater than or equal to weight of any edge in this cycle.–Proof?CDEFGHI242169 562 54513 1Edge(GH): 5Cycle edges: (GI), (IE), (ED),(HD) all have weights less than (GH)Property 3 of minimal spanning trees•Graph: G = (V,E) , Spanning tree: T = (V,ET,R)•Edge c … weight of c must be greater than or equal to weight of any edge in this cycle.•Proof: Otherwise, let d be an edge on cycle with lower weight. Construct T’ from T by removing c and adding d. T’ is less weight than T, so T not minimal. Contradiction., so d can’t exist.CDEFGHI242169 562 54513 1Edge(GH): 5Cycle edges: (GI), (IE), (ED),(HD) all have weights less than (GH)Building Minimal Spanning Trees•Prim’s algorithm: simple variation of Dijkstra’s SSSP algorithm –Change Dijkstra’s algorithm so the priority of bridge (fn) is length(f,n) rather than minDistance(f) + length(f,n)–Intuition: Starts with any node. Keep adding smallest border edge to expand this component.•Algorithm produces minimal spanning tree!Prim’s MST algorithmTree MST = empty tree;Heap h = new Heap();//any node can be the root of the MSTh.put((dummyRoot anyNode), 0);while (h is not empty) { get minimum priority (= length) edge (tf); if (f is not lifted) {
View Full Document
Unlocking...