Redirected
edited by
1,012 views
1 votes
1 votes

An undirected graph $G(V,E)$ contains $n(n>2)$ nodes named $v_1, v_2, \dots , v_n$. Two nodes $v_i$ and $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$. The cost of the minimum spanning tree of such a graph with $10$ nodes is

  1. $88$
  2. $91$
  3. $49$
  4. $21$
edited by

1 Answer

0 votes
0 votes
10 nodes v1,v2,...,v10

Edges 0 less than |i-j| less than or equal to 2

|1-2|=|2-3|=|3-4|=........=|9-10|=1

Weights

1+2,2+3,.....,9+10

i.e., 3,5,7,9,11,13,15,17,19

|1-3|=|2-4|=|3-5|=|4-6|=.... =|8-10|=2

Weights

1+3,2+4,3+5,......8+10

i.e., 4,6,8,.....18

No other edges can be added to this graph

 Now, using Kruskal's algorithm, taking the node with the minimum weight for constructing the minimum cost spanning tree.

i.e., v1-v2(weight-3)

Then v1-v3(4),

Can't take v2-v3 since it makes a circuit...

Adding all the weights..

3+4+6+8+10+12+14+16+18=91

Ans:(B) 91
Answer:

Related questions

1 votes
1 votes
3 answers
1
Arjun asked Nov 5, 2017
839 views
Which of the following routing technique / techniques is/are used in distributed systems?Fixed RoutingVirtual RoutingDynamic Routing(a) only(a) and (b) only(c) onlyAll (a...
1 votes
1 votes
2 answers
3
Arjun asked Nov 5, 2017
911 views
The Sigmoid activation function $f(t)$ is defined as$\dfrac{1}{\text{exp} (t) + \text{exp} (-t)}$$t \text{ exp}(-t)$$\dfrac{1}{1+ \text{exp} (t)}$$\dfrac{1}{1+ \text{exp...