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

6n-11 option was given here just because of slight error will deduct your marks.

make connecting nodes condition wrong you will get this answer as option.condition highlighted below. 

two nodes Vi and Vj are connected if and only if 0< ∣i−j∣ ≤2

Like if you try for 5 vertices by doing this mistake you get 19 as answer and by making sure that this condition is not wrong you will get 21 as answer.

---

For $n=3$,      $A,B,C,D$ will give same value as cost.
For $n=4$,      $A,B,C$ will give same value as cost.
For $n=5$,      $Only\;B\;will\;give\;same\;value\;as\;cost.$

---

Here option B is giving near value of min cost spanning tree not exact min . But here we can use substitution method to save time in exam 

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.

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 ?