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

66 if not distinct,

69 if distinct

---

Nice

---

Done ✅

Answer 1

Consider the cycle $ABC$. $AC$ and $BC$ are part of minimum spanning tree. So, $AB$ should be greater than $max(AC, BC)$ (greater and not equal as edge weights are given to be distinct), as otherwise we could add $AB$ to the minimum spanning tree and removed the greater of $AC, BC$ and we could have got another minimum spanning tree. So, $AB > 9$.

Similarly, for the cycle $DEF, ED > 6$.

And for the cycle $BCDE, CD > 15$.

So, minimum possible sum of these will be $10 + 7 + 16 = 33$. Adding the weight of spanning tree, we get the total sum of edge weights

$= 33 + 36 = 69$

Comments

If it is told that integer edge weights are not distinct then

DE = 6, AB=9, CD=15.

So total weight will be:

9+6+15+36

= 66

---

 @chandra sai it would be 8. since ED is >6 which is 7, so in cycle BEDC maximum edge is 7. And given that graph is distinct we can not take 6. Because 6 is already available in graph see edge FD. 

---

@Ayush Upadhyaya nice explaination sir

Answer 2

The minimum possible sum of weights of all 8 edges of this graph is 69..
first we compare A to C and A to B we find 9 at A to C it means A to B must greater than A to C and for minimum possible greater value than 9 will b 10 .. so first we conclude 10.
after that we have again two conflict pair B to E and C to D in which we select B to E 15 which C to D possible weight 16.
now we have E to D and F to D in which we select F to D 6 means E to D must be greater than 6 so possible value greater than 6 is 7 .
so missing weight are
A to B ---->10
C to D---->16
E to D---->7

Comments

69 is correct. But you must proceed taking cycles: ABC first, DEF second and then BCDE. Suppose DF was 20, then DE should be 21 and CD should be 22.

---

Yup this method waste my whole day .:)

---

u have followed the sequnce of  cycles to be taken in given question like ABC first, DEF second and then BCDE.Is there any constraint to follow this sequnece or any condition we have to check

Answer 3

Start with any vertex and apply prims algo and fix weights of the edges accordingly.

Answer 4

First, all edge weights are different.

Consider ABC portion of given graph, after including edge AB it will form a cycle in MST so AB is not included & it's weight is more then AC & BC (=10). 

Now consider DEF portion, and apply the same above logic, weight of CD > wt. of EF & wt. of FD (=7).

Same logic in BECD, Wt. CD = 16

16+7+10=33

33+36(Wt of MST) = 69.

Answer 5

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 ...

Answer 6

distinct told so 10,7,16  can be missing edge sum is 33+36 (given)= Total 69