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.

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

+4

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.

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.

+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$

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$

0

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

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

is it 6 or 8??please clarify

+25

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

0

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?

0

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

0

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

0

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$ ?

+13 votes

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

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

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

16+7+10=33

33+36(Wt of MST) = **69**.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,292 answers

198,230 comments

104,909 users