GATE CSE 2011 | Question: 54

Question

An undirected graph $G(V,E)$ contains $n \: (n>2)$ nodes named $v_1,v_2, \dots, v_n$. Two nodes $v_i, v_j$  are connected if and only if $ 0 < \mid i-j\mid \leq 2$. Each edge $(v_i,v_j)$ is assigned a weight $i+j$. A sample graph with $n=4$ is shown below.

What will be the cost of the minimum spanning tree (MST) of such a graph with $n$ nodes?

• A. $\frac{1}{12} (11n^2 - 5 n)$
• B. $n^2-n+1$
• C. $6n-11$
• D. $2n+1$

Comments

Thank you for giving this beautiful solution!

---

Done ✅

---

i agree @Anurag_Patwa 😎

Answer 1

Q 54. Answer is B.

$\text{ We observe a pattern in the weight of MST being formed }$

$\text{ For n=3 } (1+2+3)+(1)$
$\text{ For n=4 } (1+2+3+4)+(1+2)$
$\text{ For n=5 } (1+2+3+4+5)+(1+2+3)$
$\text{ These can be obtained by drawing graphs for these graphs. }$
$\therefore \text{ Total weight of MST is } \sum_{i=1}^{n}i+\sum_{i=1}^{n-2}i=n^2-n+1\\$

Comments

@papesh @abhishekmehta4u why in the end we have 2(n-1). I know, for n vertices in G we get (n-1) edges in MST, but where's the 2 coming from?

@Chhotu

Is it because every term is increasing by 2?

@jatin saini @srestha

---

@iarnav , papesh   splitted  the term 3 as 1+2 to make the sum simple..since series $3,4,6,8,10,....$ contains $(n-1)$ terms due to no. of edges in the minimum weight spanning tree. Now after splitting,  series $1,2,4,6,8,10,....$  contains $n$ terms . So, it means series $2,4,6,8,10,....$ contains $(n-1)$ terms and its $N^{th}$ term will be $2+(N-1)*2$ = $2+(n-1-1)*2$ = $2n-2$ = $2(n-1)$.

---

@ ankitgupta.1729  Thanks bhai, as always! :)

Answer 2

Caption

Q 54. Answer is B

Answer 3

Start from initial vertex and add each vertex at a time with its minimum weight edge.

Comments

So the main idea was to satisfy the condition of 0<|i-j|<=2 and simultaneouly keeping the sum i+j lesser.

 

example: we did V4-V2 instead of V4-V3 cuz no doubt the both of them satisfies the |i-j| condition but the sum is 6 and 7 respectively and we want least so V4-V2 it is.

Answer 4

One more way to prove the same thing is as follow --> 

Comments

Your answer is same as the one in the comments below the best answer. What's the point in adding the same thing ?

Answer 5

ANSWER is B:

The pattern that goes with the solution:.

 For n=3 (1+2+3)+(1) 
 For n=4 (1+2+3+4)+(1+2)
 For n=5 (1+2+3+4+5)+(1+2+3) 

For n=  {n(n+1)/2 } + {(n-2)(n-2+1)/2}

         ={(n²+n)/2} + {(n²-3n+2)/2}

         =(n²-3n+2+n2+n)/2

         =n²-n+1

Answer 6

Try putting n=4, MST 13, every option satisfies except D.

Try n=3. MST 7, the subgraph {v1 v2 v3} will tell you the MST in the given graph. It satisfies all the options.

So seeing no other way, add v5, connect it to v4, v3, We connect only v3 and v4 with v5 bcs of the condition given 0< ∣i−j∣ ≤2. 

The v4-v5 edge weight is 5+4 = 9 and v3-v5 edge wight is 8.

The MST cost of the graph = 21.

now only option B satisfies.

Ans (B).