The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+18 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 Active (3.3k points)
edited by | 2.9k 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.
what will be the case if weight of the edge v(i, j) is | i+j | ?
I think it would be [(n+1)(n+2)/2] - 3.

3 Answers

+24 votes
Best answer
$2(n-1)$ the spanning tree will traverse adjacent edges since they contain the least weight.
answered by Active (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.
Suppose I take 4 vertices as an example. Then the minimum spanning tree is a line graph with 3 edges of weight 2 each.

now both options B and C gives me the correct minimum weight as 6.
+14 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).

Correct Answer: $B$
answered by Boss (41k points)
edited by
which is equal to 2n-2
+1 vote

Ans is 2n-2

answered by Junior (627 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
49,535 questions
54,122 answers
71,039 users