写在前面

其实矩阵树定理是OI的一个必学知识点,但是由于本人OI学了就忘了,外加现在集合论与图论用到了其相关的知识,故Michael_Bryant在此进行回顾。

一道应用题

我们现在在$A$镇有$n$个城市,我们现在要通过建树要使得任意两座城市之间有且仅有一条路径
$1 \leq n \leq 12$

一种显然的想法

生成树计数问题

并不值得注意的注意

这个问题中显然路径是无向的
针对有向图的矩阵树定理变体我们会在下文给出

问题的解法:Matrix-Tree矩阵树定理

基本概念

1.邻接矩阵$A[G]$
$A[i][j]=i,j$直接相连的边数
2.度数矩阵$D[G]$
$D[i][j]=0(i ≠ j)$
$D[i][j]=degree[i],(i = j)$
其中$degree[i]$表示在图$G$中点$i$的度数

定义

我们定义Kirchhoff矩阵(基尔霍夫矩阵)满足如下计算方法:
$C[G]=D[G]-A[G]$
并基于Kirchhoff矩阵给出我们的Matrix-Tree定理

前置技能

对于矩阵的理解以及对于行列式的理解(笔者认为理解计算和基本定义即可)
在此笔者不进行过多赘述

定义

当我们有了Kirchhoff矩阵之后
我们就可以重新描述Matrix-Tree矩阵树定理了
$G$的所有不同生成树的个数等于其Kirchhoff矩阵$C[G]$任何一个$n-1$阶主子式的行列式的绝对值

Matrix-Tree矩阵树定理的正确性证明

笔者最想逃避的就是这部分
但是发现这部分不写的话和没写这篇博客没什么区别
所以还是别鸽了QAQ

有关Kirchhoff矩阵

我们从对于这个新定义的矩阵的理解开始入手
读者有没有想过 这个矩阵为什么是这样的计算方式
有另外一个矩阵:一个无向图$G(V,E)$的关联矩阵$B$其满足如下定义:
$B _ {ij}=1$,$v_i$为边$e_j$的起点
$B _ {ij}=-1$,$v_i$为边$e_j$的终点
$B _ {ij}=0$,otherwise
此时我们观察$B * B^T$的特点
不难发现$B * B^T$就是Kirchhoff矩阵(建议读者找个图自行验证)
更多地,如果我们记$B_r$为$B$去掉第$r$行形成的矩阵
那么$B_r * B _ r^{T}=C_r$
基于上面那层理解,我们可以给出Kirchhoff矩阵的一些性质,或者说是一些导出更恰当
1.$det(C)=0$
根据这个矩阵的构成容易看出每一行的和是$0$,使用行列式的可加性即可计算
2.如果$G$是一个非连通图,那么$C$的任意一个$n-1$阶主子式为$0$
口胡证明如下:考虑对一个图的Kirchhoff矩阵进行行,列的交换,注意到此时$det(C)$的符号会发生一系列变化,我们使得每个联通块对应的点的度数在主对角线上是连续的。
此时我们对于这个矩阵进行分割:我们发现对于一个大小为$k$的连通块,每行只有$k$个元素不是$0$,并且这一系列元素构成的是该连通块的Kirchhoff矩阵。
整个图的Kirchhoff矩阵变成了一个分块矩阵,主对角线上面是每个联通块的Kirchhoff矩阵。根据分块矩阵的运算性质,此时Kirchhoff矩阵的行列式等于所有小Kirchhoff矩阵行列式的乘积。
取一个主子式,我们只破坏了若干小Kirchhoff矩阵的一个,这并不影响运算结果是$0$(笔者仍然是建议读者进行实践操作)
3.如果$G$是一棵树,那么$C$的除去除第$1$行第$1$列$n-1$阶主子式的值均为$1$
证明如下:数学归纳法
我们证明的目标是把行列式化成主对角线元素均为$1$的三角行列式
Step 1.我们钦定一个根节点记作$V_r$,而后以到$V_r$的距离从小到大为排序依据,对树上的每个节点排序后形成一个节点序列(其中包含节点$V_r$)
那么这个节点序列满足的一条显然的性质是:对于任意一个节点$v_i$,它的父节点一定在它之前出现了(当然每个祖先都出现了)
Step 2.我们根据上面的节点序列进行矩阵中的行列交换,交换方法类似于上面提出的非联通图的交换方法,为了保证主对角线元素仍然处于主对角线,我们一定是行列各交换一次,所以这个过程中行列式的值是保持不变的。
Step 3.我们继续调整,对于每个节点$v_i$,我们将其子节点对应的每一列都加到第$i$列上(这里注意$i \geq 1$)
现在,我们来联想一下这个行列式的最终形式。(如果你想不明白 还是建议进行实操)
首先,对于最后一列的对应节点,它只与自己的父节点相连,度数为$1$并且在主对角线上 这是满足我们的设想的
然后,我们由下向上考虑每个主对角线的元素。假设目前$i-1$行至$n$行全部都是主对角线为$1$并且满足三角行列式的形式,那么我们现在进行对$i$行的考虑
对于节点$v_i$,它的每个子节点对应列中,第$i$行元素为$-1$,对角线的元素此时应当为$1$(因为我们是由下至上归纳的)
再看第$i$列,对应的儿子行的元素都是$-1$,对角线元素应该是$k+1$(分别对应$k$个子节点和一个父节点)
所以进行运算之后满足了主对角线为$1$其余往下均为$0$ 证毕
我们成功得到了一个主对角线元素都是$1$的三角行列式
这样去掉任何一行一列(除第$1$行第$1$列外)剩下的主子式的值都是$1$
相信看懂的读者都能给出结论,经过变换的Kirchhoff矩阵的左上角元素为$0$
这就很简单了 不论是在OI,ACM还是理论应用,我们都人为在那个位置$+1$就好啦
至此,我们对于Kirchhoff矩阵的性质的讨论暂且结束

Binet-Cauchy定理(比内-柯西定理)

这个定理描述了矩阵大小和行列式之间的关系
百度百科对其的证明可以戳下面 笔者在此不进行证明
Binet-Cauchy定理传送门

Matrix-Tree定理真正的证明

我们将$C$的第二种理解带入Binet-Cauchy定理来看看会有什么事情发生
$det(C_r)=det(B_r * B_r^T)$
此时显然是一种$p(=n-1) < q(m) $的情况
所以上式$= \sum _ {x ∈ {1,2...m},|x|=n-1} det(B_r^x * B_r^{x^{T}}) $
其中$B_r^x$表示边含于一个大小为$n-1$的集合的对应的每一列形成的一个新的子式
我们来看$ \sum $符号之后的式子的意义:$B_r^x * B_r^{x^{T}}$
这正好是个Kirchhoff矩阵,这是一个$n-1$阶主子式,其中这个主子式对应的图有$n-1$个边和$n$个点。所以当这个图是树的时候,$det(C)=1$,否则为$0$,注意到对子图求和的过程,正好是对树计数的过程。
问题得证。

定理推广

感觉这部分还是写给ACM和OI的 不过无所谓了

推广到统计边权乘积的和

其实有一个简单暴力的推广办法,因为我们上面的证明支持有重边的图,所以如果边权是整数,我们直接在两个点之间连上边权那么多条边,得到的生成树个数就是所有生成树的边权乘积的和了。如果不是整数,是有理数的话,我们考虑所有边权的最简分母的一个公倍数 $t$,我们把每条边的边权乘以 $t$,然后统计的结果除以$t^{n-1}$就能得到我们要的结果了,考虑利用行列式线性性质把$t^{n-1}$分进行列式里,刚好可以让基尔霍夫矩阵的任意一个主余子式的每一行的所有元素除以 $t$,所以这等价于我们一开始就把基尔霍夫矩阵的每一个元素除以 $t$ 。这样我们得到了一个推广的基尔霍夫矩阵,里面连边数量改成了边权和,度数改成了这个点连出去的边的边权和,并且Matrix-Tree定理在所有元素都是有理数的情况下成立。对于计算机上的浮点数来说这就够了,因为它们都是有理数。
  不过上面这个只是一个小技巧而已,实际上也可以正常地推广,只要考察上面的证明中有什么地方不一样了,再验证它们是否能够保持成立即可(有时我们还会进一步修改证明过程中的定义,就像从树的证明推广到一般无向图一样)。实际上边权乘积刚好符合了我们的过程而边权和就不行了。如果要正经地证明推广的话只是多说一些废话,并没有什么有价值的思想,这里就不啰嗦了。

推广到有向图

到有向图上可能定理就有点变样了,但大致还是在的…首先邻接矩阵改成只记出边,度数矩阵改成了只记入度,然后现在得到的基尔霍夫矩阵的主子式$M _ {ii}$代表了以$i$为根的有向生成树个数。
这下基尔霍夫矩阵的变化比较明显,它不是对称的了,并且它的每行元素的和也不再一定是$0$了(现在是一个点的入度减去出边数)。但是好在每一列的和还是 $0$,所以最重要的性质还没有改变,仍然可以全部行加到一行上来证明它的行列式为 $0$ 。而不连通的图的基尔霍夫矩阵的主子式的值为 $0$ 这一条出现了改变,变成如果从 $i$ 点出发不能到达所有点,则 $M _ {ii}=0$,证明还是类似的,取不能到达的点排在一起,在主对角线上形成一块基尔霍夫矩阵。接下来删点的时候,出现变化的就是这一层点集的出边影响到的点。计数的时候原理没有变化,仍然是成立的。大致就是这样推广到有向图上。
另外这和上一个推广没有什么冲突的地方,两个推广结合在一起也是可以的。

算法流程

构建Kirchhoff矩阵 而后取出一行一列进行高斯消元就好了

一些例题

bzoj 4031
bzoj 3534
(博客上都有题解 懒得找对应luogu的题号了)
还有一个:
给定一个图,图上每条边是红色或蓝色,求恰有 $k$ 条红边的生成树个数。 $n≤50$ 。
这个就是没什么悬念的Matrix-Tree定理了,对于限制条件可以利用多项式,把红边边权设为 $x$,蓝边为 $1$ 。那么最后求行列式得到的多项式中 $x^k$的系数就是答案了。同样这也是利用了边权乘积的那个推广。至于多项式情况下不方便高斯消元的问题,通过代入具体的数插值求多项式就可以解决问题

写在后面

虽然AFO也不打ACM了
但是这种知识还是要经常复习
对于防止脑子生锈有很大的作用啊