Matrix Tree定理入门笔记
Walking_Dead
2020-02-27 12:49:48
[或许更好的阅读体验](https://www.cnblogs.com/Dark-Romance/p/13276282.html)
# Matrix Tree定理
## 写在前面的话
写这篇博客其实写了很久,主要是刚开始的时候太菜了,完全不能完全理解,于是,我写的东西当我变得强一点之后就会发现有点问题,于是就改啊改啊添啊添啊,于是就从刚才开始的那个样子变成了现在这样。
希望我写的博客能对初学矩阵树定理的同学有一点帮助。
## 前置知识:行列式
### 行列式的定义
一个矩阵的行列式定义为:
$$\sum_{p} (-1)^{\pi (p)} \prod_{j=1} A_{j,p_j}$$
这里的$p$指的是$\{1,2,3,...,n\}$的一种排列,$\pi (p)$指的是$p$的逆序对个数
### 行列式的求法
如果我们直接用暴力的话时间复杂度为$\Theta (n\times n!)$,但是实际上我们可以对此进行优化。
-----------------------
#### 性质1
>
交换矩阵的任意两行,行列式变号
我们可以发现交换了两行以后,变化的只有符号位,但是如何说明一定为变成相反数呢?我们发现这个问题只与排列的逆序对数有关,下面引出一个命题来证明。
#### 定理1
>
一个排列交换其中任意两个元素,逆序对个数变化量为奇数
#### 证明1
显然。我们可以发现变化量只跟两个元素之间的元素有关,然后就很好证了,这里就不赘述了。
#### 性质2
>
矩阵的一行都乘以$k$,行列式也乘以$k$
#### 证明2
根据定义公式,显然。
#### 性质3
>
如果矩阵内有两行相等,那么行列式为$0$
#### 证明3
因为交换以后要变为相反数,但是可以看出变化前与变化后行列式一样,所以为了满足条件,行列式的值为$0$。
#### 性质4
>
如果一行是另一行的$k$倍,那么行列式值为$0$。
#### 证明4
由性质$2$和性质$3$显然。
#### 性质5
>
一行加上另一行的$k$倍,行列式不变。
#### 证明5
可以从行列式定义的式子下手。
我们可以把现矩阵的行列式拆成两个行列式相加,一个是原先矩阵的行列式,另一个是增长的行列式。
根据性质$4$,可以得到增长的行列式为$0$。
#### 性质6
>
一个上三角矩阵的行列式为斜边元素之积。
#### 证明6
根据公式显然。
--------------------------
有了上面的$6$个性质,我们就可以用$\text {Gauss}$消元把原矩阵消成一个上三角矩阵,然后就好求了。
### 模数非质数时的求法
如果模数非质数我们就不能直接用费马小定理或者拓展欧几里得了。
我们可以考虑用类似于辗转相除法的一种做法,我们一直去找其它行来尽可能抵消当前这一行,然后每一次操作就把两行进行一次尽可能的抵消,实际上就是辗转相除法。结局肯定与辗转相除法一样有一行该列终于变成了零。我们发现这个的时间复杂度也是$\Theta(n^3\log n)$的。
不过还是有$\Theta(n^3)$,不过因为我太弱了,这里先咕着。
upd on 2022/05/02:
之前就听说了辗转相除法是 $\Theta(n^3)$,但一直没有来改,现在来改一下吧。
## 前置定义:Kirchhoff矩阵
$\text {Kirchhoff}$矩阵是指的对于一个图构造出来的一个矩阵。具体定义为度数矩阵减去邻接矩阵。
度数矩阵指的是:
$$A_{i,j}=
\begin{cases}
degree_i,i=j\\
0,i\not= j
\end{cases}$$
邻接矩阵应该就不用解释了。不过需要注意的是如果有重边的话应该算有多少条。
## Matrix Tree定理
>
一个图中的生成树个数等于其$\text {Kirchhoff}$矩阵的任意一个 **代数余子式的行列式**。
## Matrix Tree定理的证明
### 性质1
一个图的$\text {Kirchhoff}$矩阵行列式为零。
### 性质2
一个图的$\text {Kirchhoff}$矩阵的任一代数余子式的行列式相同。
### 前置定义
我们定义一个图的关联矩阵$B$为:
$$
\forall e_{k}=\{ u_k,v_k\}
$$
$$
\exists B_{k,u_k}=1,B_{k,v_k}=-1
$$
我们定义一个矩阵$A$的转置矩阵$A^T$为:
$$A^T_{i,j}=A_{j,i}$$
### 证明
首先我们可以得到,对于一个图,设它的$\text {Kirchhoff}$矩阵为$\text L$,关联矩阵为$\text B$,那么有:
$$\text L=\text B \text B^T$$
这个很好证明,只需要把式子列出来一下就好了。
## Part$1$
>
对于一个非连通图$\text G$,$|L|=0$
### 证明
$|L|$是$L$的行列式。我们再设$M_i$为$L$删去第$i$行第$i$列后得到的矩阵。
首先,我们考虑把$\text G$视作若干个强连通分量,就叫做$G_1,G_2,G_3,...,G_k$吧。
那么,我们可以考虑对$L$进行一下交换,把一个联通块内的元素在$L$排在相邻位置。就比如如果$1,2$在同一联通块,我们就可以第一行放$1$,第二行放$2$。
那么:
$$
L=
\begin{matrix}
G_1 & 0 & 0 & ... & 0\\
0 & G_2 & 0 & ... & 0\\
0 & 0 & G_3 & ... & 0\\
... & ... & ... & ... & ...\\
... & ... & ... & ... & ...\\
0 & 0 & 0 & ... & G_k
\end{matrix}
$$
我们这个时候可以不去考虑符号位的变化,因为如果$|L|=0$也没有区别。
我们可以看出:
$$|L|=|G_1|\times |G_2|\times ...\times |G_k| $$
这个我们可以通过想象高斯消元过程来说明。因为最后消掉以后都是上三角矩阵,那么,对于$\forall i,G_i$都是上三角矩阵,那么就满足条件了。
又因为$\text {Kirchhoff}$矩阵的性质$1$,所以
$$\forall i,|G_i|=0$$
所以$|M_i|=|L|=0$。
## Part$2$
我们考虑一棵树$G$。
可以通过数学归纳法说明$|M_i|=1$,这里就不赘述了。
## Part$3$
这里我们首先要提到一个定理: **Binet-Caucthy**定理
---------------------
### $\text{Binet-Caucthy}$定理
>
$|AB|=\sum_{|s|=n} |A_{p}B_{p}|$
其中$A,B$不一定是方阵。$s$指的是一个从$\{1,2,3,..,m\}$中选出的一个集合。$A_p$表示$A$的列中只保留$s$中选中的列留下的矩阵。
由于作者水平有限,这里没有办法证明。(因为我太菜了)
---------------------
那么,我们就可以进行推导了。我们设$B_i$为$G$的关联矩阵$B$去掉$i$这一列的矩阵。可以得到:
$$|M_i|=|B_i B^T_i|=\sum_{|s|=n-1} |{B_{i}}_p {B^T_i}_p|$$
根据$\text {Part}2$,后面那部分只有在$s$选出来的边构成树的时候为$1$,其余时候皆为$0$。
于是原式就等于从$\text G$中选出$n-1$条边组成一棵树的方案数。
至此,证毕。
# $\text{Matrix Tree}$定理的应用
## $\text {The 1st}$
[题目传送门](https://www.luogu.com.cn/problem/SP104)
## 题目大意
给定一张无向图,求其生成树个数
## $\text{Solution}$
模板题。用$\text{Matrix Tree}$求解即可。不理解$\text {Matrix Tree}$定理的也可以通过阅读代码理解。
## $\text {Code}$
[具体实现](https://www.luogu.com.cn/paste/rvkk0470)
## $\text {The 2nd}$
[题目传送门](https://www.luogu.com.cn/problem/P3317)
## 题目大意
有$n$个节点,$m$条边,每条边有$p_i$的概率留下来。求最后留下一棵树的概率。
## $\text{Solution}$
这道题给了我们一个启示,$\text {Matrix Tree}$定理其实是可以推广的。推广到一般情况,$\text {Matrix Tree}$其实求的是所有可能生成树边权之积的和。
这道题是求刚好留下一棵生成树的概率,那么,即是求:
$$\sum_{\text {tree}} (\prod_{i\in \text {tree}} p_i \prod_{i\not \in \text {tree}}(1-p_i))$$
$$=\sum_{\text {tree}} (\prod_{i\in \text {tree}} p_i \frac{\prod_{i} (1-p_i)}{\prod_{i\in \text {tree}} (1-p_i)})$$
$$=\prod_{i=1} (1-p_i) \sum_{\text {tree}}{ \frac{p_i}{1-p_i}}$$
这个时候我们只需要把 $\frac{p_i}{1-p_i}$ 视作第$i$条边的边权即可。那么一个点的度数就是所有以它为端点的边的边权和。
其实$\text {Matrix Tree}$定理还可以推广到有向图里面去,只需要建图的时候有方向性即可。
## $\text {Code}$
[具体实现](https://www.luogu.com.cn/paste/fiwdu8x4)
## $\text {The 3rd}$
[题目传送门](https://www.luogu.com.cn/problem/P4336)
## 题目大意
有$n$个节点若干条条边,有$n-1$个公司,每个公司有可以修的边的名单,求每个公司刚好修一条路修出一棵树的方案数。
## $\text {Solution}$
这道题有两个限制,那我们就只好考虑容斥了。
如果我们直接算出$n-1$个公司修铁路的方案数,很显然,我们多算了。因为我们也算上了$n-2$个公司修的方案数,那我们就得减去$n-2$个公司修的方案数,那$n-2$个公司修的方案数又得减去$n-3$个公司修的方案数......以此类推,不难看出这就是个容斥了。
然后套一下矩阵树定理的板子就好了。
## $\text{Code}$
[具体实现](https://www.luogu.com.cn/paste/m6wuif9j)
## $\text {The 4th}$
[题目传送门](https://www.luogu.com.cn/problem/CF917D)
## 题目大意
给定一棵$n$个点的数,对于每个$k\in [0,n-1]$,求出恰好有$k$条边与给定树相同的生成树个数。
## 思路
感谢 @EMT__Mashiro 的点拨。
我们上文提到了,其实矩阵树定理求的是:
$$\sum_{T} \prod_{e_i \in T} w_{e_i}$$
$w_i$表示第$i$条边的权值。
我们对于这道题,我们其实可以发现,如果我们对于在给定树中出现的边赋值为$x$,未出现过的赋为$1$,那么,对于$k\in [0,n-1]$,答案就是:
$$[x^k] \sum_{T} \prod_{e_i \in T} w_{e_i}$$
但是我们显然不可能直接拿矩阵树定理套多项式吧?(常数爆炸警告!)我们可以发现这其实是一个$n-1$次的多项式,于是我们可以选$n$个点求到答案然后用高斯消元求到系数即可。
## $\text {Code}$
[具体实现](https://www.luogu.com.cn/paste/3pe52c81)
## $\text {The 5th}$
[题目传送门](https://www.luogu.com.cn/problem/P6624)
## 题目大意
给出一个图,求出:
$$\sum_{T}(\sum_{i=1,e_i \in T}^{n-1} w_{e_i}) \times gcd(w_{e_1},w_{e_2},w_{e_3},..,w_{e_{n-1}})$$
## 思路
先讲个特别有趣的事情,这道题其实是$2020$省选$\text {Day2T3}$,然后恰好那天luogu日报就是这篇博客。。。
我们发现其实这个式子可以反演,就可以变成:
$$\sum_{T}(\sum_{i=1,e_i \in T}^{n-1} w_{e_i}) \times \sum_{d|w_{e_1},d|w_{e_2},...,d|w_{e_{n-1}}} \varphi (d)$$
$$=\sum_{d=1} \varphi (d) \sum_{T} (\sum_{i=1,i_i \in T,d|w_{e_i}} w_{e_i})$$
于是我们的问题就是如何求出后面那个东西,其实我们有了上一道的基础,我们可以把边权设为$1+xw_{e_i}$,那么,答案就是一次项的系数了。于是,我们就可以模拟一个一次多项式$\Theta(144 n^4)$解决了。($\sqrt {152501}\approx144$)但是其实$\Theta(144n^4)$只是一个上界,实际上远远跑不满,只要剪枝剪得好就可以在$500\text {ms}$左右通过这道题。
## 一个小小的拓展
其实矩阵树定理可以拓展到交换环上的元素。交换环就是说上面的元素都满足交换律。