Matrix Tree 定理及证明

引言

矩阵树定理是一个基于线性代数工具，解决图上生成树计数相关问题的工具。

最大的特点之一就是网上很多人都不会证明。

一些线代基础：矩阵，行列式等。

为什么要写这个证明呢？周围很多人认为比较浪费时间，一般不考。然而输入感知定理其中的智慧，不仅对于图论、线性代数有了更深入的了解，还可以为思维注入一些新鲜血液，因此对我个人而言不全是浪费时间之举。

基础定义

图的关联矩阵

对于一个 (n) 个点（第 (i) 个点记为 (v_i)），(m) 条边（第 (j) 条边记为 (e_j)）的无向图（为方便起见我们在此处暂定一个方向），定义其“关联矩阵” (M) 为：

[M_{i,j} = egin{cases} 1 & e_j ext{是} v_i ext{的入边} \ -1 & e_j ext{是} v_i ext{的出边} \ 0 & extit{otherwise.} \ end{cases} ]

显然大小是 (n imes m) 的。

拉普拉斯（基尔霍夫）矩阵

拉普拉斯矩阵 (L) 定义为：

[L_{i,j} = egin{cases} deg v_i & i = j\ - ext{cnt}(v_i, v_j) & i e j end{cases} ]

其中 (deg v) 表示顶点 (v) 的度数，( ext{cnt}(u,v)) 表示边 (uleftrightarrow v) 的数量。

拉普拉斯矩阵有一个很好的关于关联矩阵的性质（附证明，(M^T) 表示 (M) 的转置）：

[L = M imes M^T \ L_{i,i} = sum_{k=1}^n M_{i,k}M^T_{k,i} = sum_{k=1}^n M^2_{i,k}=deg v_i \ L_{i,j} = sum_{k=1}^n M_{i,k}M^T_{k,j} = sum_{k=1}^n M_{i,k}M_{j,k}=- ext{cnt}(v_i, v_j) ]

(M) 和 (M^T) 相乘的意图何在？注意这样直接实现了内积，对于 (i=j) 的情况，只要 (e_k) 与 (v_i) 相连即产生 (1) 的贡献；对于 (i e j) 的情况，如果 (e_k=(i,j))，那么会有 (-1) 的贡献。通过这个性质我们可以实现 (L) 与 (MM^T)​ 之间的互相转换。除此之外，更加深层的目的将在下面提到。

理论铺垫

关联矩阵与图性质的关系

考虑我们最终的目的是选择 (m) 条边中的 (n-1) 条，那么相当于在关联矩阵中“抽出” (n-1) 列。这些列编号的集合记为 (S)，记 (M[S]) 为 (M) 仅保留列 (S) 得到的矩阵，大小为 (n imes (n-1))（为了方便，如果行比列多，可能以此表示保留行而不是列）。

方阵更容易研究，考虑将 (M[S]) 的某一行扔掉，是不会丢失信息的；相反扔掉更多的行则会有丢失——这一点还原到原图上就比较显然了。这也反映 (M[S]) 的秩为 (n-1)。设丢掉一行后的矩阵为 (M_0[S])，这个“丢掉一行”在原图上可以理解为忽略生成树的根，由于是无向图，根的实际选择不需要关心，因此说将“某一行扔掉”。

思考对于一个不合法的情况，那么图中必然有环。于是不难想到环中这些边对应的列向量必然线性相关。换句话说，不满秩。不满秩的一个比较简洁的充要条件是 (det M_0[S] = 0)。

反之如果生成树合法，那么 (det M_0[S]=pm1)。这个不难证，首先对于一个叶子，必然有对应行只有一个非零元素。使对应行消去其他行，然后该非零元素对应的行列都只有其一个非零元素。我们抛掉这一行和这一列，剩下部分仍然可以归纳下去。最后每行只剩下恰好一列上为 (pm 1)。那么行列式值也为 (pm 1)。

柯西-比内（Cauchy-Binet）定理

设 (A) 为 (n imes m) 的矩阵，(B) 为 (m imes n) 的矩阵，那么：

[det (AB)=sum_{Ssubseteq {1, 2, cdots, m}land |S|=n}(det A[S])(det B[S]) ]

证明？式子太 shit 了先咕了，而且又不是重点，感性理解吧。

Matrix Tree 定理

定理内容

记 (L_0) 为 (L) 去掉某 (k) 行及第 (k) 列所得的方阵，则该无向图的生成树个数为 (det L_0)。

定理证明

根据理论基础，证明非常简单：

[egin{aligned} det L_0 &= det (M_0M_0^T) \ &= sum_{Ssubseteq {1, 2, cdots, m}land |S|=n-1}(det M_0[S])(det M_0^T[S]) \ &= sum_{Ssubseteq {1, 2, cdots, m}land |S|=n-1}(det M_0[S])^2 end{aligned} ]

其中 (S) 恰好为一个选边方案，如果合法那么 (det^2) 产生 (1) 的贡献，反之没有贡献。

最后显然就是生成树的个数。

定理理解

整个定理比较复杂，内容比较多，然而核心是很明确的。

首先是 (M_0[S])​ 的行列式为 (pm 1) 当且仅当生成树合法。

然后借助 Cauchy-Binet 公式中的枚举 (S) 可以完美表示出“枚举边的子集”这一个过程。同时上面 (pm 1) 我们还需要将其转化为 (1)，最后 ((det M_0[S])^2) 正是我们想要的。

Cauchy-Binet 公式中等式的另一边 (det L_0) 简洁且好求，直接根据输入的图即可构造。

直接看整个定理像是凑出来的，然而仔细理解证明，再去挖掘整个想法便豁然开朗了。

有向图上的拓展

一些扯淡

我个人认为，没有理解 Matrix Tree 定理本质，是不太能讲清楚为什么有向图可以这么简单地拓展的。其中的精髓其实是拉普拉斯矩阵的定义，如何设计才最合适。

有向图的 Matrix Tree 定理描述

基于上面的结果，重定义拉普拉斯矩阵：

[L_{i,j}=egin{cases} deg_{ ext{in}}v_i & i = j\ - ext{cnt}(v_i o v_j) & i e j end{cases} ]

其中 (deg_ ext{in} u)​ 表示 (u)​ 的入度；( ext{cnt}(u o v))​ 表示有向边 (u o v)​ 的个数。

(det L_0) 即为外向生成树的个数。

看起来……有那么点道理？

有向图中的定理理解

事实上这里没有什么 (L=MM^T) 了，如果单纯去重定义 (M) 是找不出这样一个 (M)​ 可以满足这个性质凑数上面那个 (L) 的。

这就需要考虑无向图中这个 (M) 的真实目的。对于合法的 (S)，(det M_0[S]=pm 1) 而 ((det M_0[S])^2=1)，这是关键，那么对于有向图我们也从中入手。

考虑一个外向树应该有什么性质。在无向图中我们尝试从树最基本的特征如手，这里我们如法炮制：对于外向树的叶子而言，它只有一个入边。观察关联矩阵，该叶子对应的行一定只有一个 (1)​，其他都是 (0)。

还是消元，我们发现只有一行在这一列有一个 (-1)​，即叶子的父亲。这样一直下去，(M_0)​ 会被消成一个单位矩阵，显然 (det =1)​​，注意不同于之前的 (pm 1)​。还有一点，外向树只是 (det =1) 的充分条件但不必要，这里仍然只保证了构成树。

由于 Cauchy-Binet 公式是帮助我们间接枚举边集用的，实际上不可或缺。我们希望去迎合它，同时在 (det M_0[S]=1) 的基础上再加一个。考虑新设计一个 (n imes m) 的 (D) 矩阵，满足 (det D_0[S]=1)​ 当且仅当​ (S) 构成的图每个点（除了去掉的那一行）都有恰好一条入边——加上这个限制后恰好满足了外向树。

那么 (D) 的构造如下：

[D_{i,j} = egin{cases} 1 & e_j ext{是} v_i ext{的入边} \ 0 & extit{otherwise.} \ end{cases} ]

或许你注意到了：(L=MD^T)​。接下来的步骤大同小异，故 skip。

结语

整个定理结论简单，证明过程也许繁杂但也非无迹可寻。不论是无向图还是有向图，其核心思想是类似的。其中利用行列式值和所求的相对应起来，以及利用 Cauchy-Binet 公式中 (S)​ 的枚举这些思想都是具有启发性的。