The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

What important point we keep in mind while finding the #(number) of spanning tree ?? from the given graph

+1 vote

Best answer

Depends on the method used to find number of MST's.

If you are using KIRCHOFF's THEOREM, then nothing special (except the theorem itself) is to be kept in mind.

If you are finding them manually using some counting tools (such as P and C etc), then :

1.Any spanning tree of a **connected** graph with n vertices will have exactly n-1 edges.

2. Look for the vertices which can be reached from multiple paths.Count the number of ways to reach that vertex.

3. Find a cycle(if any) whose edges are necessarily required to be traversed in order to make it an MST. Try to eliminate 1 edge at a time of that cycle and see how many ways are there to use edges of that cycle.

4.If it is a complete a graph that we have formula for number of MST's of a complete graph(google that).

All these points vary on individual basis.One may use them or not.I use these points.

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- 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.1k
- Non GATE 1.6k
- Others 1.8k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,362 questions

55,789 answers

192,413 comments

90,934 users