edited by
612 views
1 votes
1 votes

Consider the following undirected graph with some edge costs missing.

Suppose the wavy edges form a Minimum Cost Spanning Tree for $G$. Then, which of the following inequalities NEED NOT hold?

  1. $cost(a,b)\geq 6$.
  2. $cost(b,e)\geq 5$.
  3. $cost(e,f)\geq 5$.
  4. $cost(a,d)\geq 4$.
  5. $cost(b,c)\geq 4$.

Please someone solve and explain :)

edited by

1 Answer

Best answer
4 votes
4 votes

option d

if you put the cost of enequalities then  minimum cost spanning tree must be a all weavy edges.

then we put the  cost of edges one by one if mst is only weavy edges then it is right otherwise it is wrong

selected by

Related questions

0 votes
0 votes
0 answers
1
3 votes
3 votes
0 answers
2
1 votes
1 votes
2 answers
4
gauravkc asked Apr 5, 2018
1,188 views
Can someone solve this?Also please attempt this question on Algorithms time complexity if interested :)https://gateoverflow.in/210836/algorithms-time-complexity