Minimum spanning tree

Question

What would be the maximum weight of minimum spanning tree of a complete connected graph with 6 vertex where each edge  is of distinct +ve weights and max weight of edge is 15

1) 25

2) 26

3)27

4) none of these

Comments

Answer given is 25

Option 1

---

"where each vertex is of distinct edges " -> what does this mean? or did you mean "Each edge is of distinct weight?"

---

Yeah

I hve made the correction in the question.

Answer 1

given that each edge is distinct and weights starts from 1, For answering this question,come from very basic

with n=3 ===> Minimum spanning tree = 1+2 = 3

 

with n=4 ===> Minimum Spanning tree = 1+2+4 = 7 ( for getting maximum value of MST, assume edge with weight 3 getting into loop )

 

with n=5 ===> Minimum Spanning tree = 1+2+4+7 ( for getting maximum value of MST, assume edge with weight 3,5,6 getting into loop )

 

with n=6 ===> Minimum Spanning tree = 1+2+4+7+11  ( for getting maximum value of MST, assume edge with weight 3,5,6,8,9,10 getting into loop )

 

with n=7 ===> Minimum Spanning tree = 1+2+4+7+11+16  ( for getting maximum value of MST, assume edge with weight 3,5,6,8,9,10,12,13,14,15 getting into loop )

 

---

---

I am forming a recurrence relation for n nodes

 T ( n ) = T ( n-1 ) + { $ \binom{n-1}{2} $ + 1 }

          = T ( n-2 ) + { $ \binom{n-2}{2} $ + 1 }  + { $ \binom{n-1}{2} $ + 1 } =  T ( n-2 ) +  $ \binom{n-2}{2} $  +  $ \binom{n-1}{2} $ + 2

        = T ( n-3 ) + { $ \binom{n-3}{2} $ + 1 }  + { $ \binom{n-2}{2} $ + 1 }  + { $ \binom{n-1}{2} $ + 1 } = T ( n-3 ) +  $ \binom{n-3}{2} $  + $ \binom{n-2}{2} $  +  $ \binom{n-1}{2} $ + 3  

          .

          .

          .

          .

          .

= T ( n-k ) + { $ \binom{n-k}{2} $ + 1 }  + ...... + { $ \binom{n-1}{2} $ + 1 } = T ( n-k ) +  $ \binom{n-k}{2} $  + ....... +  $ \binom{n-1}{2} $ + k

 

we know that T(3) = 3 ===> n-k=3 ==> k=n-3

 

T ( n-k ) +  $ \binom{n-k}{2} $  + ....... +  $ \binom{n-1}{2} $ + k

= T(3) + $ \binom{3}{2} $  + ....... +  $ \binom{n-1}{2} $ + n-3

=  $ \binom{3}{2} $  + ....... +  $ \binom{n-1}{2} $ + n

= $\frac{2*3}{2} + \frac{3*4}{2} +\frac{4*5}{2}+....+\frac{(n-2)*(n-1)}{2} $+ n

=  $\frac{2*3}{2} + \frac{3*4}{2} +\frac{4*5}{2}+....+\frac{(n-2)*(n-1)}{2} $+ n + $\frac{2}{2} - \frac{2}{2} $

=  $  \frac{1*2}{2} + \frac{2*3}{2} + \frac{3*4}{2} +\frac{4*5}{2}+....+\frac{(n-2)*(n-1)}{2} $+ n + - $ \frac{2}{2} $

=  $  \frac{1}{2} $ ( 1*2 + 2*3 + 3*4 +4*5 +....+(n-2)*(n-1) ) + n  - 1

=  $  \frac{1}{2} $ ( $  \frac{(n-2)*(n-1) (n) }{3} $ )+ n - 1 

=  ( $  \frac{(n-2)*(n-1) (n) }{6} $ )+ n - 1 

 

ex:-

T(6) = ( $  \frac{(4)*(5) (6) }{6} $ )+ 6 - 1  = 20+5 =25

T(7) = ( $  \frac{(5) (6) (7) }{6} $ )+ 7 - 1  = 35+6 =41

Answer 2

Answer will be $25$

---

Concept-:For maximum weight of MST,try to involve minimum weight edge in cycle as possible.

we have $\binom{6}{2}=15$ edges having respective weights as $\left \{ 1,2,3,....15 \right \}$.We need only $6-1=5$ edges

Now start with weight edge (WE) $1$,$2$ and then put $3$ in cycle.

now we have $2$ edges with WE as $1$ and $2$ .Now Add WE $3$ in the cycle 

Now we have WE $4$ which do not have any option, we will take it .for WE $5$ we will try to add it in cycle

Try to add $6$  also in the cycle.

Now we have WE $7$ , we do not have any choice for $7$,so take it

Upto now ,we have edges as weight edge $1,2,4,7$ for MST.

We need 1 more.

If you repeat above steps,you will find that you will get WE as $11$.

Hence answer=$1+2+4+7+11=25$

Comments

Assuming ABCDEF as MST, if we use Prim's algorithm, edges are added to MST like this. Substituting loop edges with the minimum possible weight.

So total 1 + 2 + 4 + 7 + 11 = 25.