TIFR CSE 2014 | Part B | Question: 4

Question

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?

• A. cost$(a, b) \geq 6$.
• B. cost$(b, e) \geq 5$.
• C. cost$(e, f) \geq 5$.
• D. cost$(a, d) \geq 4$.
• E. cost$(b, c) \geq 4$.

Comments

I feel this question too deserves the "verbal-ability" tag.

---

important key of this question is just to understand a-d >=4 which also hold a-d>=5 but more severe condition is

 a -b >= 6 even a - b >= 5 can still also exist hence a) option should be correct.

Answer 1

 

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.

Comments

is there anyone who can explain option a and d again in some another way ????

---

what happens if option b is not holding and may be the the value of edge b-e is 2

---

Hi,

There are two possible ways to approach this question, 

If the above given tree to be only possible mst then the equlities needs to be

Connecting both components using d-e = 5:

1. cost(a,b)>5
2. cost(b,e)>5.
3. cost(e,f)>5
4. cost(a,d)>5

Connecting vertex c to either of component using c-f = 4

1. cost(b,c)>4

If the above given tree needs to be one among many possible (5*2 = 10) mst then the equalities needs to be.

// which is

Connecting both components using d-e = 5:

1. cost(a,b)≥5 or cost(a,b)≥6 // should hold
2. cost(b,e)≥5. // should hold
3. cost(e,f)≥5. // should hold
4. cost(a,d)≥5 // should hold

Connecting vertex c to either of component using c-f = 4

1. cost(b,c)≥4 // should hold

Since Option D is given cost(a,d)≥4, which is inaccurate . because if  cost(a,d)=4 the edge d-e will never be present in all possible MWST. 

I think the question is prhased in a wrong way. “which of the following inequalities NEED NOT hold” instead of “which of the following inequalities is FALSE”

Please correct me if i am wrong. @Arjunsir.

Answer 2

.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)

Comments

me too with d

---

if cost(b,e) >= 4, it would also not affect the MST , (B) can also be the answer.

correct me if I'm wrong.

---

i think option d 

Answer 3

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.

Comments

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

---

Answer will be A)

Language is playing vital role in this question .

Answer 4

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!