GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
355 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.1k points)   | 355 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 Mar 2017
  1. rude

    4768 Points

  2. sh!va

    3054 Points

  3. Rahul Jain25

    2920 Points

  4. Kapil

    2728 Points

  5. Debashish Deka

    2602 Points

  6. 2018

    1574 Points

  7. Vignesh Sekar

    1422 Points

  8. Akriti sood

    1378 Points

  9. Bikram

    1342 Points

  10. Sanjay Sharma

    1126 Points

Monthly Topper: Rs. 500 gift card

21,517 questions
26,844 answers
61,157 comments
23,181 users