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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.