edited by
11,567 views
40 votes
40 votes

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$
edited by

6 Answers

Best answer
78 votes
78 votes

 

Above is the graph.
Below is the MST.

Length of the path from $v_5$ to $v_6= 8+4+3+6+10= 31$ (Answer)

Correct Answer: $C$

edited by
28 votes
28 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

edited by
5 votes
5 votes

Answer is C.

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

1 votes
1 votes

From the previous question, we know $n^2-n+1$ will be the weight of the MST with $n>2$

Evidently, only $V_1$ and $V_2$ are connected, and no other vertex $V_i$ is connected to $V_{i+1}$

 

We can wisely use the above equation. For a path between $V_5$ and $V_6$, vertices more than 6 are redundant, since weight only increases for a larger $i$ of any vertex $V_i$ here.

We only need an MST upto 6 vertices. Path from $V_5$ to $V_6$ ill be included in it. It's weight will be $n^2-n+1$

=> $36-6+1$

=> $31$

 

Answer:

Related questions

26 votes
26 votes
1 answer
2
Kathleen asked Oct 9, 2014
5,105 views
A complete, undirected, weighted graph $G$ is given on the vertex $\{0, 1,\dots, n -1\}$ for any fixed ‘n’. Draw the minimum spanning tree of $G$ ifthe weight of the ...
12 votes
12 votes
4 answers
4
makhdoom ghaya asked Nov 30, 2016
2,655 views
In the graph shown above, the depth-first spanning tree edges are marked with a $’ T’$. Identify the forward, backward, and cross edges.