GATE CSE
First time here? Checkout the FAQ!
x
+7 votes
435 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 (39.7k points) 256 1308 1941 | 435 views

2 Answers

+9 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 (7.1k points) 7 29 79
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.

sachin then ad >=5 , but in given option its >=4 ?
+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 (741 points) 6 8 28
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.
i also agree that (a,d)>=4 is not a must condition because if(a,d) = 4 then we would have selected (a,d) instead of (d,e) and cost(a,b)>=6 is need not condition as (a,d) = 5 still it would not change MST

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23398 Points

  2. Bikram

    17078 Points

  3. Habibkhan

    8280 Points

  4. srestha

    6300 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4978 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4348 Points

  9. sushmita

    3970 Points

  10. Rishi yadav

    3804 Points


Recent Badges

Commentator Shivam Chauhan
Notable Question set2018
Nice Comment srestha
Notable Question set2018
Regular Shankar Jha
Popular Question Shubhanshu
Good Comment mcjoshi
Notable Question antarachoudhury
Popular Question shweta12345
Good Comment Rohan Mundhey
27,325 questions
35,176 answers
84,122 comments
33,280 users