edited by
14,641 views
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:

  1. $n-1$
  2. $2n-2$
  3. $\begin{pmatrix} n \\ 2 \end{pmatrix}$
  4. $n^2$
edited by

7 Answers

Best answer
40 votes
40 votes
$2(n-1)$ the spanning tree will traverse adjacent edges since they contain the least weight.
edited by
17 votes
17 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$
edited by
4 votes
4 votes
$\underline{\mathbf{Answer:B}}\Rightarrow$

$\underline{\mathbf{Explanation:}}\Rightarrow$

Make a square of $4$ vertices and make it as a complete graph, that is, having $6$ edges.

Now, make the spanning tree. It will be the $3$ adjacent edges and the weight will be $2+2+2=6$.

Now, check the options and substitute $\mathbf {n = 4}$, then only option $\mathbf B$ is satisfied.

$\therefore \mathbf B$ will be the answer.
edited by
Answer:

Related questions