edited by
16,249 views
59 votes
59 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
edited by

5 Answers

Best answer
75 votes
75 votes
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
7 votes
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'
0 votes
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.
Answer:

Related questions

111 votes
111 votes
9 answers
1
gatecse asked Sep 12, 2014
34,608 views
Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to$15$$30$$90$$36...
71 votes
71 votes
14 answers
3
gatecse asked Sep 26, 2014
28,614 views
A list of $n$ strings, each of length $n$, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is$O (n \log...
45 votes
45 votes
3 answers
4
gatecse asked Aug 21, 2014
11,809 views
Which one of the following is NOT logically equivalent to $¬∃x(∀ y (α)∧∀z(β ))$ ?$∀ x(∃ z(¬β )→∀ y(α))$$∀x(∀ z(β )→∃ y(¬α))$$∀x(∀ y(�...