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

@nikhilsaxena835 because it is a minimum spanning tree and if we take the edges the weight will become more so that's why we excluded that edges

---

 

understand the whole thing with simple graph(Both Questions)

---

nice one Master OogWay

Answer 1

 

Above is the graph.
Below is the MST.

Length of the path from $v_5$ to $v_6= 8+4+3+6+10= 31$ (Answer)

Correct Answer: $C$

Answer 2

There is no direct edge between V_i and V_i+1 vertex in mst except V1 to V2 so path from V_i and V_i+1 includes all edges from v1 to V_i+1 which are in mst:

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²-n+1

In this case v6 = 6²-6+1 =31

Comments

nice approach

---

will this work for v7 to v8 also???

---

Nice one @papesh

Answer 3

Answer is C.

It can be easily obtained by drawing graph for up to 7 vertices.

Comments

Draw spanning tree upto 7 vertices, then you will see if v5 to v6 length is 11 and we add that then that will create a cycle.

---

NO need to draw full spanning tree..

there is no direct edge between V_i and V_i+1 vertex so path from V_i and V_i+1 includes all edges from v1 to V_i+1 which are in mst:

equation: n²-n + 1 from previous question

in our case v6 = 6²-6+1 =31

---

Nice catch drawing MST till 6 vertices will do! :)

Answer 4

From the previous question, we know $n^2-n+1$ will be the weight of the MST with $n>2$

Evidently, only $V_1$ and $V_2$ are connected, and no other vertex $V_i$ is connected to $V_{i+1}$

 

We can wisely use the above equation. For a path between $V_5$ and $V_6$, vertices more than 6 are redundant, since weight only increases for a larger $i$ of any vertex $V_i$ here.

We only need an MST upto 6 vertices. Path from $V_5$ to $V_6$ ill be included in it. It's weight will be $n^2-n+1$

=> $36-6+1$

=> $31$

 

Answer 5

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.

Answer 6

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.