GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
327 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 (28.1k points)   | 327 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.8k 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.

+1 vote
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 (641 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 Jan 2017
  1. Debashish Deka

    8126 Points

  2. sudsho

    5042 Points

  3. Habibkhan

    4706 Points

  4. Vijay Thakur

    4458 Points

  5. Bikram

    4348 Points

  6. saurabh rai

    4212 Points

  7. Arjun

    4010 Points

  8. santhoshdevulapally

    3722 Points

  9. GateSet

    3292 Points

  10. Sushant Gokhale

    3286 Points

Monthly Topper: Rs. 500 gift card

19,122 questions
24,033 answers
52,725 comments
20,276 users