Question 8737 – GATE 2013
April 30, 2024Question 10208 – Engineering-Mathematics
April 30, 2024Question 8833 – Minimum-Spanning-Tree
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?
Correct Answer: D
Question 5 Explanation:
Let graph G be
Then MST for G is,
Now let’s square the weights,
Then MST for G’ is,
So, from above we can see that T is not necessarily equal to T’ and moreover (t1) < (t2).
So option (D) is correct answer.
Then MST for G is,
Now let’s square the weights,
Then MST for G’ is,
So, from above we can see that T is not necessarily equal to T’ and moreover (t1) < (t2).
So option (D) is correct answer.
T’ = T with total weight t’ = t2
T’ = T with total weight t'<t2</t
T’ ≠ T but total weight t’ = t2
None of the above
Subscribe
Login
0 Comments