in Algorithms edited by
7,581 views
25 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$
in Algorithms edited by
7.6k views

6 Comments

edited by

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.

11
Option B should be 2n-2...
5
It seems this question needs small correction.
3
what will be the case if weight of the edge v(i, j) is | i+j | ?
0
I think it would be [(n+1)(n+2)/2] - 3.
0

Subscribe to GO Classes for GATE CSE 2022

7 Answers

33 votes
 
Best answer
$2(n-1)$ the spanning tree will traverse adjacent edges since they contain the least weight.
edited by
by

8 Comments

MST will be line graph.
4

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.
1
edited by
Suppose I take a complete graph with 4 vertices. Then the minimum spanning tree contains 3 edges of weight 2 each.

Now both options B and C gives me the correct minimum weight as 6.
0

@Gupta731

To avoid that take a complete graph of $4$ vertices and then you will only get $\mathbf {B}$ as the answer.

0
not 4 take 3 vertices then solve because for 4 vertices there will be confusion between option B and C
0
Here, direct solution is given without any explanation

Further, the solution doesn't explain the underlying concept(s) properly. Therefore, It is not suitable for novice users.
0
edited by

@set2018

Refer the solution given by me(@vermavijay1986) for better understanding

of the sentence:  “MST will be a line graph” 

OR we can say that:  “MST will be a line tree” 

0
16 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

1 comment

which is equal to 2n-2
3
3 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
by

2 Comments

For $n = 4,$ option $B;C$ are satisfied. But for $n = 3,$ only option $B$ is satisfied.
0

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
2 votes

Ans is 2n-2

by
1 vote

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). 

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

1 comment

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
0 votes

Recall the definition of Complete Graph , then the solution is straightforward:

Refer the attached file below:

Answer:

Related questions