The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+26 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

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 then 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 thier confidence a bit.

Or atleast they could have mentioned t and t' are only (unique) MST possible on then 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 thier confidence a bit.

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

+7

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

+6

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.

+4

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.

+1

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.

+2

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

0

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

+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 t^{2} in any case. Please clarify

+1

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

+6 votes

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.5k
- Digital Logic 2.1k
- Programming & DS 4k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,079 questions

45,572 answers

132,066 comments

49,040 users