GATE2012 q29
Revision as of 13:09, 8 December 2013 by Arjun Suresh (talk | contribs)

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

Retrieved from "https://gatecse.in/w/index.php?title=GATE2012_q29&oldid=1234"

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