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

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

In the first line it would be  "AC and BC are part of minimum spanning tree". Must be some typo.

---

if edges are not distinct weight in that case, should AB=9, ED=6, CD=15??? @Arjun sir

---

What if edge weight are not distinct . Should the answer be 66 ?

---

in the same above question,

what will be the weight of CD if BE=5(in the cycle BEDC)?

is it 6 or 8??please clarify

---

Cut and cycle property both asked in this question.

Cycle property states that if edge 'e' has maximum weight in some cycle of G, then that edge won't be included in mst of G.

Using this rule,

If we notice cycle ABC, maximum weight edge which is in mst is 9, that means, there must have been an edge weight strictly greater than 9 due to which this edge i.e. AB was not included in mst for G.

Since, question asks for the minimum weight of total edges, we assume this value is 10.

Using the same concept, edge ED is of weight 7.

Cut property of MST states for any cut (S,V-S) of a graph G, if there is an edge 'e' that is lightest among all the edges that cross the cut( cross the cut means one end of edge e exists in S, and another in V-S) then that edge is safe for adding to MST.

Since, we can see the cut (ABC,DEF), BE and CD cross the cut.

Since, BE is included in mst of G, this means this was lightest of all edge crossing this cut.

So, CD should have been at least 16.

So, now total weight of all edges =69

---

Just wow !!! very much clear explanation :-)

---

Very gd explanation ....

---

@chandra sai,

 It is 8 if BE=5 since greatest of all(5,2,7)

---

I have same doubt sanyam56, correct us @arjun sir

---

I understand the cycle part but I have a question that If we apply prim algorithm then we can go A->B or A->C now in question it go A->C that means A->B must be greater so minimum grater is 10. Now in question it shows B->C is 2 but not C->B that means it use kruskal algorithm but if we consider prim then it can go 2 direction C->B or C->D we choose C->B that is 2 that means C->D will be greater it should be 3 as wll as in between E->F and E->D E->D will bw 5 ? am i wrong?

---

@Ayush Upadhyaya AMAZING EXPLAINATION. THANK YOU

---

@Ayush Upadhyaya

After deciding ED = 7 ..we can also apply cycle property to BCDE right 

So CD must be max weight edge in BCDE as it is not included in MST

Hence we can take CD = 16

Am I right ??

---

@jatin khachane 1_Yes you can do, but only after ED is evaluated otherwise you don't know whether ED was larger or CD.

---

Ayush, you said

If we notice cycle ABC, maximum weight edge which is in mst is 9, that means, there must have been an edge weight strictly greater than 9 due to which this edge i.e. AB was not included in mst for G.

Isnt this incorrect? AB can still be 9 and not get included in MST. For distinct weight graph, MST is unique. For non distinct weight graph, there can be multiple MSTs. The question nowhere says the given MST is unique or graph have distinct edge weights? 

Or, does the following statement in the question:

 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. 

indeed mean that the MST given in the question is unique? and thats why you said $w(AB)>9$ ?

---

cycle bcde should not be considered as both cd and de are not part of the MST, instead cycle bcdfe must be considered to calculate edge weight of cd.

---

In question they did not mention that edges are distinct can AB=9 ,CD=15,ED==6

just a dounbt!!!

---

The graph shown below has $8$ edges with distinct integer edge weights.

---

@ Ayush Upadhyaya

 

Very Well  explanation.

Thank You So much.

---

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

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.