668 views

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

1. 11
2. 25
3. 31
4. 41
Its a linked question. Previous question is- http://gateoverflow.in/2162/gate2011-54

Above is the graph....
Below is the MST.

Length of the path from v5 to v6= 8+4+3+6+10= 31 (Ans)

selected ago by

There is no direct edge between Vi and Vi+1 vertex in mst except V1 to V2 so path from Vi and Vi+1 includes all edges from v1 to Vi+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=n2-n+1

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

edited by
@Gabbar how u write equation??
kk i got it thks
@Gabbar , if we draw MST and find the value it will give 31 as answer

the weights are 4+3+6+8+10=31
@srestha there is 8 not 9 in MST...plz check it...

and 11 is not possible since it generates cycle...
yes.

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

Answer is 31 but we have to draw 10 vertices to get it
Why isn't ans $11$ as there is a edge between vertex(5) and vertex(6) ?
because it create cycle by create minimum spaning tree.
No, 7 vertices are sufficient to calculate cost of 5-6.
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 Vi and Vi+1 vertex so path from Vi and Vi+1 includes all edges from v1 to Vi+1 which are in mst:

equation: n2-n + 1 from previous question

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