32 votes 32 votes Consider a weighted complete graph $G$ on the vertex set $\{v_1,v_2,.....v_n\}$ such that the weight of the edge $(v_i, v_j)$ is $2|i-j|$. The weight of a minimum spanning tree of $G$ is: $n-1$ $2n-2$ $\begin{pmatrix} n \\ 2 \end{pmatrix}$ $n^2$ Algorithms gatecse-2006 algorithms spanning-tree normal + – Rucha Shelke asked Sep 16, 2014 edited Jan 10, 2018 by Puja Mishra Rucha Shelke 14.6k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments Puja Mishra commented Jan 10, 2018 reply Follow Share https://www.geeksforgeeks.org/gate-gate-cs-2006-question-11/ 0 votes 0 votes sahil_malik commented Oct 27, 2018 reply Follow Share what will be the case if weight of the edge v(i, j) is | i+j | ? 0 votes 0 votes Vegeta commented Nov 4, 2018 reply Follow Share I think it would be [(n+1)(n+2)/2] - 3. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes To solve the above question we can consider a complete graph with 3 vertices. The weight of minimum spanning tree of a Complete Graph of 3 vertices will be 4 (2 (edge 1,2)+2 (edge 2,3)). The only option satisfying G with n=3 is option B (i.e 2n-2). Chirag Shilwant answered Dec 9, 2019 Chirag Shilwant comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes By drawing two spanning trees for n=3, and n=4. It can be easily seen that pattern of weights is is indicating that the correction option is choice (b) i.e 2n-2 Girjesh Chouhan answered May 9, 2020 Girjesh Chouhan comment Share Follow See 1 comment See all 1 1 comment reply vermavijay1986 commented Jan 15, 2021 reply Follow Share The solution is obtained for particular cases only, one should provide the general solution. For a general solution refer the solution given by me @vermavijay1986 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Recall the definition of Complete Graph , then the solution is straightforward: Refer the attached file below: vermavijay1986 answered Jan 15, 2021 vermavijay1986 comment Share Follow See all 0 reply Please log in or register to add a comment.