The Gateway to Computer Science Excellence
+46 votes

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

in Algorithms by Boss (30.8k points)
edited by | 6.1k views
Before looking at very good answer as provided by various Guys.

Please think on point, If Graph has distinct integer edge weights and MST does not contain particular edge then it's weight should be greater than other edges forming cycle due to inclusion of this particular edge.
In prime algorithm why not CD don't be 3?

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.



I think so.

5 Answers

+77 votes
Best answer
Consider the cycle $ABC$. $AC$ and $AB$ 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$
by Veteran (431k points)
edited by
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?




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.
+13 votes

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

by Active (5k points)
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
+5 votes

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

by Active (4.8k points)
edited by
+1 vote

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

by Active (1.9k points)
edited by
nt a gd approach ... see the best answer and its comments ...
0 votes

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


33+36(Wt of MST) = 69.

by (431 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
104,909 users