The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+17 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:

  1. $n-1$
  2. $2n-2$
  3. $\begin{pmatrix} n \\ 2 \end{pmatrix}$
  4. $n^2$
asked in Algorithms by Loyal (4.3k points)
edited by | 1.6k views

for a weight of the edge (vi,vj) is 2|i-j|

The weight of MST will be 2(n-1)

for a weight of the edge (vi,vj) is |i-j|

The weight of MST will be (n-1)           // for this question, there is a typo.



Option B should be 2n-2...
It seems this question needs small correction.

2 Answers

+22 votes
Best answer
$2(n-1)$ the spanning tree will traverse adjacent edges since they contain the least weight.
answered by Loyal (3.3k points)
edited by
MST will be line graph.

MST will be line graph.

Chhotu  pls explain how?


MST will add the edges with minimum weight, Weight of edges = 2|i−j|.

All successive number will have weights of 2. (like 1-2 weight is 2 , 2-3 weight is 2 so on) Hence it will be a line graph of weight 2 (n-1). i.e n-1 edges each of weight 2.

Take for example K4 an try.
+13 votes
None of the options match the Actual answer.

 For connecting every i & i+1 node we have edge of weight 2 ,therefore We get 2*(n-1).
answered by Veteran (49.5k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,705 questions
40,253 answers
38,861 users