计数：Matrix-Tree 定理
Amidst
·
·
题解
作为一个生成树计数中的一个重要定理，Matrix-Tree 拥有通用性强和大家都不会证明的双重优点。
Laplace 矩阵
亦称 Kirchhoff 矩阵。
无向图的 Laplace 矩阵
我们定义 Laplace 矩阵 L = D-A，其中 D 是该图的度数矩阵，A 是该图的邻接矩阵。
我们规定
D_{ij}=\begin{cases}\deg (i),i=j&\\0,i\ne j&\end{cases}
至于邻接矩阵，不必多言。
我们不妨记无向图 G 的生成树个数为 t(G)。
有向图的 Laplace 矩阵
我们定义有向图的出度 Laplace 矩阵 L^{\mathrm{out}}=D^{\mathrm{out}}-A，入度 Laplace 矩阵 L^{\mathrm{in}}=D^{\mathrm{in}}-A，其中 D^{\mathrm{out}} 是该图的出度矩阵，D^{\mathrm{in}} 是该图的入度矩阵。
我们规定
D^{\mathrm{out}}_{ij}=\begin{cases}\deg^{\mathrm{out}}(i),i=j&\\0,i\ne j&\end{cases}
同理，有
D^{\mathrm{in}}_{ij}=\begin{cases}\deg^{\mathrm{in}}(i),i=j&\\0,i\ne j&\end{cases}
我们不妨记有向图 G 以 k 为根的^\dag内向生成树个数为 t^{\mathrm{in}}(G,k)，以 k 为根的外向生成树个数为 t^{\mathrm{out}}(G,k)。
同理，外向生成树即有向图生成的满足所有父节点都只向子节点连有向边的树。
# Matrix-Tree 定理
## 定理内容
### 无向图的 Matrix-Tree 定理
一个无向图 $G$，对于 $\forall k\in[1,n]\cap \mathbb Z$，都有
$$t(G)=\det L_{[n]\setminus \{k\},[n]\setminus \{k\}}$$
其中 $\det A$ 是对 $A$ 的行列式求值的结果。
即无向图 Laplace 矩阵的所有 $n-1$ 阶主子式的值与该图的生成树个数均相等。
如果你不会行列式求值，[click here](https://www.luogu.com.cn/article/ezmuawvs)。
### 有向图的内向生成树的 Matrix-Tree 定理
一个有向图 $G$，对于 $\forall k\in[1,n]\cap \mathbb Z$，都有
$$t^{\mathrm{in}}(G,k)=\det L^{\mathrm{out}}_{[n]\setminus \{k\},[n]\setminus \{k\}}$$
即有向图的**出度** Laplace 矩阵删去第 $k$ 行第 $k$ 列得到的主子式的值与该图的**内向**生成树的个数相等。
### 有向图的外向生成树的 Matrix-Tree 定理
一个有向图 $G$，对于 $\forall k\in[1,n]\cap \mathbb Z$，都有
$$t^{\mathrm{out}}(G,k)=\det L^{\mathrm{in}}_{[n]\setminus \{k\},[n]\setminus \{k\}}$$
即有向图的**入度** Laplace 矩阵删去第 $k$ 行第 $k$ 列得到的主子式的值与该图的**外向**生成树的个数相等。
### 带权无向图的 Matrix-Tree 定理
一个无向图 $G$，对于 $\forall k\in[1,n]\cap \mathbb Z$，都有
$$\sum\limits_{T\in \mathcal T(G)}w(T)=\det L_{[n]\setminus \{k\},[n]\setminus \{k\}}$$
其中 $\mathcal T(G)$ 是图 $G$ 的生成树集合。
### 带权有向图的内向生成树的 Matrix-Tree 定理
一个有向图 $G$，对于 $\forall k\in[1,n]\cap \mathbb Z$，都有
$$\sum\limits_{T\in \mathcal T^{\mathrm{in}}(G,k)}w(T)=\det L^{\mathrm{out}}_{[n]\setminus \{k\},[n]\setminus \{k\}}$$
其中 $\mathcal T^{\mathrm{in}}(G,k)$ 是图 $G$ 的内向生成树集合。
### 带权有向图的外向生成树的 Matrix-Tree 定理
一个有向图 $G$，对于 $\forall k\in[1,n]\cap \mathbb Z$，都有
$$\sum\limits_{T\in \mathcal T^{\mathrm{out}}(G,k)}w(T)=\det L^{\mathrm{in}}_{[n]\setminus \{k\},[n]\setminus \{k\}}$$
其中 $\mathcal T^{\mathrm{out}}(G,k)$ 是图 $G$ 的外向生成树集合。
## 定理证明
### Cauchy-Binet 公式
对于一个 $m\times n$ 的矩阵 $A$ 和一个 $n\times m$ 的矩阵 $B$，有
$$\det(AB)=\sum\limits_{S\subset [m]\land |S|=n}\det A_{S,[n]}\det B_{[n],S}$$
#### 证法一
若 $n>m$，由于
$$\operatorname{rank}(AB)\le\min\{\operatorname{rank}(A),\operatorname{rank}(B)\}\le m<n$$
其中 $\operatorname{rank}(A)$ 为矩阵 $A$ 的秩，故 $\det(AB)=0$。
若 $n=m$，该式显然成立。
下面论证 $n<m$ 的情况。
记 $I_n$ 为 $n$ 阶单位矩阵。
首先有引理
$$\begin{vmatrix}I_n&B\\A&I_m\end{vmatrix}=\begin{vmatrix}I_n&B\\0&I_m-AB\end{vmatrix}=|I_m-AB|$$
$$\begin{vmatrix}I_n&B\\A&I_m\end{vmatrix}=\begin{vmatrix}I_n-BA&B\\0&I_m\end{vmatrix}=|I_n-BA|$$
于是有
$$\lambda^n|\lambda I_m-AB|=\lambda^m|\lambda I_n-BA|$$
考虑证明。
当 $\lambda=0$ 时，显然成立。
当 $\lambda\ne 0$ 时，
$$\begin{aligned}\lambda^n|\lambda I_m-AB|&=\lambda^{n+m}|I_m-\lambda^{-1}AB|\\&=\lambda^{n+m}|I_n-\lambda^{-1}BA|\\&=\lambda^m|\lambda I_m -BA|\end{aligned}$$
设 $P=(p_{ij})_{n,n}$，设展开式系数
$$|\lambda I-P|=\lambda^n+\sum\limits_{k=1}^n(-1)^kc_k\lambda^{n-k}$$
下证 $c_k$ 为 $P$ 中所有 $k$ 阶主子式值之和。
不妨引入 Kronecker 符号
$$\delta_{ij}=\begin{cases}1,i=j&\\0,i\ne j&\end{cases}$$
则
$$|\lambda I-P|=\sum\limits_{\sigma \in S_n}\operatorname{sgn}(\sigma)\prod\limits_{i=1}^n (\lambda \delta_{i,\sigma(i)}-p_{i,\sigma (i)})$$
考虑其中对 $\lambda^{n-k}$ 项系数有贡献的部分。
对于 $\forall \sigma \in S_n$，设
$$\mathscr J(\sigma)=\{J\subseteq\{1,2,3,\dots,n\}\big|\forall j\in J,\sigma(j)=j\}$$
$$\mathscr J_k(\sigma)=\{J\in \mathscr J(\sigma)\big| \lvert J\rvert=k \}$$
则有
$$(-1)^kc_k=(-1)^k\sum\limits_{\sigma \in S_n}\operatorname{sgn}(\sigma)\sum\limits_{J\in \mathscr J_{n-k}(\sigma)}\prod\limits_{i \notin j}p_{i,\sigma(i)}$$
$$c_k=\sum\limits_{|J|=k}\sum_{\sigma\in S_{n,j}}\operatorname{sgn}(\sigma)\prod_{i\notin J}p_{i,\sigma(i)}$$
$$c_k=\sum\limits_{|J|=k}|P_{[n]\setminus J,[n]\setminus J}|$$
则我们证明了该引理。
接下来考虑证明 Cauchy-Binet 公式。
$$\lambda^{n-m}|\lambda I_m-AB|=|\lambda I_n-BA|$$
考察左右两侧 $\lambda^{n-m}$ 项系数，
$$(-1)^m|AB|=(-1)^m\sum\limits_{|J|=m}|(BA)_{[n]\setminus J,[n]\setminus J}|$$
故
$$\begin{aligned}|AB|&=\sum\limits_{|J|=m}|(BA)_{[n]\setminus J,[n]\setminus J}|\\&=\sum\limits_{|J|=m}|A_{[n]\setminus [m],[n]\setminus J}||B_{[n]\setminus J,[n]\setminus [m]}|\end{aligned}$$
#### 证法二
直接暴力计算。
---
Cauchy-Binet 公式表明，Laplace 矩阵的主子式其实是一系列子结构的和，每个子结构都反映了对应子图的性质。
对于 Cauchy-Binet 公式的证明，可以看看[这篇](https://zhuanlan.zhihu.com/p/7837458535)。
### 关联矩阵
我们规定不带权无向图的关联矩阵 $M$ 为
$$M_{ij}=\begin{cases}-1,\exist u(e_i=(v_j,u))&\\1,\exist u(e_i=(u,v_j))&\\0,\mathrm{otherwise}&\end{cases}$$
考虑拓展到带权有向图，容易得知出度关联矩阵 $M^{\mathrm{out}}$ 为
$$M^{\mathrm{out}}_{i,j}=\begin{cases}\sqrt{w(e_i)},\exist u(e_i=(v_j,u))\\0,\mathrm{otherwise}&\end{cases}$$
出度关联矩阵 $M^{\mathrm{in}}$ 为
$$M^{\mathrm{in}}_{i,j}=\begin{cases}\sqrt{w(e_i)},\exist u(e_i=(u,v_j))\\0,\mathrm{otherwise}&\end{cases}$$
显然有
$$D^{\mathrm{out}}=(M^{\mathrm{out}})^TM^{\mathrm{out}},A=(M^{\mathrm{out}})^TM^{\mathrm{in}},D^{\mathrm{in}}=(M^{\mathrm{in}})^TM^{\mathrm{in}}$$
进而有
$$L^{\mathrm{out}}=(M^{\mathrm{out}})^T(M^{\mathrm{out}}-M^{\mathrm{in}}),L^{\mathrm{in}}=(M^{\mathrm{in}}-M^{\mathrm{out}})^TM^{\mathrm{in}}$$
#### 引理
对于 $G$ 的一个子图 $(W,S)$，若 $|W|=|S|\le n$，则
子图 $G_s=(V,S)$ 是一个以 $V\setminus W$ 为根节点集的内向森林，当且仅当
$$\det(M^{\mathrm{out}}_{S,W})\det(M^{\mathrm{out}}_{S,W}-M^{\mathrm{in}}_{S,W})\ne 0$$
且当上式成立时，其值必然为
$$\prod\limits_{e\in S}w(e)$$
记之为 $w(G_s)$。
#### 引理的证明
证明我不是很会，可以去 [OI-Wiki](https://oi-wiki.org/graph/matrix-tree/#%E7%94%A8%E5%85%B3%E8%81%94%E7%9F%A9%E9%98%B5%E5%88%BB%E7%94%BB%E5%9B%BE%E7%9A%84%E7%BB%93%E6%9E%84) 查看。
----
现在可以证明 Matrix-Tree 定理了。
我们以带权有向图的内向生成树的 Matrix-Tree 定理为例，记 $W=[n]\setminus\{k\}$ 为除去节点 $k$ 后的点集。
#### 带权有向图的内向生成树的 Matrix-Tree 定理
一个有向图 $G$，对于 $\forall k\in[1,n]\cap \mathbb Z$，都有
$$\sum\limits_{T\in \mathcal T^{\mathrm{in}}(G,k)}w(T)=\det L^{\mathrm{out}}_{[n]\setminus \{k\},[n]\setminus \{k\}}$$
其中 $\mathcal T^{\mathrm{in}}(G,k)$ 是图 $G$ 的内向生成树集合。
#### 证明
根据 Cauchy-Binet 公式，有
$$\begin{aligned}\det L^{\mathrm{out}}_{[n]\setminus \{k\},[n]\setminus \{k\}}&=\det(L^{\mathrm{out}}_{W,W})\\&=\sum\limits_{S\subset [m]\land |S|=n-1}\det M^{\mathrm{out}}_{S,W} \det (M^{\mathrm{out}}_{S,W}-M^{\mathrm{in}}_{S,W})\end{aligned}$$
由关联矩阵引理，当且仅当 $T$ 是一个以 $k$ 为根的内向树时，右侧累加一个 $w(T)$。
# Cayley 公式
$n$ 个节点的有标号不同构无根树数量为 $n^{n-2}$。
## 证法一：一一对应
考虑利用组合数学证明。
钦定 $T$ 是其中一棵树，叶子节点中标号最小的记为 $a_1$，$a_1$ 的邻接点（即有根树中的父亲）记为 $b_1$，从图中删去 $a_1$ 及所有连边，$b_1$ 便成为这棵树的顶点。
在余下的树 $T_1$ 中，叶子节点中标号最小的记为 $a_2$，$a_2$ 的邻接点记为 $b_2$，从图中删去 $a_2$ 及所有连边，$b_2$ 便成为这棵树的顶点。
如此步骤继续 $n-2$ 次，直到剩下最后一条边，于是一棵树 $T$ 对应一个序列
$$b_1,b_2,b_3,\cdots,b_{n-2}$$
其中 $b_i\in [1,n] \cap \mathbb Z$，并且**允许重复**。
为何允许重复比较易懂，留给读者自行思考。
现在证明一个序列对应一棵树。
我们不妨再引入一个序列
$$c_1,c_2,c_3,\cdots,c_n$$
其中 $c_i=i$。
在序列 $c$ 中找出第一个不出现在序列 $b$ 中的数，显然，这个数是 $a_1$，同时，我们有了一条边 $(a_1,b_1)$，我们从 $c$ 中消去 $a_1$，从 $b$ 中消去 $b_1$，在余下的部分中继续执行此操作 $n-2$ 次。最后，$c$ 中剩余两个数，即为 $a_{n-1}$ 和 $b_{n-1}$，是树 $T$ 的最后一条边。
于是我们证明了序列 $b$ 和树 $T$ 一一对应。
考虑计数，由于序列 $b$ 可重，故总方案数为
$$n^{n-2}$$
序列 $b$ 也称为树 $T$ 的 Prüfer 序列。
## 证法二：Matrix-Tree 定理
不妨转化问题，我们发现原问题等价于求 $n$ 个顶点的完全图的生成树数量。
我们写出 Laplace 矩阵
$$L=\left\lgroup\begin{array}{cc}n-1&-1&-1&\cdots&-1\\-1&n-1&-1&\cdots&-1\\-1&-1&n-1&\cdots&-1\\\vdots&\vdots&\vdots&\ddots&\vdots\\-1&-1&-1&\cdots&n-1\end{array}\right\rgroup_{n\times n}$$
计算其任意 $n-1$ 阶主子式，有
$$\begin{aligned}\det(nI_{n-1}-{\bf 1} {\bf 1}^T)&=n^{n-1}\det(I_{n-1}-n^{-1}{\bf 1}{\bf 1}^T)\\&=n^{n-1}(I_{n-1}-n^{-1}{\bf 1}^T{\bf 1})\\&=n^{n-1}(1-\frac{n-1}{n})\\&=n^{n-2}\end{aligned}$$
应用无向图的 Matrix-Tree 定理，原命题得证。
# BEST 定理
设 $G$ 为有向欧拉图，$k$ 为任意顶点，则 $G$ 的不同欧拉回路个数
$$\operatorname{euc}(G)=t^{\mathrm{in}}(G,k)\prod\limits_{v\in V}(\deg(v)-1)!$$
BEST 定理表明，对于 $\forall k,k'\in V_G$，都有 $t^{\mathrm{in}}(G,k)=t^{\mathrm{in}}(G,k')$。
## 证明
考虑图 $G$ 的任意一棵内向树，对于每个节点 $u$，我们给以 $u$ 为起点的所有**不在**内向树上的 $\deg(u)-1$ 条**出边**一个顺序，称这个根向树及这个出边的排列顺序为一个组合。
于是我们只需要证明组合和欧拉回路一一对应。
考虑从根节点开始，每到达一个节点，若不在内向树上的出边都被走过了，就沿着根向树上的边走向其父亲，否则就按照出边的排列顺序走向下一个节点。
注意到这样只会经过每个节点至多一次，现在证明这样会**经过且仅经过每个节点一次**。
不妨设到达节点 $u$ 后无法移动，考虑分类讨论。
若 $u$ 不是根节点，我们经过 $u$ 时会经过其一条入边和一条出边，而无法移动说明只经过了 $u$ 的一条入边，说明 $\deg^{\mathrm{in}}(u)=\deg^{\mathrm{out}}(u)+1$，与 $G$ 为欧拉图矛盾。
这样我们就证明了这种方案一定会形成一个欧拉回路。
现在我们证明了一个组合对应一个欧拉回路，接下来考虑证明一个欧拉回路对应一个组合。
记 $e_u$ 为 $u$ 最后访问的入边，下面证明所有 $e_u$ 构成一棵内向树。
不妨设 $e_u$ 构成的图中有环，首先根节点必然不会出现在环上。现在环上找出任意一个节点 $u$，容易发现 $u$ 沿着环的方向可以再次回到 $u$。由于原图是欧拉图，$\deg^{\mathrm{in}}(u)=\deg^{\mathrm{out}}(u)$，而 $u$ 在环上回到 $u$ 会导致 $\deg^{\mathrm{in}}(u)=\deg^{\mathrm{out}}(u)+1$，矛盾，故所有 $e_u$ 构成树。
其实我觉得到 $\deg^{\mathrm{in}}(u)=\deg^{\mathrm{out}}(u)$ 即可推出结论，因为这说明根节点与这个环的任意一个节点没有连边。
于是一个组合和一个欧拉回路**一一对应**。
# 典例
## SP104 HIGH - Highways
直接连边后求出 Laplace 矩阵，删去任意一个点后高斯消元求解即可。
```cpp
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%lld%lld",&u,&v);
a[u][v]--;
a[v][u]--;
a[u][u]++;
a[v][v]++;
}
ans=det(n-1);
```
## P4111 [HEOI2015] 小 Z 的房间
同样地，求出 Laplace 矩阵后高斯消元求解即可。
## P3317 [SDOI2014] 重建
给定了 Laplace 矩阵，直接高斯消元求解。
## P4208 [JSOI2008] 最小生成树计数
先跑最小生成树，若没有直接输出 $0$，由于权值相同边至多 $10$ 条，一边并查集合并一边求行列式，最后将贡献加起来即可。
```cpp
if(!kruskal(n,m))
{
printf("0\n");
return 0;
}
int ans=1;
for(int i=1;i<=cntv;i++)
{
init(n);
for(int j=1;j<n&&tr[j].w!=v[i];j++)
merge(tr[j].u,tr[j].v);
for(int j=n-1;j>=1&&tr[j].w!=v[i];j--)
merge(tr[j].u,tr[j].v);
cntb=0;
for(int j=1;j<=n;j++)
if(fa[j]==j)
b[j]=++cntb;
for(int j=1;j<=n;j++)
b[j]=b[find(j)];
memset(a,0,sizeof a);
for(int j=1;j<=m;j++)
{
if(e[j].w!=v[i])
continue;
a[b[e[j].u]][b[e[j].v]]--;
a[b[e[j].v]][b[e[j].u]]--;
a[b[e[j].u]][b[e[j].u]]++;
a[b[e[j].v]][b[e[j].v]]++;
}
ans=ans*det(cntb-1)%mod;
}
```
## P2143 [JSOI2010] 巨额奖金
和最小生成树计数是一个题，略微转化即可。
## P6178 【模板】Matrix-Tree 定理
无向边变为了有向边。建立 Laplace 矩阵的时候删去一半即可，删去的一半和剩下的一半只要对称即可。
```cpp
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
if(u==1||u==n)
u=n-u+1;
if(v==1||v==n)
v=n-v+1;
a[u][v]=(a[u][v]-w+mod)%mod;
a[v][v]=(a[v][v]+w)%mod;
if(!t)
{
a[v][u]=(a[v][u]-w+mod)%mod;
a[u][u]=(a[u][u]+w)%mod;
}
}
printf("%lld\n",det(n-1));
```
## P2144 [FJOI2007] 轮状病毒
这里讲一种很无脑的做法。
求出 Laplace 矩阵，直接删去中间点后消元，删去中间点的过程可以简化为 $a_{ii}\gets a_{ii}+1$。
高精计算即可，注意优化高精度。
## P4455 [CQOI2018] 社交网络
也是有向图形式的 Matrix-Tree 定理板子。同样高斯消元求解即可。
## P5296 [北京省选集训2019] 生成树计数
建立 Laplace 矩阵时矩阵内的值变成了多项式，考虑 $\exp$ 形式后就很好做。
```cpp
K++;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
int w;
scanf("%lld",&w);
if(i>j)
continue;
poly tmp=exp(w);
a[i][j]=a[i][j]-tmp;
a[j][i]=a[j][i]-tmp;
a[i][i]=a[i][i]+tmp;
a[j][j]=a[j][j]+tmp;
}
printf("%lld\n",det(n-1)[K-1]*fac[K-1]%mod);
```
## P6624 [省选联考 2020 A 卷] 作业题
是上一题的弱化版。以同一种方式考虑即可。
## P5807 【模板】BEST 定理 | Which Dreamed It
BEST 定理的直接应用。套用 BEST 定理直接计算即可。
## P7531 [USACO21OPEN] Routing Schemes P
有人说很难看出来是 BEST 定理，我觉得很显然。直接套用 BEST 定理即可，注意起点和终点的处理，使用一种类似网络流的形式建立超级源点和超级汇点即可。
# 编者按
本文在洛谷、博客园和 CSDN 更新。后续可能会补充。
## 参考资料
[矩阵树定理 - OI Wiki](https://oi-wiki.org/graph/matrix-tree/)
[Matrix Tree 定理及证明 - \_Wallace\_](https://www.cnblogs.com/-Wallace-/p/matrix-tree.html)
[柯西比内Cauchy-Binet公式的3种证明 -
Whitea](https://zhuanlan.zhihu.com/p/7837458535)
[矩阵树定理&BEST定理学习笔记 - tzc_wk](https://www.cnblogs.com/tzcwk/p/matrix-tree-best-theroem.html)
[代数学讲义 - 李文威](https://www.wwli.asia/index.php/en/books-item-en)
[高等代数（第五版） - 王萼芳、石生明](https://xuanshu.hep.com.cn/front/book/findBookDetails?bookId=5bc22d0ef18f967ee7f37820)
[高等代数 辅导及习题精解（北大|第五版） - 张天德](https://www.hep.com.cn/book/show/9f2bd856-3e5d-4d99-a06c-e362feccc207)
[组合数学（第5版） - 卢开澄、卢华明](https://www.tup.tsinghua.edu.cn/booksCenter/book_07098001.html)