Arjun Suresh (talk | contribs) (Created page with "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 span...") |
Arjun Suresh (talk | contribs) |
||
(19 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
Let $G$ be a weighted graph with edge weights greater than one and $G'$ be the graph constructed by | 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'$, | 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'''? | + | respectively, with total weights $t$ and $t'$. Which of the following statements is '''TRUE'''? |
− | |||
− | ( | + | (A) $T' = T$ with total weight $t' = t^2 $ |
− | (C) $T' \neq T$ but total weight $t' = | + | '''(B) $T' = T$ with total weight $t' < t^2$''' |
+ | |||
+ | (C) $T' \neq T$ but total weight $t' = t^2$ | ||
(D) None of the above | (D) None of the above | ||
+ | |||
+ | |||
+ | ==={{Template:Author|Arjun Suresh|{{arjunweb}} }}=== | ||
+ | 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. | ||
+ | |||
+ | |||
+ | |||
+ | {{Template:FBD}} | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | [[Category:Algorithms & Data Structures Questions from GATE]] | ||
+ | [[Category:GATE2012]] |
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' = t^2$
(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 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.
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' \eq T$ with total weight $t' = t^2 $
(B) $T' \eq T$ with total weight $t' < t^2$
(C) $T' \neq T$ but total weight $t' = t2$
(D) None of the above