in Algorithms edited by
12,736 views
55 votes
55 votes

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?

  1. $T' = T$ with total weight $t' = t^2 $
  2. $T' = T$ with total weight $t' < t^2$
  3. $T' \neq T$ but total weight $t' = t^2$
  4. None of the above
in Algorithms edited by
by
12.7k views

4 Comments

@Arjun Sir, @srestha ma'am,

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

0
0
Isn't that clearly mentioned in the answer?
0
0
edited by

 @ 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 ?

0
0

5 Answers

70 votes
70 votes
Best answer
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.
edited by

4 Comments

How is option A correct for single edge graph since edge weight has to be >1?
0
0
edited by
In question they didn’t mention distinct edges.

If I assume all edge weights as same then either $T' = T$ or $T' \neq T$ but $t' < t^2$.
0
0

@gatecse and @arjun sir

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

This line is only true when we consider only positive edge weights, right?

 

1
1
12 votes
12 votes

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

1 comment

D IS MORE CORRECT THAN B
2
2
7 votes
7 votes
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'

1 comment

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

so why not ans B.
0
0
0 votes
0 votes
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.

2 Comments

edited by
@PRG1499 But in the question it is given that edge weights should be greater than one.
0
0
Yes, but we can get a different structure from 2 edges having the same value, thus option B fails atleast one test case.
0
0
Answer:

Related questions