Minimal Spanning TreesSpanning Tree•Assume you have an undirected graph G = (V,E) •Spanning tree of graph G is tree T = (V,ETE, 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 Gsimple cycle is (I,H,G,I)edge (H,C):p is node Asimple 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 bin T’. In T, there must be a path from b to a that containsedge (s? t). In this path, replace edge (s? t) by the path inT’ obtained by deleting (s? t) from the cycle Y, which gives a path from b to a. Contradiction, thus a mustbe 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’ issame 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 seqstructure 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,ETE)– 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(GàH): 5Cycle edges: (GàI), (IàE), (EàD),(HàD) all have weights less than (GàH)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(GàH): 5Cycle edges: (GàI), (IàE), (EàD),(HàD) all have weights less than (GàH)Building Minimal Spanning Trees• Prim’s algorithm: simple variation of Dijkstra’s SSSP algorithm – Change Dijkstra’s algorithm so the priority of bridge (fàn) 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 (tàf);if (f is not lifted) {add (tàf) to MST;//grow MSTmake f a lifted node;for each edge (fàn) if (n is not lifted) h.put((fàn), length(f,n));}}Steps of Prim’s algorithmA BCDEFGHI242169 562 54513 1[((dummyàA), 0)] [] add (dummyàA) to MST[((AàB),2), ((AàG),5),((AàF),9)][((AàG),5),((AàF),9)] add (AàB) to MST[((AàG),5),((AàF),9), (BàG),6),((BàC),4)] [((AàG),5),((AàF),9),((BàG),6)] add (BàC) to MST[((AàG),5),((AàF),9),((BàG),6),((C,H),5), ((C,D), 2)]………..Property of Prim’s algorithm• At each step of the algorithm, we have a spanning tree for “lifted” nodes.• This spanning tree grows by one new node and edge at each iteration.A
View Full Document