The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
3.1k 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
asked in Algorithms by Boss (18.2k points)
edited by | 3.1k views
0
Please remove the tag calculus. It is misleading.
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.

3 Answers

+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.
answered by Boss (18.2k points)
edited by
+8
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.)
+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. 

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

0
Thanks :)
0
pragy can u plz provide example for mst where this is true........
+1
None of the above means None is True- not Multiple Choices are TRUE.
+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 > t2 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
Hope yu got right answer now and it's clear. Thank You.
0
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
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'.
+6 votes

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

answered by Active (2.1k points)
+1
D IS MORE CORRECT THAN B
+2 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 (15.9k points)
0
Can you Explain why T and T' are not equal and t'<t^2.

so why not ans B.


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

40,770 questions
47,479 answers
145,658 comments
62,241 users