Information about MINIMUM SPANNING TREES

MINIMUM SPANNING TREES : 1 MINIMUM SPANNING TREES Definition : Spanning tree : Let G = (V,E) be an un-directed connected graph. A sub-graph T = (V1, E1) of G is a spanning tree of G iff T is a tree. O O O O O O O O O O O O O O O (a) (b) (c) (d) MINIMUM SPANNING TREES (Contd..) : 2 MINIMUM SPANNING TREES (Contd..) Is a complete graph (b),(c),(d) are three of A’s spanning trees. (A minimal connected sub-graph of G which includes all the vertices of G is a spanning tree of G) APPLICATIONS OF SPANNING TREES : 3 APPLICATIONS OF SPANNING TREES Spanning trees can be used to obtain an independent set of circuit equations for an electrical network. Let B be the set of network edges not in the spanning tree. Adding an edge from B to the spanning tree creates a cycle. Different edges from B result in different cycles. MINIMUM SPANNING TREES (Contd..) : 4 MINIMUM SPANNING TREES (Contd..) Kirchoff’s second law is used on each cycle to obtain a circuit equation. The cycles obtained in this way are independent as each contains one edge from B which is not contained in any other cycle. Hence the circuit equations so obtained are also independent. MINIMUM SPANNING TREES (Contd..) : 5 MINIMUM SPANNING TREES (Contd..) (cities) arises from the property that a spanning tree is a minimal sub-graph G1 of G such that V(G) = V(G1) and G1 is connected. A connected graph with n vertices must have at least n-1 edges and all connected graphs with n-1 edges are trees. MINIMUM SPANNING TREES (Contd..) : 6 MINIMUM SPANNING TREES (Contd..) If the nodes of G represent cities and the edges represent possible communication links connecting two cities, the minimum number of links needed to connect the n cities is n-1. The spanning trees of G will represent all feasible choices. In practice, the edges will have weights associated with them. MINIMUM SPANNING TREES (Contd..) : 7 MINIMUM SPANNING TREES (Contd..) These might represent the cost of construction, the length of the link etc. We are interested in finding a spanning tree of G with minimum cost. Prim’s algorithm (Greedy method) to obtain a minimum cost spanning tree. If A is the set of edges selected so far, then A forms a tree. The next edges (u,v) to be included in A is a minimum cost edge not in A with the property that A U {u, v} is also a tree. Prim’s Algorithm- Example : 8 Prim’s Algorithm- Example Example : 2 10 50 1 40 3 45 35 5 30 25 15 55 4 6 20 Prim’s Algorithm- Example (Contd..) : 9 Prim’s Algorithm- Example (Contd..) Edge Cost Spanning tree (1,2) 10 10 1 2 (2,4) 25 10 1 2 6 25 (3,6) 15 10 1 2 25 6 15 3 Prim’s Algorithm- Example (Contd..) : 10 Prim’s Algorithm- Example (Contd..) Edge Cost Spanning tree (6,4) 20 10 1 2 25 4 20 6 15 3 (1,4) Reject (3,5) 35 10 1 2 5 25 4 20 6 15 3 35 PRIM’s algorithm to find minimum cost spanning tree : 11 PRIM’s algorithm to find minimum cost spanning tree The cost of spanning tree is 105. Procedure PRIM (E,cost, n, T, mincost) // E is the set of edges in G // // cost (n,n) is the adjacency matrix // // such at cost (i,j) is a +ve real number // // or cost (i,j) is 8 if no edge (i,j) exists // // A minimum cost spanning tree is // PRIM’s algorithm to find minimum cost spanning tree contd.. : 12 PRIM’s algorithm to find minimum cost spanning tree contd.. // computed and stored as a set // // of edges in the array T(1,n-1,2) // // (T(i,1), T(i,2) is an edge in minimum cost spanning tree // Real cost (n,n), mincost; Integer near(n),i,j,k,l,T(1:n-1,2) (k,l) ? edges with minimum cost 4 mincost ? cost (k,l) (T(1,1) T(1,2) )? (k,l) for i? 1 to n do // initialing near // PRIM’s algorithm to find minimum cost spanning tree contd.. : 13 PRIM’s algorithm to find minimum cost spanning tree contd.. if cost (i,L) < cost (I,k) then near (i) ? L else near (i) ? k endif repeat near(k) ? near (l) ? 0 // (K,L) is already in the tree // for i ? 2 to n-1 do //find n-2 additional edges for T // Let j be an index such that NEAR (J) ? 0 and COST (J,NEAR(J)) is minimum PRIM’s algorithm to find minimum cost spanning tree contd.. : 14 PRIM’s algorithm to find minimum cost spanning tree contd.. (T(i,1),T(i,2)) ? (j, NEAR (j)) Mincost ? mincost + cost (j, near (j)) NEAR (j) ? 0 for k ? 1 to n do // update near // if NEAR (k) ? 0 and COST(k near (k)) > cost(k,j) then NEAR (k) ? j endif 20 repeat Repeat if mincost >> 8 then print (‘no spanning tree’) endif END PRIM EXPLANATION OF PRISM’S ALGORITHM : 15 EXPLANATION OF PRISM’S ALGORITHM After including a minimum cost edge near (i) is computed for each I = 1,…n. Near (i) is the vertex (out of the two vertices in the included edge) which is near to i. Near (i) is computed so that after including an edge, we need to find the vertex with which we are trying to form the new /next edge in the spanning tree. EXPLANATION OF PRISM’S ALGORITHM (Contd..) : 16 EXPLANATION OF PRISM’S ALGORITHM (Contd..) To exclude already included edges make near (k) ?0 near (l) ? 0 if (k, l) is included. In the second for-loop we are finding I which forms an edge with near (i) and having minimum cost. In the third for-loop which is included in the second for-loop we check whether near (i) values are same or, are to be updated with respect to the newly added edge or w.r.t. to the newly included vertex j. EXPLANATION OF PRISM’S ALGORITHM (Contd..) : 17 EXPLANATION OF PRISM’S ALGORITHM (Contd..) Example: Minimum cost edge (1, 2) with cost 10 is included Near (3) ? 2 Near (4) ?1 Near (5) ?2 Near (6) ?2 Near (1) ? 0 Near (2)?0 Select out of 3,4,5,6 a vertex such that {Cost (3, 2) = 50 Cost (4, 1) = 30 Cost (5, 2) = 40