CONSTRUCTION OF MINIMUM COST SPANNING TREE

 

   CONSTRUCTION OF MINIMUM COST SPANNING TREE

Let, G = (V, E) be an undirected connected weighted graph with n vertices, where V is the set of vertices, E is the set of edges and W be the set of weights (cost) associated to respective edges of the graph.

Where   the edge adjacent to vertices

 = the weight associated to the edge .

 The Weight Matrix M of the graph G is constructed as follows: If there is an edge between the vertices in G

then Set,  =  Else Set,  = 0

 Algorithm: Input: the weight matrix  for the undirected weighted graph G

Output: Minimum Cost Spanning Tree T of G.

Step 1: Start

Step 2: Repeat Step 3 to Step 4 until all (n-1) elements matrix of M are either marked or set to zero or in other words all the nonzero elements are marked

Step 3: Search the weight matrix M either column-wise or row-wise to find the unmarked nonzero minimum element  which is the weight of the corresponding edge   in M.

Step 4: If the corresponding edge   of selected  forms cycle with the already marked elements in the elements of the M then Set = 0 Else Mark  

Step 5: Construct the graph T including only the marked elements from the weight matrix M which shall be the desired Minimum cost spanning tree of G.                                      

Fig 1

 NUMERICAL EXAMPLE:

Consider the following graph and its shows the various steps involved in the construction of the minimum cost spanning tree

Fig 2 Graph G

Fig 3[ Matrix of graph G]

From fig 2 Graph G = (V, E) where V is the set of vertices and E represents the edge with weigh are also given. Here V=7 and Edge = 9.

Fig 3 represents the adjacent matrix for the given graph.

Fig 4 graph G

Fig 5 weight matrix

  Fig 4 The minimum element 10 is selected and the corresponding edges (1, 6) are also marked by the color pink. Repeat the process till the iteration will exist

fig 6

Fig7 weight matrix

 From Fig 6 and 7 the next non zero minimum element 12 is marked and the corresponding edges are also colored.

Fig 8

               

 The next non zero minimum element 14 is marked it is shown in the Fig 8. The corresponding marked edges are shown in below Fig 9.

Fig 9 adjacent matrix

Fig 10 adjacent matrix

From Fig 10. the next minimum element 16 is marked.

 

 

 

Fig 11, Adjacent matrix

From Fig 11 the next minimum non zero element18 is marked. But while drawing the edges it forms the circuit so we remove and mark it as 0 instead of 18.

Fig 12 circuit (2,3,4,7)

Next, we go to next minimum element that is 22 it is marked and shown in same Fig 12. and the both marking process of the edges 18 and 19 were shown below figs.

Fig 13

Fig 14

The next minimum element is 24 while marking that its forms a circuit so we mark 0 instead of 24 and we move to the final marking process that is the minimum element is 25 is shaded and edges are colored.

Fig 15 final stage.

We have to study the minimum cost spanning tree using the Matrix Algorithm and find the minimum cost is 99 [1]. So, the final path of minimum cost of spanning is {1, 6}, {6, 5}, {5, 4}, {4, 3}, {3, 2}, {2, 7}.

Comments

Post a Comment

Popular posts from this blog

theorem of graph theory

 THEOREM 1: Let T_0 be minimum cost spanning tree in G. then every in- tree edge in T_0 must be a minimum cost edge in the fundamental cut set associated with it.  Proof:  Let (X;(X)) ̅ be the fundamental cut set associated with the in- tree edge(i;j)in T_0. So, (i;j)is the only in-tree edge in  (X;(X)) ̅, and deletion of (i; j) from T_0disconnects it into smaller trees, one spanning the nodes in X, and the other spanning the nodes in X ̅.   Suppose a minimum cost edge in the cut set (X;(X)) ̅ is an out-of-tree edge (p; q) and not (i; j)    i, e.,         c_pq<c_ij  . then replacing, (i; j) in T_0 by (p; q) leads to spanning tree T_1  with cost = cost of T_0-(c_ij- c_pq) < cost of T_0,  contradicting, the optimality of T_0    hence (i; j) must be minimum cost edge in the fundamental cut set (X;(X)) ̅ associated with it in T_0. THEOREM 2: Let T_0 be minimum cost spanning tree in G. then every in...
Read more

PRIM’S ALGORITHM

Image
  PRIM’S ALGORITHM   Prim’s algorithm is a greedy algorithm that is used to find a minimum spanning tree (MST) of a given connected weighted graph. This algorithm is preferred when the graph is dense. The dense graph is a graph in which there is a large number of edges in the graph. This algorithm can be applied to only undirected connected graph and there should not be any negative weighted edge. In this case, the algorithm is quite efficient. Since there are no non-negative weight cycles, there will be a shortest path whenever there is a path.             The steps to find minimum spanning tree using Prim’s algorithm are as follows: 1. If graph has loops and parallel edges than remove loops and parallel edges of that graph. 2. Randomly choose any node, labelling it with a distance of 0 and all other nodes as ∞. The chosen node is treated as current node and considered as visited. All other nodes are considered as unvisited....
Read more
  ALGEBRA What is Algebra? Algebra helps solve the mathematical equations and allows to derive unknown quantities, like the bank interest, proportions, percentages. We can use the variables in the algebra to represent the unknown quantities that are coupled in such a way as to rewrite the equations. The algebraic formulas are used in our daily lives to find the distance and volume of containers and figure out the sales prices as and when needed. Algebra is constructive in stating a mathematical equation and relationship by using letters or other symbols representing the entities. The unknown quantities in the equation can be solved through algebra. Some of the main topics coming under algebra include Basics of algebra, exponents, simplification of algebraic expressions, polynomials, quadratic equations, etc Branches of Algebra As it is known that,  algebra is the concept based on unknown values called variables. The important concept of algebra is equations. It follows various...
Read more