One can use Kirchof's theorem to get distinct minimum spanning trees .....

The Gateway to Computer Science Excellence

+30 votes

+49 votes

0

Sir,could you explain? actually i want to know if there is any shortcut for finding total number of minimum spanning trees of a Graph.

The steps i have taken to answer this question

1.I used krushkal's algorithm for finding all the minimum spanning trees.

2..Then i counted all the total no of minimum spanning trees.

But that is a lengthy process & takes some time..So i want to know.. is there any other method for fining it easily? Waiting for your Reply :)

The steps i have taken to answer this question

1.I used krushkal's algorithm for finding all the minimum spanning trees.

2..Then i counted all the total no of minimum spanning trees.

But that is a lengthy process & takes some time..So i want to know.. is there any other method for fining it easily? Waiting for your Reply :)

+1 vote

3*2=6

Delete all 2 edges and try to form spanning tree but you cannt

Therefore there there are 3 choices for

Upper right section and 2 for bottom triangle

Delete all 2 edges and try to form spanning tree but you cannt

Therefore there there are 3 choices for

Upper right section and 2 for bottom triangle

0 votes

Below diagram shows a minimum spanning tree. Highlighted (in green) are the edges picked to make the MST.

In the right side of MST, we could either pick edge ‘a’ or ‘b’. In the left side, we could either pick ‘c’ or ‘d’ or ‘e’ in MST.

There are 2 options for one edge to be picked and 3 options for another edge to be picked. Therefore, total 2*3 possible MSTs.

https://www.geeksforgeeks.org/gate-gate-cs-2014-set-2-question-62/

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,324 answers

198,405 comments

105,169 users