Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 11: | Line 11: | ||
(D) None of the above | (D) None of the above | ||
| − | + | 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. | ||
| + | Hence, B is the answer. But for a single edge graph A is also true. Hence, in GATE 2012, marks were given to all. | ||
<div class="fb-like" data-layout="standard" data-action="like" data-share="true"></div> | <div class="fb-like" data-layout="standard" data-action="like" data-share="true"></div> | ||
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?
(A) $T' = T$ with total weight $t' = t^2 $
(B) $T' = T$ with total weight $t' < t^2$
(C) $T' \neq T$ but total weight $t' = t2$
(D) None of the above
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. Hence, B is the answer. But for a single edge graph A is also true. Hence, in GATE 2012, marks were given to all.
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?
(A) $T' = T$ with total weight $t' = t^2 $
(B) $T' = T$ with total weight $t' < t^2$
(C) $T' \neq T$ but total weight $t' = t2$
(D) None of the above
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. Hence, B is the answer. But for a single edge graph A is also true. Hence, in GATE 2012, marks were given to all.
GATECSE