矩阵树定理学习笔记

矩阵树定理（Matrix-tree Theorem）是把图的生成树个数和矩阵行列式联系起来的一个定理。

矩阵树定理

有向图内向生成树计数

对于无自环（允许有重边）的有向图$G=(V,E)$。设出度矩阵$D(G)$表示每个点的出度的对角矩阵。而$A(G)$表示邻接矩阵，$A_{ij}$表示$(i\to j)$的边数。那么可得到对应的拉普拉斯矩阵（Laplacian Matrix）$L(G)=D(G)-A(G)$。

$L(G)$关于$L(G)_{k,k}$的余子式（也是主子式）是以$k$为根的内向生成树的个数。

无向图生成树计数

主子式形式

对于无自环（允许有重边）无向图$G=(V,E)$，设度数矩阵$D(G)$表示每个点的度，而$A(G)$表示邻接矩阵，$A_{ij}$表示$(i,j)$的重边数。则$L(G)=D(G)-A(G)$。

对于任意$i\in[1,n]$，$L(G)$关于$L(G)_{i,i}$的余子式是生成树的个数。即，无向图的拉普拉斯矩阵的所有$n-1$阶主子式的行列式值都相等。

注意到无向图矩阵树定理求的实际上是$\sum_{T}\prod_{(i,j)\in T}A_{ij}$，因此它也可以理解为是求所有生成树的边权乘积的和。

特征值形式

对于$L(G)$的$n-1$个非零特征值（即无向图的$L(G)$至少有一个特征值为$0$）$\lambda_1,\lambda_2,\cdots,\lambda_{n-1}$，$G$的生成树个数为

$$\frac{1}{n}\prod_{i=1}^{n-1}\lambda_i$$

关联矩阵

在矩阵树定理应用的过程中，我们不太需要关注证明，但需要知道拉普拉斯矩阵是怎么来的。

对于无向图$G$，我们给$G$的每条边随便定向，定向后的图为$G'$。另外我们给边标号，第$i$条边是$(u_i,v_i)$那么定义$G'$的关联矩阵$M(G')$为

$$M_{ij}=\begin{cases} -1 & i=u_j\\ 1 & i=v_j\\ 0 & \text{otherwise} \end{cases}$$

容易证明，$L(G) = M(G')M(G')^T$。

实际上我们也很少关心关联矩阵的性质，我们关注的是：$L$是由两个矩阵相乘得到的。

生成树计数

给出一个$n$个点边带权完全图$G=(V,E,w:E\to \mathbf{Z})$，求其所有生成树的边权和的$k$次方之和，即

$$\sum_{T}\left(\sum_{(u,v) \in T}w(u,v)\right)^k$$

$1\le n\le 30, 0\le k\le 30$。

首先这题用斯特林数是不方便的，考虑生成函数。

我们想办法转化为矩阵树定理方便处理的形式。

注意到$(w_1+w_2+\cdots +w_m)^k = k![x^k]\prod_{i=1}^m e^{w_ix}$，即上式等于

$$k![x^k]\sum_{T}\prod_{(u,v) \in T} e^{w(u,v)x}$$

而我们只需要求$x^k$项，则可以把多项式对$x^{k+1}$取模。所以我们让边权是$e^{w(u,v)x} \bmod x^{k+1}$即可。

有个细节：每个点的度是$d_u = \sum e^{w(u,v)x}$，而不是$\prod$。理解了拉普拉斯矩阵怎么来的就可以理解这一点。

时间复杂度$O(n^3k^2)$。

代码