in Algorithms edited by
9,975 views
47 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
10k views

9 Comments

Please remove the tag calculus. It is misleading.
0
(a+b)^2  >= a^2 + b^2.  Hehe. :)
5
what is the final answer now?
0
edited by
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.
0

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
Always true is missing in the statement of question which creates a lot of ambiguity.
0

@Arjun Sir, @srestha ma'am,

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

0
Isn't that clearly mentioned in the answer?
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

5 Answers

61 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

23 Comments

A is true for single edge graph

B is true for most graphs

C is true when G has multiple MSTs.

Since option D says None of the above, shouldn't D be the answer?

Are you sure that marks were awarded to all for this question? (Please cite some source.)
31

None of the above would mean all others are false rt? Or the question should have asked "Always TRUE". Here is the answer key same file as published by IIT-K. 

http://gatecse.in/w/images/b/b5/Key_CS_2012.pdf

This official site supposedly still has the key. But as usual no words for IIT IT department. 

http://gate.iitk.ac.in/gate2012/anskeys.php

13
Thanks :)
0
pragy can u plz provide example for mst where this is true........
0
None of the above means None is True- not Multiple Choices are TRUE.
2
For D to be correct, A, B and C should be FALSE. Here, A and B can be TRUE. But now they stopped giving marks to all and so should go for the most general case- B here.
7
Then the question should have been "ALWAYS TRUE", though you are correct- D can also be chosen. May be due to this ambiguity, GATE gave marks to All.
3

in case of  multiple min spanning tree also. t > t2 and T=T'.

I don't understand your 3rd point. Could u explain? @pragya

2
Sir ,will you plz explain how single edge graph is satifying option a.?Like if i take a graph T with two vertices A n B with edge weight 2 and so  T' will have edge weight 4 ,so MST will have T=T' but  not t=t'.
0
"Let G be a weighted graph with edge weights greater than one and G′." It will always greater than G' so it will not affect any how. @neal
0
Hope yu got right answer now and it's clear. Thank You.
1
edited by
so it can be "Less than or equal to" for all cases, right?
0
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
2
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 ?
0
@kuldeep marks to all means to everyone including those who didn't even read that question.
4
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.
0
How is option A correct for single edge graph since edge weight has to be >1?
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

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

 

0
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
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 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
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 votes
Answer is D.

Take a complete graph with 3 vertices and each edge is 2. So if we square all, we still can have different types of mst than previous with same cost. Since all options are comparing T and T', they're all wrong, as we can't say. T and T' may or may not be equal. Hence D.
Answer:

Related questions