edited by
17,446 views
70 votes
70 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_______________.

edited by

5 Answers

Best answer
106 votes
106 votes
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$
edited by
14 votes
14 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

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

Answer:

Related questions

80 votes
80 votes
7 answers
1
makhdoom ghaya asked Feb 13, 2015
28,736 views
The least number of temporary variables required to create a three-address code in static single assignment form for the expression $q + r / 3 + s - t * 5 + u * v/w$ is_...
32 votes
32 votes
9 answers
2
makhdoom ghaya asked Feb 13, 2015
24,370 views
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.