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

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 2

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

Answer 3

I drew a graph for n=10 and found answer for Q54) as B and answer for Q55) as C

BUT that is a messy and time consuming procedure ... does anyone have a better approach to the given problem ?

Comments

Put the values 3,4,5,6...to check using which value the options are giving different anwers, then using the least such value, draw the required graph. In this case n=5 will suffice. You will see that the cost of MST is 21 which is satisfied only by option B. Having found the method you will know where to attach the new node, V6. Then from the new MST find the value of v5 to v6 which will be nothing but 21 + the minimum value to reach to v6 which will be (v4 to v6)=10, thus the answer will be 21+10=31.

---

that is indeed the best way to solve these problems

Answer 4

$Cost = (v_1 +(v_1+ vertex_d=1))+[\{v_1+(v_1+vertex_d=\color{Red}2)\}+\{v_2+(v_2+vertex_d=\color{Red}2)\}+\{v_3+(v_3+vertex_d=\color{Red}2)\}+\{v_4+(v_4+vertex_d=\color{Red}2)\}+......+\{v_{n-2}+(v_{n-2}+vertex_d=\color{Red}2)\}]$

$= (1 +(1+1))+[\{1+(1+\color{Red}2)\}+\{2+(2+\color{Red}2)\}+\{3+(3+\color{Red}2)\}+\{4+(4+\color{Red}2)\}+......+\{(n-2)+((n-2)+\color{Red}2)\}]$

$= 3+ [2*\{1+2+3+4+....+(n-2)\} + \color{Red}2*(n-2)] $

$= 3 + 2*[(n-2)(n-1)/2] + \color{Red}2*(n-2)$

$= 3 + (n-2)[n-1+2]$

$= n^2 -n +1$

where, $vertex_d$ = distance from current vertex

$Explanation:$

Here with the given conditions, you have to pick "ALL THE EDGES" from least labelled vertex (as they will be the one with least weights) such that you don't end up in a cycle.

Hence, from vertex $v_1$ possible edges are $v_1$$v_{2(1+1)}$ and $v_1$$v_{3(1+2)}$, from vertex $v_2$ edges are $v_2$$v_3$ and $v_2$$v_4$ but since vertex $v_3$ is already covered by edge $v_1$$v_3$ you need not pick $v_2$$v_3$. You will soon realize that vertex only with distance 2 from current vertex are taken (except for vertex $v_1$ which has the base case edge $v_1v_2$).The last term in the series will be for $v_{n-2}$ as it will cover the last vertex $v_n$.