The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
2.1k views

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.7k points)
edited by | 2.1k views
+9

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.

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

2 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
0
MST will be line graph.
0

MST will be line graph.

Chhotu  pls explain how?

0
@set2018

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.
+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).
answered by Boss (42.6k points)
Answer:

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

38,000 questions
45,496 answers
131,569 comments
48,633 users