The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+32 votes

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?

  1. $\frac{1}{12} (11n^2 - 5 n)$
  2. $n^2-n+1$
  3. $6n-11$
  4. $2n+1$
asked in Algorithms by Veteran (97.1k points)
edited by | 4.7k views
Simple substitution .... For n=5 ... Option A will fail ... So option B ...
For those interested in recurrence relations, this would look like: $\color{red}{T(n) = T(n-1) + 2n-2}$  with  $\color{blue}{T(2) = 3}$ for base case.
@Krish... how did you form the recurrence relation by seeing this question AND how did the idea hit your brain that you can form a recurrence relation and can solve the question like this? help me to learn also please :-)
For n=5, Along with option A, option C and option D also fails

8 Answers

+29 votes
Best answer

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\\$

answered by Active (4.2k points)
edited by

But 55 is asking about V5 to V6 . right? and not Vto V6


edge weights in mst:

=3 + 4 + 6 + 8 + 10 + 12 +...+*(2(n-1))

=1+(2+ 4+6+....till n-1 terms)

=1+ 2(1+2+3+4+...n-1) 


@papesh veteran, amazing approach

@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?


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)$.
+17 votes


Q 54. Answer is B

answered by (101 points)
edited by
+8 votes

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

answered by Active (4.6k points)
+3 votes


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}

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



answered by (41 points)
+2 votes

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

answered by Boss (12.3k points)
Your answer is same as the one in the comments below the best answer. What's the point in adding the same thing ?
0 votes
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 ?
answered by Active (4k points)
Put the values 3,4,5, 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.
0 votes

$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


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

answered by Active (2.1k points)
0 votes

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

answered by Junior (855 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,808 questions
54,489 answers
74,660 users