The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+20 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**?

- $T' = T$ with total weight $t' = t^2 $
- $T' = T$ with total weight $t' < t^2$
- $T' \neq T$ but total weight $t' = t^2$
- None of the above

+32 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.

$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.

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.)

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.)

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

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.

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.

in case of multiple min spanning tree also. t > t^{2} and T=T'.

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

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'.

"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

^{2} in any case. Please clarify

@anchitjindal07 C can never be true as for single edge graphs multiple spanning trees are not possible

+5 votes

- All categories
- General Aptitude 1.1k
- Engineering Mathematics 4.5k
- Digital Logic 1.9k
- Programming & DS 3.3k
- Algorithms 2.9k
- Theory of Computation 3.6k
- Compiler Design 1.4k
- Databases 2.7k
- CO & Architecture 2.4k
- Computer Networks 2.7k
- Non GATE 901
- Others 1.2k
- Admissions 246
- Exam Queries 433
- Tier 1 Placement Questions 17
- Job Queries 42
- Projects 4

32,330 questions

39,145 answers

108,247 comments

36,501 users