retagged by
648 views

1 Answer

Best answer
7 votes
7 votes

Answer: 45

AF, EG, DH these three edges will always be part of MST. Now among AE and FG, you can take anyone but not both because then it will create a cycle. Similarly, between ED and GH you can take anyone but not both because then it will create a cycle. In the left-most cycle which is ABCDEA , there are 5 edges you can take any 2 out of them that are not already taken, similarly, for the rightmost cycle, FGHJIF, take any 2 out of them that are not already taken, so till now a total of 3+3=6 edges each edge weight is 7 and 3 edges of weight 1,  So total edge weight = 6*7+3*1=45.one of the possible minimum spanning trees will be spanning tree containing edges AF, EG, DH, AE, GH, FI, IJ, AB, BC.

Minimum spanning tree - Wikipedia

The number of possible MST: Between AE and FG you can take anyone so 2 choices, similarly ED and GF have 2 choices. So till now 2*2= 4 choices (AE and ED or AE and GF or FG and ED or FG and GF) between AB, BC, CD you can take any two so 3 choices, similarly between FI, IJ, GH you can take any two, so total 2*2*3*3=36 choices.

selected by
Answer:

Related questions

1 votes
1 votes
1 answer
1
Sagar475 asked Jan 21, 2022
662 views
A min heap of size 2048 is stored on an array with array indices [1..2048] is stored and the minimum number of comparisons required to determine the maximum of element i...
2 votes
2 votes
1 answer
2
LRU asked Nov 22, 2021
832 views
Number different of binary search trees which can be created with the elements {12, 34, 22, 43, 13, 45, 55, 94, 99, 23} with 45 as the root is___.
1 votes
1 votes
1 answer
3
LRU asked Nov 2, 2021
366 views
What is the correct order ?
1 votes
1 votes
1 answer
4
devilstephen7 asked Sep 20, 2021
492 views
Consider the following function int foo(int n){int p = 1 ;if (n && !(n&(n-1))) return n; while (p<n){p <<= 1;}return p;}What is the worst case time complexity of function...