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

    3154 Points

  2. pawan kumarln

    1636 Points

  3. sh!va

    1590 Points

  4. Arjun

    1350 Points

  5. Bikram

    1298 Points

  6. Devshree Dubey

    1246 Points

  7. Angkit

    1044 Points

  8. Debashish Deka

    1042 Points

  9. LeenSharma

    880 Points

  10. srestha

    706 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    384 Points

  2. pawan kumarln

    262 Points

  3. Ahwan

    236 Points

  4. Arnab Bhadra

    136 Points

  5. LeenSharma

    118 Points


22,770 questions
29,090 answers
65,119 comments
27,635 users