GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
364 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 (29.5k points)   | 364 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 (6.9k 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 (671 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 May 2017
  1. akash.dinkar12

    3140 Points

  2. pawan kumarln

    1606 Points

  3. sh!va

    1580 Points

  4. Arjun

    1316 Points

  5. Devshree Dubey

    1230 Points

  6. Angkit

    1020 Points

  7. Debashish Deka

    1012 Points

  8. Bikram

    970 Points

  9. LeenSharma

    796 Points

  10. srestha

    658 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. pawan kumarln

    232 Points

  2. jjayantamahata

    106 Points

  3. joshi_nitish

    106 Points

  4. Ahwan

    96 Points

  5. Aditya GN

    63 Points


22,717 questions
29,045 answers
65,029 comments
27,454 users