The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+27 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
asked in Algorithms by Boss (18.3k points)
edited by | 4k views
Please remove the tag calculus. It is misleading.
(a+b)^2  >= a^2 + b^2.  Hehe. :)
what is the final answer now?
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.

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.

3 Answers

+41 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.
answered by Boss (18.3k points)
edited by
so it can be "Less than or equal to" for all cases, right?
Here (D) is the possible answer. Can anyone tell me why were marks given to all?

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

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

C is false with this graph

But if all edge weights of G are same then there can be different MST possible for G and G'.
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.
+7 votes

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

answered by Active (2.2k points)
+3 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'
answered by Boss (16.1k points)
Can you Explain why T and T' are not equal and t'<t^2.

so why not ans B.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
47,925 questions
52,325 answers
67,789 users