Redirected
recategorized
1,746 views
1 votes
1 votes

Consider a weighted complete graph $G$ on the vertex set $\left\{ν_{1} , ν_{2},.... ν_{n} \right\}$ such that the weight of the edge $(ν_{i} , ν_{j})$ is $4 | i – j|$. The weight of minimum cost spanning tree of $G$ is :

  1. $4n^{2}$
  2. $n$
  3. $4n – 4$ 
  4. $2n – 2$
recategorized

4 Answers

1 votes
1 votes
Clearly it's 4(n-1).

I'm answering it by procedure although we can answer such question by hit and trial method also.

as the graph is connected and it has n vertices.

for spanning tree we need those n-1 edges that corresponds to total minimum weight (no cycle of course)

Now one time focus 4|i-j| , think for second how can this be minimum , yes it would be minimum for adjacent edges as for adjacent edges |i-j|=1 and simply there would be n-1 such adjacent edges (in that way MST property is saved)

so ultimately n-1 edges each having 4 weight   => 4(n-1)

 

in hit and trial take any connected graph (for easiness take triangle) and apply some MST algo and put the values and cross check answer.
0 votes
0 votes
For minimum spanning tree n-1 edges are enough . and graph is complete graph . so each adjacent vertex is connected by a edge of weight 4 .
so cost of minimum spanning tree using prims algo = (n-1)*4=4n-4

Related questions

1 votes
1 votes
1 answer
1
1 votes
1 votes
1 answer
3
makhdoom ghaya asked Oct 1, 2016
844 views
Consider a hash table of size $m = 10000$, and the hash function $h(K) = floor (m(KA \bmod 1))$ for $A = ( \sqrt{5} – 1)/2$. The key $123456$ is mapped to location ____...
1 votes
1 votes
3 answers
4
makhdoom ghaya asked Oct 4, 2016
4,057 views
Which formal system provides the semantic foundation for Prolog ?Predicate calculusLambda calculusHoare logicPropositional logic