GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
349 views

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$.
asked in Algorithms by Veteran (29k points)   | 349 views

2 Answers

+6 votes
Best answer

Now check this diagram, this is forest obtained from above given graph using Kruskal's algorithm for MST.

So according to the question edge $d-e$ has weight 5 and it is included in the formation of MST. Now if edges $b-e$ and $e-f$ has weight greater than 5 than it is not a problem for our MST because still we will get the given tree as Kruskal's algorithm takes the smallest weighted edge without forming a cycle.

Cost of edge $b-c \geq 4$ may also lead us to the same tree as above though Kruskal's algorithm will have choice between $c-f$ and $b-c$.

Now if the edge weight of $a-d$ becomes 4, it is guaranteed that Kruskal's algorithm will not select edge $d-e$  because its edge cost is 5, and hence the tree structure will change. But there can be the case where edge weight is greater than 4 and we still get the same tree (happens when $a-d \geq 5$). Because in the question they asked to point out an unnecessary condition this case is not the answer as we need $a-d \geq 5$ which implies $a-d \geq 4.$

Now notice option A. Put $a-b = 5.$ The given MST would not change.  So, this condition is not always necessary and hence is the answer..

 

Therefore option A is the answer .

 

answered by Boss (7k points)  
selected by
But the question is not "will not" but rather "need not".
How will it make difference @Arjun sir ? I just explained bit more in the last sentence .
a-d cannot be 4- your reason is correct. But that does not make D choice the answer rt?
sir in that way option A having wt >=6 is not necessary , so it need not be there . is that what you mean ?
yes - because thats what is asked in question :) For objective exam you will get negative even if your method is correct and final answer wrong :)
edited now !! Thanks a ton . Each and every word zaroori hota hain :P :)
why we would put a-b = 5?According to option A it should be >=6

There are ONLY two reasons, that Kruskal do not include any edge in MST-

  • either that edge forms cycle or
  • there is an equivalent edge weight and Kruskal choose to pick another one.


Tightest lower bound on every edge is -
$cost(b, c) \geq 4$ and every other edge cost $\geq$ 5.

+2 votes
I think answer should be D, bcoz if cost(a,d) =4, then it will come in MST( Min spanning tree). So this condition need not necessary hold.
answered by Junior (659 points)  
I think $cost(a, d) \geq 4$ is a MUST NOT condition, otherwise it will change the cost of MST when $cost(a, d) = 4$, whereas $cost(a, b) \geq 6$ is a NEED NOT condition. Along the same lines, remaining options are MUST conditions.

Related questions

Top Users Feb 2017
  1. Arjun

    5224 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3748 Points

  4. Aboveallplayer

    2986 Points

  5. Debashish Deka

    2356 Points

  6. sriv_shubham

    2298 Points

  7. Smriti012

    2142 Points

  8. Arnabi

    2008 Points

  9. sh!va

    1654 Points

  10. mcjoshi

    1628 Points

Monthly Topper: Rs. 500 gift card

20,832 questions
25,989 answers
59,623 comments
22,046 users