GATE CSE 2012 | Question: 29

Question

Let $G$ be a weighted graph with edge weights greater than one and $G'$ be the graph constructed by squaring the weights of edges in $G$. Let $T$ and $T'$ be the minimum spanning trees of $G$ and $G'$, respectively, with total weights $t$ and $t'$. Which of the following statements is TRUE?

• A. $T' = T$ with total weight $t' = t^2 $
• B. $T' = T$ with total weight $t' < t^2$
• C. $T' \neq T$ but total weight $t' = t^2$
• D. None of the above

Comments

@Arjun Sir, @srestha ma'am,

For such a question, What should we opt for option B or D? 
Please Clarify.

---

Isn't that clearly mentioned in the answer?

---

 @Arjun sir,
Can we consider two tree equivalent even when they have different weighted edges but are isomorphic to each other ?

So here equality means isomorphism ?

Answer 1

When the edge weights are squared the minimum spanning tree won't change.

$t'$ < $t^2$, because sum of squares is always less than the square of the sums except for a single element case.

Hence, B is the general answer and A is also true for a single edge graph. Hence, in GATE 2012, marks were given to all.

Comments

@reboot

yes that’s correct, it’s only true if the weights are positive. But if you read the question, it is given that each weight in the original graph G is greater than 1 which implies that, all weight are positive and square of weight will never produce the original value.

---

I was right on track but I missed single element case so got wrong answer as B

---

This question can be a good MSQ

Answer 2

we can make different as well as same MST also so option (d) is correct option

Comments

D IS MORE CORRECT THAN B

Answer 3

d will be the answer. t' may or may not b equal to t . if distict weight it will be equal and if same weight then diffrent structure may be obtained . plus the weight of t <= t'

Comments

Can you Explain why T and T' are not equal and t'<t^2.

so why not ans B.

Answer 4

Here D is correct. As everyone said B option is true but in one case it fails if there is a graph with 2 Nodes and edge weight is 1 then it t1==t^2, thus t1<t^2 will fail. And definitely MST doesn't change When edge weights are squared.

Comments

@PRG1499 But in the question it is given that edge weights should be greater than one.

---

Yes, but we can get a different structure from 2 edges having the same value, thus option B fails atleast one test case.