Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I am wondering how to calculate the number of spanning arborescences in a directed graph when a root is specified. For example:
where there are 5 spanning arborescences. Note that there is an edge from b2 to b3 and one from b3 to b2.
Angela Pretorius mentioned a method in Number of Spanning Arborescences, Mathematics, but there is no euclidean circuit in this example. It seems that he/she is referring to BEST theorem.
It seems that Kirchhoff's theorem can be used:
Kirchhoff's theorem can be modified to count the number of oriented spanning trees in directed multigraphs. The matrix Q is constructed as follows:
The entry i, j for distinct i and j equals −m, where m is the number of edges from i to j;
The entry i, i equals the indegree of i minus the number of loops at i.The number of oriented spanning trees rooted at a vertex i is the determinant of the matrix gotten by removing the i-th row and column of Q.
