retagged by
469 views
1 votes
1 votes

retagged by

1 Answer

2 votes
2 votes

Edge weights of MST are given. MST cost adds up to 34.Now we need to find the minimum value of sum of {a,b,c,d,e,f,g} given that edge weight of each edge is distinct. 

So one solution that immediately comes to mind to find min of a,b,c,d,e,f,g is to assign a,b,c,d,e,f,g with minimum unassigned value. 1,2,3,5,6,7 and 10 have already been used so assign 4,8,9,11,12,13,14 to the rest of labeled edges(I am not considering 0 or -ve as edge wt).4+8+9+11+12+13+14 = 71.

but if you observe that if we use value 4 in any of a,b,c,d,e,f,g the 4 has to be the part of MST.Using value 4 will do two things

1) edge labeled 4 will definitely be part of MST (you can try this.use Kruskal) &

2) Minimum MST tree will be changed (cost lower than 34 and also different MST which is not allowed)

So we can't use 4.Next, best option is to use 15

8+9+11+12+13+14+15 = 82

NOTE - assigning these value to egdes a,b,c,d,e,f,g cannot be done arbitrarily.say we cannot assign 'a' edge wt 8.Doing this would alter min MST and its cost.But all this is immaterial to obtaining the solution of this question  

Related questions

5 votes
5 votes
1 answer
3
2 votes
2 votes
1 answer
4
shivanisrivarshini asked Apr 21, 2016
656 views