(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...")
 
 
(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' \eq T$ with total weight $t' = t^2 $
 
 
   
 
   
(B) $T' \eq T$ with total weight $t' < t^2$
+
(A) $T' = T$ with total weight $t' = t^2 $
 
   
 
   
(C) $T' \neq T$ but total weight $t' = t2$
+
'''(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]]

Latest revision as of 11:29, 15 July 2014

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


Solution by Arjun Suresh

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.





blog comments powered by Disqus

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