closed by
786 views

3 Answers

Best answer
3 votes
3 votes

b. Let cost(b,e) = 4. Now, we should replace (d, e) with (b, e) in MST

c. Let cost(e, f) = 4. Now, we should replace (d, e) with (e, f) in MST

d. Let cost(a, d) = 3. Now, we should replace (d, e) with (a, d) in MST (actually cost(a,d) ≥ 5)

e. Let cost(b, c) = 3. Now, we can replace (c, f) with (b, c) in MST

a. cost(a,b) ≥ 3, won't affect the MST. 

selected by
0 votes
0 votes
option b ,c ,d ,e  data is insufficeint
so inequality may or may not holds
for options a )  a->b >= (a->e + e->d + d->b) =6
:0
0 votes
0 votes

Ans: because we have given wavy edges form MST So, for verification of option A we have to check that with MST how many cost to reach at a->b then we will get a->e->d->b = -2+5+3 = 6 so in given option a with cost(a,b)>= 6 this is posible coz , cost equal then we can reach at a to b with that edge but we don't consider that edge while making MST so cost must be >6 not equal to 6 so option A is Need Not HOLD. Like wise if you check for other option then enequality is holding...

Related questions

0 votes
0 votes
3 answers
1
1 votes
1 votes
1 answer
2
Ram Swaroop asked Jan 30, 2019
1,561 views
Consider a simple undirected weighted graph G(V, E) with 10 vertices and 45 edge, assume (u, v) are two vertices weight of a edge is =4lu- vl then the minimum cost of the...
0 votes
0 votes
2 answers
4
Nidhi Budhraja asked Aug 31, 2018
734 views
Q1) Why is the path between a pair of vertices in a minimum Spanning tree of an undirected graph not the shortest( minimum weight) path?