GATE CSE 2015 Set 1 | Question: 43

Question

The graph shown below has $8$ edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight $36$ and contains the edges: $\{(A, C), (B, C), (B, E), (E, F), (D, F)\}$. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all $8$ edges of this graph is_______________.

Comments

the key point is given in the question "distinct" edges that easily gives the answer, what if they doesn't tell about edge are distinct or not, then we have to go with 66 as answer isn't it.

---

@Aks9639

I think so.

---

66 if not distinct,

69 if distinct

Answer 1

Let's start with vertex A. 

From A we can go to B or C but we are going to C having weight 9 as it may be the case edge (a-b) has weight 10,11,12.....but for choosing edge (a-c), min 10 is sufficient and we have to consider min also for our answer. So take (a-b) as 10.

Now we are at C. from C we can go to B or D, but going to B with weight 2 as (c-d) may be having weight '3'. So take (c-d) as 3.

We are at B now, and from there we are going to E with weight 15 but not following (c-d) which we assumed 3 before. so (c-d) is surely > 15. Let's take it 16(min). So (c-d) is 16 as for now.

Now come to E. we are selecting (e-f) bcoz (e-d) may be having weight 5. Coming F we are selecting    (f-d) having weight 6, so (e-d) surely >6 and so min (e-d) is 7.

And hence we can deduce 69 as the answer.

Also one thing is to be noted, we have followed prim's approach while solving...

Comments

nt a gd approach ... see the best answer and its comments ...