Everule's blog

By Everule, history, 3 years ago, In English

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

Prerequisites

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

$$$\sum\limits_{c \subseteq C_F} (-1)^{|c|}F(c)$$$

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

$$$(-1)^{|c|} \prod\limits_{P[x] = x} deg_x = (-1)^{n-1}\text{sgn}(P)\prod\limits_{P[x] = x} -deg_x$$$

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$$$.

  • Vote: I like it
  • +251
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +53 Vote: I do not like it

great blog thanks for helping the community

»
3 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Here is a problem with a pretty interesting transformation to use Kirchoff's Tree Theorem.

Translation
Solution

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?

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    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:

    • Take the original row y.
    • Multiply it by -1 (this changes the sign of the determinant).
    • Subtract each other row from it (this does not change the determinant). You have now turned row y into row x.
    • Reorder the rows to get row x into its proper place (this may change the sign of the determinant depending on the parity of x and y).

    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.

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 3   Vote: I like it +8 Vote: I do not like it

      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:

      • Change $$$f(i)=j$$$ to $$$f(i)=i$$$;
      • Change $$$f(v)=v$$$ to $$$f(v)=j$$$;

      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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the old matrix is just sum of product of all edges over all spanning trees

Why 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!

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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$$$.