Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I already asked a question about paths. This time is about trees. Knowing the adjacent matrix, is it possible to calculate (with permutations?) the number of possible trees that can be generated from a chosen vertex?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

If you know the adjacency matrix of a graph you can then construct the Laplacian matrix, and use the Matrix-Tree Theorem to determine the total number of distinct spanning trees in the graph. Because each spanning tree contains each vertex of the graph any spanning tree can be "generated" from any vertex.

If you would like all of the trees enumerated, you can use the instructions given at the bottom of the wiki page under the subheading, "Explicit enumeration of spanning trees," but that method requires a significant amount of algebraic manipulation. Similarly, if you are considering digraphs, there are different constructions of the Laplacian that you can use to better tailor your results.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.