4k views

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
edited | 4k views
0
0
(a+b)^2  >= a^2 + b^2.  Hehe. :)
0
what is the final answer now?
0
I think they missed 'Always' TRUE in question. Otherwise, every option is true for some or the other graphs.

Or atleast they could have mentioned t and t' are only (unique) MST possible on the graph G and G', then option B would be correct.

Its this sort of questions which waste lot of time of candidates in exam, also break their confidence a bit.
+1

I think t' can never equal to t2. Lets a, b, c be the edge weights of MST of T. So, if T = T', then cost of MST of T = a+b+c, and cost of MST of T'=a2+b2+c2. Now, (a+b+c)2 ≠ a2+b2+c2, Unless a=b=c=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.
edited by
0
so it can be "Less than or equal to" for all cases, right?
+1
Here (D) is the possible answer. Can anyone tell me why were marks given to all?
+1

Pragy Agarwal Sir, How option C can be true.. Please give an example... Even in case of multiple MSTs, although T and T' may be different but still t' will not be equal to t2 in any case. Please clarify

+1
@anchitjindal07 C can never be true as for single edge graphs multiple spanning trees are not possible
0
sir here by saying T' = T ... do they mean they are isomorphic ...? How can we say 2 graphs (or trees) are equal ?
0
@Arjun sir , marks to all when we have attempted ?
+2
@kuldeep marks to all means to everyone including those who didn't even read that question.
0

C is false with this graph

0
But if all edge weights of G are same then there can be different MST possible for G and G'.
0
I think "B" is the answer since "edge weights greater than one" is mentioned in the question , so weights are never one. .. So A and C are always False.

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

+1
D IS MORE CORRECT THAN B
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'
0
Can you Explain why T and T' are not equal and t'<t^2.

so why not ans B.

1
2