1Minimal Spanning TreesReading. Weiss, sec. 24.2.2Real quotes from a Dilbert-quotes contest:"As of tomorrow, employees will be able to access the building only using individual security cards. Pictures will be taken next Wednesday and employees will receive their cards in two weeks."(Microsoft Corp. in Redmond, WA)"What I need is an exact list of specific unknown problems we might encounter.” (Lykes Lines Shipping)"E-mail is not to be used to pass on information or data. It should be used only for company business.” (Electric Boat Company)"This project is so important, we can't let things that are more important interfere with it.” (United Parcel Service)Spanning TreeAssume you have a directed or undirected graph.Spanning tree of a graph is tree such that– Tree has same set of nodes– Set of tree edges is a subset of graph edgesABCDEFGHIABCDEFGHITree Another treeBFS and DFS WalkPre-order traversal gives a depth-first search (DFS) of a tree. Breadth-first search (FBS) as in second diagram11232344556677DFS BFSNodes numbered in the order visitedTwo spanning trees of the same graphABGHIBreadth-first Spanning Tree012ABCDEFGHI123456789Depth-first Spanning TreeA is root of tree. Tree edges are red.To build a spanning tree: (1) start with one node, A, as root. (2) At each step, add to tree one edge from a node in tree to a node that is not yet in the tree. FEDCV = {A}; E = {}; s = (A,F), (A,G), (A,B) // s: stack of edgesStep 1: Take (A,F) off stack and add to E;push onto s edges leaving F.V = {A,F}; E = {(A,F)}; s = (F,E), (F,I), (F,A) (A,G), (A,B)Step 2: Take (F,E) off s and add to E;push onto s edges leaving E.V = {A,F,E}; E = {(A,F),(F,E)}; s = (E,F), (E,I), (E,D),(F,I), (F,A) (A,G), (A,B)Build a DFS spanning tree (V, E). Use a stackCABDEFGHIAfter taking an edge (v,w) off stack:if w already in V, don’t do anythingBuild a DFS spanning tree (V, E)V = {A}; E = {}; //start off with one-node trees = stack of edges to neighbors of A; // s is a stack of edges/** invariant:(V,E) is a tree.For all edges (v,w) in s: v is in V and (v,w) not in E.Any node in graph that is not in V is reachable from theend node of some edge in s. **/while (s is not empty do) {(v, w) = pop(s); // Take top edge (v,w) off s;if (w is not in V) {Add w to V; add (v,w) to E;Push onto s all edges with start node w;}}ABDEFGHIC2V = {A}; E= {}; s = (A,F), (A,G), (A,B) // s: queue of edgesStep 1: Take (A,F) off s and add to E;push onto s edges leaving F.V = {A,F}; E = {(A,F)}; s = (A,G), (A,B), (F,E), (F,I), (F,A)Step 2: Take (A,G) off s and add to E;push onto s edges leaving G.V = {A,F,G}; E = {(A,F),(A,G)}; s = (A,B), (F,E), (F,I), (F,A),(G,I), (G,H), (G,B), (G,A)Build a BFS spanning tree (V, E). Use a queue.After taking an edge (v,w) off queue:if w already in V, don’t do anythingABDEFGHICBuild a BFS spanning tree (V, E)V = {A}; E = {}; //start off with one-node trees = queue of edges to neighbors of A; // s is a queue of edges/** invariant:(V,E) is a tree.For all edges (v,w) in s: v is in V and (v,w) not in E.Any node in graph that is not in V is reachable from theend node of some edge is s. **/while (s is not empty do) {(v, w) = pop(s); // Take top edge (v,w) off s;if (w is not in V) {Add w to V; add (v,w) to E;Push onto s all edges with start node w;}}ABDEFGHICBuild a DFS or BFS spanning tree (V, E)Building a DFS spanning tree and building a BFS spanning tree are essentially the same algorithm.DFS algorithm uses a stack ofedges to processBFS algorithm uses a stack ofedges to processABDEFGHICProperty 1 of spanning trees • Graph: G = (V,E) • Spanning tree: T = (V,ET,R)• Choose any edge: c = (u,v) in G but not in T• There is a simple cycle containing only edge c and edges in spanning tree.• Proof: Let w be the first node in common to paths from u to root of tree and from v to root of tree. The paths uÆv, vÆw,wÆu can be catenated to form the desired cycle.edge (I,H):w is node Gsimple cycle is (I,H,G,I)edge (H,C):w is node Asimple cycle is (H,C,B,A,G,H)ABCDEFGHIUseful lemma• In any tree T = (V,E), |E|=|V| – 1For all n>0, P(n) holds, whereP(n) for a tree with n (>0) nodes: |E| = |V| – 1Proof by induction on n* n = 1. tree with node has 0 edges. 0 = 1 - 1.* Assume P(n) for some n, 0 < n. Consider a tree S=(VS, ES) with n+1 nodes.S has a leaf. Remove 1 leaf (and the edge to it) to give a tree T with nnodes. By inductive assumption, P(n), |ET| = |VT|-1. Since |ES| = |ET|+1 and |VS|=|VT|+1, the result follows.• An undirected graph G = (V,E) is a tree iff (1) it is connected(2) |E| = |V| – 1Property 2 of spanning trees • Graph: G = (V,E) • Spanning tree: T = (V,ET,R)• Choose any edge: c = (u,v) 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 (sÆt) in Y gives another spanning tree T1.ABCDEFGHIedge (H,C):simple cycle is (H,C,B,A,G,H)adding (H,C) to T and deleting (A,B) gives another spanning tree3Proof of Property 2• T1 is connected.- Otherwise, assume node a is not reachable from node bin T1. In T, there is a path from b to a that containsedge (s→t). In this path, replace edge (s→t) by the path inT1 obtained by deleting (s→t) from the cycle Y, which gives a path from b to a.• In T1, numbers of edges = number of nodes –1- Proof: by construction of T1 and fact that T is a tree• Therefore, from lemma, T1 is a tree.• Assume an undirected graphG = (V,E) with weights on each edge• Spanning tree of graph G is tree T = (V,ET)– 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– A graph can have several MST’s– Applications: phone network design etc.Weighted Spanning TreesExampleABCDEFGHI242169562545131GraphSSSP tree (nodes inorder chosen byDijkstra’s shortestpath algoritmMinimal spanning treeweight 16weight 18CC2244222211111133556666555544AAFFDDEEBBHHIIGG99Caution: 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 node44144 41SSSP TreeMSPPrims’s algorithmUse the DFS algorithm given earlier, but consider s to be a set rather than a stack.At each iteration, choose the edge (v,w) from s that
View Full Document
Unlocking...