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.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+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:

- $n-1$
- $2n-2$
- $\begin{pmatrix} n \\ 2 \end{pmatrix}$
- $n^2$

+24 votes

Best answer

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,000 questions

45,496 answers

131,569 comments

48,633 users