1 votes 1 votes Find the no. of minimum cost spanning tree using Kruskal’s or Primus algorithm i am getting "4" but the answer is given "5" ...verify please Algorithms minimum-spanning-tree numerical-answers + – Prateek kumar asked Jan 19, 2017 • retagged Jul 8, 2022 by Lakshman Bhaiya Prateek kumar 2.0k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply Prateek Yadav 2 commented Jan 19, 2017 reply Follow Share Yes it is 4 coming 1 votes 1 votes Tejasvi96 commented Jun 16, 2018 reply Follow Share It should be 5. The first three edges that would be selected are of costs 11,12,12 ie. AD, AB, BE. Now remaining 5 edges are of same cost 13 and one edge is of cost 15(this should not be considered ). From these edges we have to select 2 for a Minimum spanning tree. Clearly DE would produce a cycle here. So out of remaining 4 we have to select two.It can be done in 4c2 ways which is 6. But if we add BC and EC together it would produce a cycle. So it should be ignored and leaves us with 5 choices. So the answer is 5. 1 votes 1 votes eyeamgj commented Jun 16, 2018 reply Follow Share see i have drawn 6 spanning trees so may be 6 or >6 0 votes 0 votes Tejasvi96 commented Jun 16, 2018 reply Follow Share How can you have 3 and 4 one. The edge is in one diagonal only. 0 votes 0 votes eyeamgj commented Jun 16, 2018 reply Follow Share oh yes thank u so much ,my mistake ...nd thank god i didnt tried further may be i could got 7or 8 or 9........spanning tries 0 votes 0 votes shivanisrivarshini commented Jun 16, 2018 reply Follow Share its just 5 spanning trees 0 votes 0 votes vupadhayayx86 commented Jun 6, 2019 reply Follow Share Answer is 5 you need to check wisely!! 0 votes 0 votes Please log in or register to add a comment.
Best answer 3 votes 3 votes Caption Rameez Raza answered Mar 17, 2017 • selected Mar 21, 2017 by shivanisrivarshini Rameez Raza comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes prims algo starting from the A minimum weight is given by :11+12+12+13+13=61 kruskals algo: sorting the weight of the graphs i.e. 11 12 12 13 13 13 13 13 15 now taking the weight and neglecting the weights that generates the cycle 11+12+12+13+13=61 vijju532 answered Jun 16, 2018 vijju532 comment Share Follow See all 2 Comments See all 2 2 Comments reply eyeamgj commented Jun 16, 2018 reply Follow Share question is about number of such spanning trees....read question carefully 0 votes 0 votes vijju532 commented Jun 16, 2018 reply Follow Share As after performing the operation i am getting 5 but i also saw the image and finds the cost too 0 votes 0 votes Please log in or register to add a comment.