GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
503 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 (76.2k points)   | 503 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.4k 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 Apr 2017
  1. akash.dinkar12

    3514 Points

  2. Divya Bharti

    2546 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Shubham Sharma 2

    1610 Points

  7. Debashish Deka

    1588 Points

  8. Arunav Khare

    1454 Points

  9. Kapil

    1424 Points

  10. Arjun

    1420 Points

Monthly Topper: Rs. 500 gift card

22,076 questions
28,042 answers
63,233 comments
24,135 users