The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

- $\frac{1}{12} (11n^2 - 5 n)$
- $n^2-n+1$
- $6n-11$
- $2n+1$

0

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.

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

+27

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)

=1+(n-1)*n=n^{2}-n+1

0

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

0

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

+2 votes

+2 votes

**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^{2}+n)/2} + {(n^{2}-3n+2)/2}

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

=n^{2}-n+1

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 ?

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

+3

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.

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*

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

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 556
- Exam Queries 551
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,894 questions

52,261 answers

182,169 comments

67,679 users