GATE CSE
First time here? Checkout the FAQ!
x
+9 votes
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
asked in Algorithms by Veteran (79k points)   | 668 views
Its a linked question. Previous question is- http://gateoverflow.in/2162/gate2011-54

3 Answers

+4 votes
Best answer

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

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

 

answered by Loyal (4.4k points)  
selected ago by
+6 votes

 

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

 

answered by Veteran (23.2k points)  
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.
+4 votes

Answer is C.

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

answered by Loyal (4k points)  
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

Answer:

Related questions



Top Users Aug 2017
  1. ABKUNDAN

    4658 Points

  2. Bikram

    4134 Points

  3. akash.dinkar12

    3144 Points

  4. rahul sharma 5

    2928 Points

  5. manu00x

    2682 Points

  6. makhdoom ghaya

    2390 Points

  7. just_bhavana

    2058 Points

  8. Tesla!

    1782 Points

  9. pawan kumarln

    1574 Points

  10. learner_geek

    1558 Points


24,892 questions
31,967 answers
74,213 comments
30,083 users