GATE CSE 2011 | Question: 55

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.

The length of the path from $v_5$ to $v_6$ in the MST of previous question with $n=10$ is

• A. $11$
• B. $25$
• C. $31$
• D. $41$

Comments

Its a linked question. Previous question is- https://gateoverflow.in/2162/gate2011-54

---

Except $V1\ and\ V2$ no other vertices of the form $V_{i}$ and $V_{i+1}$ will be adjacent in the $MST$ and if we observe by taking few examples that $V1\ is\ connected\ to\ odd\ vertices$ and $V2\ is\ connected\ to\ even\ vertices$ in the $MST$

---

$V5\ to\ V6=8+4+3+6+10=31$

---

@Sachin Mittal 1 sir how there is no edge between v5 and v6. 0<|5-6|<2. 

Answer 1

For easy visualisation, try to imagine all the vertices in horizontal line

The value 5+6=11 seems legit, however it will not give MST as,

it would be much better to connect 6 with 4 as we can get 6+4 = 10.

Basically MST can be obtained if we connect alternate edges,

with only exception of vertices 1 and 2.

 

3 + 4 + 6 + 8 + 10 = 31

 

Q1. Why this technique will give MST ?

Q2. Why only 1 and 2 should be joined horizontally ?

 

A1. we only have two ways to join two vertices either consecutively or alternate.

we just saw how continous joining was inefficient as compared to alternate.

 

A2. When we make these types of alternate pairing we will be left with two sets of even and odd numbers

in order to join these two sets we select the minimum from both of them

here,  1 is from the odd set

   and 2 is from even set.

 

 

Answer 2

In this question, sum of weights of mst for distinct values of n is following a pattern.

Ex. For n= 4, we have,

Sum of weight of mst = 3(v1->V2) + 4(v1->v3)+ 6 (v2->v4) 

For n =5 , we have,

Sum of weights of mst = same as weight of mst for n=4 + 8(v3->v5)

We are observing two patterns here: 

1) first is the weight of mst for n nodes is given by ----- weight of mst with n-1 nodes + (maximum weight of edge in mst having n-1 nodes + 2).

2) and the second pattern is in the edges we are taking.  Like in n=4, the last edge we have taken is (v2->v4) , then in n=5, the last edge taken is from (v3->v5) and the rest edges are same as that of n=4, similarly for n=6, the edge taken would be from v4->V6, for n=7 , it would be from v5-> v7...and so on.

Now for n=10, we have to find weight of path form v5to V6.

The pattern for the mst would be :- 

3(v1->V2) + 4(v1->v3) + 6(v2->v4) + 8(v3->v5) + 10(v4->V6) +12(v5->v7).......so on.

Sum of path from v5- to V6 in mst = 8(v5->v3) +4(v3->v1) + 3(v1->V2) + 6(v2->v4) + 10(v4->V6) = 31 .

so, 31 is the answer.