retagged by
4,965 views
35 votes
35 votes

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$.
retagged by

4 Answers

Best answer
21 votes
21 votes

 

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.

edited by
7 votes
7 votes

.Okay let's say I assign the minimum weight possible as from the inequality given in the question to the edges in the graph I get the below graph

Now using kruskal method I start forming the MST

(1)First I choose edge AE with weight -2.

(2)Then Edge BD(3)

(3)Then Edge BF(3)

(4)Then Edge CF(4)

At this state, I have my graph as

Now my graph has two disconnected components namely AE and BDCF.

I won't use edge BC because it would form a cycle. So I will reject this.

Now I can choose to join these two components with either edge AD(4), BE(5),DE(5),EF(5),AB(6).

We note that the edge DE was included in MST which means the next least value weight edge available to my kruskal algorithm was 5 and not 4, otherwise edge AD would have been chosen. And since I had a choice, so I took any one of BD,BE or EF and made my MST. So cost of BD,BE,EF is fine.

Hence, the cost of AD must not be atleast 4. Infact cost of AD $\geq 5$

Answer-(D)

6 votes
6 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.
1 votes
1 votes

option a) is the answer, because that's the inequality which is not entirely applicable on given MST because cost (a,b)>=6 makes it's the heaviest edge of entire MST and also including edge ab will make a cycle. So, ab is the heaviest edge among all and on top of that it's making cycle and Kruskal will never pick it up and hence this inequality will need not be there.

TL;DR - Cycle property applicable for option a).

whereas 

cost (a,d)>=4 .

Yes, cost (a,d)=4 will surely make Kruskal to pick to edge ad over de and our MST will change, in fact if you take cost (a,d) = 5 it will still change MST as now Kruskal has option to pick edge ad or de and it can pick edge ad and drop de whereas cost (a,d) >5 say {6,7,8, . . . } edge ad will never be picked because it will be the heaviest edge in cycle "adea" and Kruskal will go with edge de and our MST's structure remains same. Therefore cost (a,d)>4 holds when cost (a,d)>5 and hence option d) is not the answer!

Answer:

Related questions