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

 

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

yes.

---

nice approach

---

will this work for v7 to v8 also???

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$