Question

Problem 3's picture are given below.

5. (a) Let G = (V, E) be a weighted connected undirected simple graph. For n 1, let cycles in G. Modify {e1, e2,.. . ,en} be a subset of edges (from E) that includes no Kruskal's algorithm in order to obtain a spanning tree of G that is minimal among all the spanning trees of G that include the edges e1, e2, . . . , Cn. (b) Apply your algorithm in (a) to find a spanning tree that is minimal among all the spanning trees that includes the edge of weight 23 for the weighted graph in part (a) of Problem 3 8 3 2 7 16 15 14 13 6 4 19 20 6 17 18 9 7 23 24 22 21 3 2 12 11 10 4 (b) (a)

Answer 1

In order to find the minimal spanning tree using Kruskal's Algorithm, perform following steps:

1. First sort all the edges in increasing order of their weight.

2. Then pick the one with smallest weight.

3. After that start picking the smallest one's until all the vertices are connected to each other.

Keep in mind, while choosing edges, that the edges should not form a cycle, it they are doing so then discard it and move to the next edge. This algorithm uses greedy approach to find the minimal spanning tree from different spanning tree.

Using these three steps we can find the MST(Minimum Spanning Tree) for (a) part as-

Step 1:

Arranging edges in increasing order of their weight:

Edge 1's weight=1

Edges 2's weight=2

Edge 3's weight=3

Edge 4's weight=4

…..

Edge 24's weight=24

We can see weight of each edge corresponds to the no of that edge.

Step 2:

Now that we have arranged the edges, it's time to construct MST(Minimum Spanning Tree) from this.

Page 1

Taking G TAking EDGEL E DG2 2.3 1 の TakiNG EDGE 3 3 2 @TAKING EDAE 2 S TAKING EDAES 3 TAKING EDGE 6 . . TAKING EDGE 4 S. I 2 3 £DGER TAKING 456 7 1 2 3. TAKING EDGE9 4.5.4 . 1 2 SIMILARLY TAKING EDGE-10, 1112 8.9

Page 2

NOW, NE HAVE TO TAKE EDGES INSUCH A WAY IS FORMED. THAT No CYCLE 13. EDGE 13 CAN 5 4. (3 PLACED BE 8.9 10I12 C ON TAKING ETTMER EDGE 14, 15,1 A CYCLE WILL FORMED HENCE WE BE AILL SKIP IT- 1 2 3 1345. 1 8 1. TAKING EDG E 13 Ic 1 12 ON TAKING 18, 19, 20 AGAIN A.CNCLE WILL BE FORMED, MENCE SKIP TMEM. 15IN THE QUESTION, TMEY HAVE ASK ED TO TAKE SPANNING TREE HENCE, NE TAKE 23. IN AND SKIP WILL 2 1S ANS 13 23 fo 12 THs IS THE FINAL ANS ER AS TAKING 21, 22, 24 e WILL RESULT IN A CYCLE HENCE WE WILL SKIP IT