###### Question 8737 – GATE 2013

April 30, 2024###### Question 10208 – Engineering-Mathematics

April 30, 2024# Question 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 (t

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 (t

^{1}) < (t^{2}).So option (D) is correct answer.

T’ = T with total weight t’ = t

^{2}T’ = T with total weight t'<t

^{2</t}T’ ≠ T but total weight t’ = t

^{2}None of the above

Subscribe

Login

0 Comments