Kirchoff's tree theorem was recently used in https://atcoder.jp/contests/abc253/tasks/abc253_h, and it on first glance, almost feels like black magic, but I will show that it is not the case.
So prerequisites... Advanced contestants may skip these
Problem statement
Given an undirected graph $$$G = (V, E)$$$ with no multi edges or self loops, find the number of spanning trees in $$$G$$$.
Bijection between spanning trees and Arborescences
Let us consider all arborescences of $$$G$$$ rooted at $$$r$$$. We can undirect the arborescence to get a spanning tree of $$$G$$$. We can direct all edges of $$$G$$$ away from $$$r$$$ to get the arborescence back. Therefore they are equal in number.
Representing an arborescence as a functional graph transpose
An arborescence is the transpose of a functional graph with $$$f : [1, r-1] \cup [r+1, n] \to [1, n]$$$, where $$$f$$$ corresponds to the parent function in the arborescence. Every functional graph may not form an arborescence, they may have cycles. Notice any cycle must be a directed cycle, as every node has exactly one in edge.
Modeling counting spanning arborescences as counting acyclic functional graphs
Let $$$G$$$ be an undirected graph. We would like to count the number of arborescences rooted at $$$r$$$ in $$$G$$$. Let us root the arborescence at $$$1$$$ for convenience without loss of generality. Let's look at all functions $$$f : [2, n] \to [1, n]$$$ where $$$f(x) \in G_x$$$, where $$$G_x$$$ is the set of nodes connected to $$$x$$$ by an edge. Note any arborescence in $$$G$$$ must correspond to some $$$f$$$ satisfying these constraints, and every arborescence that has an edge not in $$$G$$$ cannot satisfy the given constraints. So we can model the problem as counting the number of functional graphs induced by $$$f$$$ without cycles. Let the set of valid functions be $$$F$$$.
Counting acyclic functional graphs with $$$PIE$$$
Let $$$C_F$$$ be the set of possible cycles in functional graphs induced by functions $$$f \in F$$$. Let $$$c \subseteq C_F$$$ be some subset of cycles in $$$C_F$$$. Let $$$F(c)$$$ be the number of functions in $$$f$$$ with the cycles in $$$c$$$. Then the number of acyclic functional graphs in $$$F$$$ is
Computing $$$F(c)$$$
Notice, that the set $$$c$$$ must consist of only disjoint cycles. Then $$$F(c) = \prod |G_x| = \prod deg_x$$$ for all $$$x \in V$$$ that is not contained in any cycle in $$$c$$$, since $$$f$$$ is already fixed for the elements in the cycles, and the ones not in any cycle could be anything.
How to use determinants to compute this
Since $$$c$$$ is a set of disjoint cycles, and so is a permutation, we can try counting over all permutations. Let us consider some set of cycles $$$c \subseteq C_F$$$ that do not contain $$$1$$$. If $$$c$$$ is not disjoint, we can ignore it. Otherwise, let there be a permutation $$$P$$$ of $$$[2, n]$$$ with the set of disjoint cycles in $$$c$$$, and for those not in $$$c$$$, we can have a self loop. This permutation should be weighted by
Notice this is true, because $$$|c|$$$ is the number of cycles in $$$P$$$ of size more than $$$1$$$, and then we multiply $$$-1$$$ over all elements in cycle of size $$$1$$$.
Notice that the set of cycles in $$$P$$$ are only valid if there exists edge $$$(i, P_i)$$$ for each $$$i$$$ with $$$i \not= P_i$$$. Then we should make matrix $$$M$$$ with $$$M_{i, P[i]} = 1$$$ if there exists such edge and $$$M_{i, P[i]} = 0$$$ otherwise. Any permutation with a cycle not in $$$C_F$$$ will contribute $$$0$$$ to the determinant. We let $$$M_{i, i} = -|G_i| = -deg_i$$$, so that the permutation is weighted by the product of $$$-deg_x$$$ over all self loops. We should remove the row/column corresponding to $$$1$$$, as there is no edge from $$$1$$$, and no cycle in $$$C_F$$$ containing it either. Then it's not hard to see that the determinant here computes the above sum. We should multiply by $$$(-1)^{n-1}$$$ or take the absolute value of the determinant. Alternatively, you can multiply each entry by $$$-1$$$ and get $$$M_{ij} = -1$$$ and $$$M_{u, u} = deg_u$$$, and then just take the determinant. As an exercise you can show that you can find number of arborescence rooted at $$$r$$$ for each $$$r$$$ in a directed graph using a similar method.
Spanning arborescence of directed graphs
If you have understood upto here, You should notice that $$$deg_i$$$ should really be indegree and whether you mark directed edges $$$(u, v)$$$ at $$$M_{u, v}$$$ or $$$M_{v, u}$$$ doesn't really matter.
Expected spanning trees
Let's assume you're given some set of edges, and each edge has some probability of being in our graph. We can compute the expected number of spanning trees. Notice that the old matrix is just sum of product of all edges over all spanning trees. Every spanning tree has a weight of 1 when all edge weights are 1. But if we weight every spanning tree by the product of the probability of each edge, we will get the probability of this spanning tree in our graph. Then summing this over all spanning trees gives us the expected number of spanning trees. For every edge $$$(u, v, p)$$$ you should set $$$M_{v, u} = M_{u, v} = p$$$, and $$$deg_u$$$ should be $$$sum(M_{u})$$$.
Counting spanning forests with mutliple roots.
Let $$$R$$$ be the set of roots. You can remove the row and column corresponding to every node in $$$R$$$. This essentially tells the matrix to not count parent pointers for any node in $$$R$$$, as required.
Counting minimum spanning trees
Iterate over edge weights in increasing order. The edges of the current edge weight, form some connected components. You should multiply the answer by the number of spanning trees of each component. Then merge each connected component into one node, and then repeat for the next smallest edge weight. This will amortize into $$$O(V^3)$$$ since the total component size of components with more than one node is less than $$$2V$$$.
great blog thanks for helping the community
Here is a problem with a pretty interesting transformation to use Kirchoff's Tree Theorem.
There is an undirected weighted simple graph with $$$n$$$ vertices and $$$m$$$ edges. The $$$i$$$-th edge connected vertices $$$(a_i,b_i)$$$ and has weight $$$c_i$$$. For some spanning tree of this graph, the cost of the spanning tree is the ternary xor of all edge weights (addition in $$$\mathbb{Z}_3^X$$$). Find the sum (we use normal addition here) of costs of all spanning trees in this graph modulo $$$M=10^9+7$$$.
$$$1 \leq n \leq 100,1 \leq m \leq \frac{n(n-1)}{2}, 0 \leq c_i \leq 10^4$$$.
tl;dr Kirchoff's tree theorem works even if we send stuff into FFT space.
We will solve for each trit separately. We can find the number of spanning trees for a weighted graph, where the cost is the product of all edges. We can transform our cost to convolution on $$$\mathbb{Z}_M^{\mathbb{Z}_3}$$$ (edges of weight $$$0$$$ get the cost of $$$\{1,0,0\}$$$, edges of weight $$$1$$$ get the cost $$$\{0,1,0\}$$$ and edges of weight $$$2$$$ get the cost $$$\{0,0,1\}$$$). And "product" is this length $$$3$$$ "xor" convolution which we denote $$$*$$$.
So, we have some matrix whose elements are in $$$\mathbb{Z}_M^{\mathbb{Z}_3}$$$ and want to calculate the determinant with $$$+$$$ and $$$*$$$ being our operators. But we cannot calculate the determinant quickly because $$$*$$$ does not have an inverse (although according to this paper, it can be found in $$$O(n^3 \sqrt{n} \log n \log \log n)$$$ ring operations). For example, there is no inverse to $$$\{1,1,1\}$$$. But, if we are to send $$$\mathbb{Z}_M^{\mathbb{Z}_3}$$$ into FFT space, which only requires $$$+$$$ and $$$\cdot$$$, then there should be a inverse for $$$\cdot$$$ since $$$\mathbb{Z}_M$$$ is a field.
Unfortunately, there is no $$$3$$$-rd root in $$$\mathbb{Z}_M$$$. But that's ok, we can just create a new number $$$X$$$ such that $$$X^2+X+1=0$$$ to act as the $$$3$$$-rd root. And thankfully, $$$\mathbb{Z}_M[X]/(X^2+X+1)$$$ is a field. We can naively compute the transformation $$$\mathcal{F}$$$ and $$$\mathcal{F}^{-1}$$$ since $$$|\mathbb{Z}_3|$$$ is so small.
Btw, it seems that calculating determinant when removing any pair of row and column also works. Your proof seems to only work when we remove the same index on the row and column. Is it simple to modify your proof to handle this?
Btw, it seems that calculating determinant when removing any pair of row and column also works. Your proof seems to only work when we remove the same index on the row and column. Is it simple to modify your proof to handle this?
This can easily be shown separately. In the Laplacian matrix each row is the negative sum of others. Suppose you took the Laplacian matrix and erased row x and column y, with x != y. You can now do the following:
Now you have the matrix you would have if you had erased row y and column y instead, and the transformations we did to get from there to here only affected the sign of the determinant. Thus, once you have shown that all (x,x)-cofactors of a Laplacian matrix are the same, you can deduce that the absolute values of all (x,y)-cofactors are also the same.
You could also rationale about it from $$$f(x)$$$ perspective.
When we remove $$$i$$$-th column and $$$j$$$-th row we force $$$f(i)=j$$$ and also force that in the remaining part of the functional graph, there are no cycles other than $$$f(v)=v$$$.
There is a one-to-one correspondence between such functional graphs and graphs having a single cycle $$$f(i)=i$$$, that is corresponding to the arborescence rooted in $$$i$$$. Essentially, the correspondence is:
That being said, removing $$$i$$$-th row and $$$j$$$-th column yields the same result as removing $$$i$$$-th row and column, even for directed graphs.
the old matrix is just sum of product of all edges over all spanning treesWhy the determinant of $$$M$$$ is sum of product of all edges over all spanning trees? Does there have some intuitive explanation of it?
btw, thanks for your blog, it is really easy to understand!
It's very intuitive. You should think about fact that the reason $$$\prod deg_x$$$ counts everything is because its product of number of way to choose. But thats somewhat arbitrary here.
If you have $$$\prod \sum w_i$$$, where $$$w_i$$$ is weight of the connected edges, you will notice that this basically chooses a parent each from each node, and takes the product. So $$$w_i = 1$$$ is actually just arbitrary weight that gets us count of spanning trees. For each functional graph here is automatically weighted by product of $$$w$$$. The same thing is true for the cycles as well, since $$$L_{ij} = -w$$$, and having $$$L_{ij}$$$ in product means I chose that edge, and therefore my answer is multiplied by $$$w$$$.