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) |
||
| Line 2: | Line 2: | ||
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' | + | (A) $T' = T$ with total weight $t' = t^2 $ |
| − | (B) $T' | + | (B) $T' = T$ with total weight $t' < t^2$ |
(C) $T' \neq T$ but total weight $t' = t2$ | (C) $T' \neq T$ but total weight $t' = t2$ | ||
(D) None of the above | (D) None of the above | ||
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
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
GATECSE