Matrix-Tree 定理学习笔记
__ACat__
·
·
算法·理论
Matrix-Tree 定理
作用
一句话，统计：
- 无向图生成树个数。
- 有向图内向树。
- 有向图外向树。
都可以用可以带权，求一棵树所有边权之积。
如何求
无向图
令 A 和 D 都是一个 n\times n 的矩阵。
$D_{i,j}$ 为点 $i$ 与点 $j$ 直接相连的边权之和。明显有 $D_{i,j}=D_{j,i}$。
**拉普拉斯矩阵**为 $L=A-D$。
令 $L$ 去掉任意一行和一列得到的矩阵为 $L'$。
那么该图的生成树个数就为 $\det (L')$。（$\det$ 表示横列式，计算出来的是一个数，后面会讲。）
#### 有向图内向树
以 $1$ 为根的内向树为例。
令 $A^{out}$ 和 $D$ 都是一个 $n\times n$ 的矩阵。
$A_{i,i}^{out}$ 为点 $i$ **出边**的边权之和，其他地方为 $0$。
$D_{i,j}$ 为**点 $i$ 到点 $j$ 的边**的边权之和。
**拉普拉斯矩阵** $L^{in}=A^{out}-D$。
由于我们以 $1$ 为根，所以去掉 $L^{in}$ 的第 $1$ 行和第 $1$ 列，得到 $L'^{in}$。
那么该有向图的以 $1$ 为根的内向生成树个数就为 $\det (L'^{in})$。
#### 有向图外向树
和上面同理，将 $A^{out}$ 换成 $A^{in}$（入边权值之和），得到 $L^{out}$ 和 $L'^{out}$。
## $\det$ 行列式如何求
二阶的式子定义是简单的：
$$
\begin{bmatrix} a & b \\ c & d \end{bmatrix}=ad-cb
$$
但更高阶的我们就搞不了了，要给出它最基本的定义。
#### 定义
$n$ 阶行列式是所有取自不同行不同列的 $n$ 个元素乘积的代数和，共 $n!$ 项：
$$
\det(A) = \sum_{\pi} (-1)^{\tau(\pi)} \prod_{i=1}^n a_{i,\pi(i)}
$$
其中：
- $\pi$ 是 $1,2,\dots,n$ 的任意一个排列；
- $\tau(\pi)$ 是排列 $\pi$ 的逆序数，用于确定每一项的符号。
#### 性质
（一级为重要的，二级为补充）
我们需要三个比较重要的性质来求解：
* 交换 $A$ 的任意两行/两列得到 $A'$，有 $\det (A)=-\det(A')$。
* 故如果 $A$ 存在两行/两列，则 $\det(A)=-\det(A')=0$。
* 将 $A$ 的第 $b$ 行加上第 $a$ 行乘上 $x$，得到 $A'$，行列式不变。
* 将 $B$ 的某一行乘上一个数 $x$，得到的新矩阵为 $B'$，由行列式的定义可以得到 $\det(B')=x\det(B)$。
* 有个比较明显的：$\det(A+B)=\det (A)+\det(B)$（乘法分配律拆开即可）。
* 那么主定理就很好证明了。
令 $B$ 的第 $b$ 行和 $A$ 的第 $a$ 行一致，其他位置不变，易得 $B$ 的第 $a$ 行和第 $b$ 行一致，有 $\det(B)=0$。
有
$$\det(A')=\det(A)+x\det(B)=\det(A)$$
* 对于左下角都为 $0$ 的矩阵，它的行列是为对角线上的乘积（因为定义中每一行都得有一个，所以有效的乘积只有对角线）。for example:
$$
\begin{vmatrix}
a & b & c & d\\
0 & e & f & g\\
0 & 0 & h & i\\
0 & 0 & 0 & j
\end{vmatrix}=aehj
$$
## 实现
可以使用辗转相除法做到简单的代码复杂度，时间复杂度为 $O(n^3\log n)$：
```cpp
ll det(ll L[N][N],ll n){
//无向图要调用 det(L,n-1)。
int f=1;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
while(L[j][i]){
ll l=L[i][i]/L[j][i];
for(int k=1;k<=n;k++) L[i][k]=(L[i][k]-L[j][k]*l%mod+mod)%mod;
for(int k=1;k<=n;k++) swap(L[i][k],L[j][k]);
f*=-1;
}
ll res=1;
for(int i=1;i<=n;i++) (res*=L[i][i])%=mod;
return (res*f+mod)%mod;
}
```
## 习题及应用
##### [P6178 【模板】Matrix-Tree 定理](https://www.luogu.com.cn/problem/P6178)
模板
##### [[HEOI2015] 小 Z 的房间](https://www.luogu.com.cn/problem/P4111)
模板
##### [CF578F Mirror Box](https://www.luogu.com.cn/problem/CF578F)
图论建模题，矩阵树定理作为工具使用，但也是一道值得联系的题目，不会的建议观看[大佬的题解](https://www.luogu.com.cn/article/51x98sma)。
##### [P3317 [SDOI2014] 重建](https://www.luogu.com.cn/problem/P3317)
要求其他边都断掉，那么我们列出答案公式：
$$
\sum_T \prod_{e\in T}p_e \prod_{e\not\in T}(1-p_e)
$$
转换一下
$$
\sum_T \prod_{e\in T}p_e \frac{\prod_{e}(1-p_e)}{\prod_{e\in T} (1-p_e)}
$$
移出系数
$$
\prod_{e}(1-p_e)\sum_T \prod_{e\in T} \frac{p_e}{1-p_e}
$$
套模板并将 $p_e=1$ 的设为 $1-eps$ 即可。
## 补充
### BEST 定理
~最好的定理~
#### 作用
统计有向图欧拉回路个数（可惜求不来无向图）
注意这里统计的回路是循环同构的。
有公式（把孤点删掉）：
$$
(\text{内向生成树个数})\times \prod (\deg^{out}-1)!
$$
如果要统计从特定节点 $s$ 开始走的，公式为（把孤点删掉）：
$$
(\text{内向生成树个数})\times \deg^{out}_s\times\prod (\deg^{out}-1)!
$$
#### 感性证明
可以见[大佬的文章](https://www.luogu.com.cn/article/iuyzfphy)。