Redirected
edited by
4,427 views
11 votes
11 votes

How many distinct minimum weight spanning trees does the following undirected, weighted graph have ?

  1. $8$
  2. $16$
  3. $32$
  4. $64$
  5. None of the above
edited by

5 Answers

Best answer
11 votes
11 votes
There are $64$ minimum spanning trees possible.

Two choices for edge of weight $4$ for each of the outer triangle, i.e., $ \binom{2}{1}*\binom{2}{1}*\binom{2}{1}*\binom{2}{1}=2^4$ and two choices for edge of weight $2$ for each of the inner triangle i.e., $\binom{2}{1}*\binom{2}{1}=2^2$.

$2^4*2^2=64$
3 votes
3 votes

First we can write the edges in increasing order:

AD-1, AC-2, CD-2, AE-2, ED-2, AB-4, BC-4, CF-4, DF-4, DG-4, EG-4, HE-4, AH-4

 

 

Now we have Vertices {A,B,C,D,E,F,G,H}

make sets by taking edges with min. weight:

 

1 weight- AD  Vertex cover: {A,D}

2 weight- Here we have 2 choice either AC or CD:   Vertex Cover {A,D,C} 

2 weight- Here we have 2 choice either AE or ED:   Vertex Cover {A,D,C,E} 

4 weight- Here we have 2 choice either AB or BC:   Vertex Cover {A,D,C,E,B} 

4 weight- Here we have 2 choice either CF or DF:   Vertex Cover {A,D,C,E,B,F}

4 weight- Here we have 2 choice either DG or EG:  Vertex Cover {A,D,C,E,B,F,G}

4 weight- Here we have 2 choice either HE or AH:   Vertex Cover {A,D,C,E,B,F,G,H}

 

Total distinct MST= $\binom{1}{1}*\binom{2}{1}*\binom{2}{1}*\binom{2}{1}*\binom{2}{1}*\binom{2}{1}*\binom{2}{1}$

Hence option (D).

 

 

1 votes
1 votes

 

 

any one please check whether it is a correct way or not?? 

i am also getting 64 

Answer:

Related questions

10 votes
10 votes
2 answers
1
4 votes
4 votes
2 answers
2
Arjun asked Dec 18, 2018
4,147 views
Which of the following decimal numbers can be exactly represented in binary notation with a finite number of bits ?$0.1$$0.2$$0.4$$0.5$All the above
5 votes
5 votes
1 answer
3