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

2 Answers

+4 votes
Best answer

 

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 (22.1k 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 (3.9k 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 Mar 2017
  1. rude

    4018 Points

  2. sh!va

    2994 Points

  3. Rahul Jain25

    2804 Points

  4. Kapil

    2608 Points

  5. Debashish Deka

    2104 Points

  6. 2018

    1414 Points

  7. Vignesh Sekar

    1336 Points

  8. Bikram

    1218 Points

  9. Akriti sood

    1186 Points

  10. Sanjay Sharma

    1016 Points

Monthly Topper: Rs. 500 gift card

21,446 questions
26,759 answers
60,943 comments
22,955 users