edited by
17,008 views
52 votes
52 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.

What will be the cost of the minimum spanning tree (MST) of such a graph with $n$ nodes?

  1. $\frac{1}{12} (11n^2 - 5 n)$
  2. $n^2-n+1$
  3. $6n-11$
  4. $2n+1$
edited by

10 Answers

Best answer
45 votes
45 votes

Q 54. Answer is B.

$\text{ We observe a pattern in the weight of MST being formed }$

$\text{ For n=3 } (1+2+3)+(1)$
$\text{ For n=4 } (1+2+3+4)+(1+2)$
$\text{ For n=5 } (1+2+3+4+5)+(1+2+3)$
$\text{ These can be obtained by drawing graphs for these graphs. }$
$\therefore \text{ Total weight of MST is } \sum_{i=1}^{n}i+\sum_{i=1}^{n-2}i=n^2-n+1\\$

edited by
9 votes
9 votes

Start from initial vertex and add each vertex at a time with its minimum weight edge.

4 votes
4 votes

One more way to prove the same thing is as follow --> 

Answer:

Related questions

26 votes
26 votes
1 answer
2
Kathleen asked Oct 9, 2014
5,107 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.