矩阵树定理及其证明

PeppaPig_qwq · 2026-04-16 00:14:02 · 算法·理论

最近发现自己忘了矩阵树定理是怎么证的了，所以来补一发。

假设我们有一个无向连通图 G = (V, E)，它有 n 个顶点（V = \{1, 2, \dots, n\}）和 m 条边，且图中没有自环。先定义三个矩阵：

1. 度数矩阵 D：D_{ii} 表示顶点 i 的度数，其余不在对角线上的元素全为 0。
2. 邻接矩阵 A：若顶点 i 和 j 之间有边，则 A_{ij} = 1。若无边，则 A_{ij} = 0。
3. 拉普拉斯矩阵 L：定义为 L = D - A。

矩阵树定理就是说图 G 的所有生成树的总数 \tau(G)，等于其拉普拉斯矩阵 L 的任意一个主子式的行列式。

人话：随意选一个 i，L 中删去第 i 行和第 i 列，得到一个 (n-1) \times (n-1) 的新矩阵 L_i，它的行列式 \det(L_i) 的值，就是生成树的个数。

定理的证明：

先给每一条边随意指定一个方向。

接着，定义一个 n \times m 的矩阵 B，行代表顶点，列代表边。对于元素 B_{ve}：

• 如果边 e 终点是 v，则 B_{ve} = 1。
• 如果边 e 的起点 v，则 B_{ve} = -1。
• 如果边 e 与顶点 v 不相连，则 B_{ve} = 0。

注意到，将 B 与它的转置矩阵 B^T 相乘，结果就是拉普拉斯矩阵。也就是

证明：对于对角线上的元素 (B B^T)_{vv} 是点 v 所有边系数 (\pm 1)^2 的和，恰好等于度数 D_{vv}。而非对角线上的数 (B B^T)_{uv}，只有当边 e 同时连接 u,v 时（一头是 1 另一头是 -1）才会产生 -1 的乘积，恰好对应 -A_{uv}。

然后有一个定理叫柯西-宾纳定理。对于 p \times q 的矩阵 M 和 q \times p 的矩阵 N（p \le q），有

这里的 S 代表从 q 列或行中挑选出 p 列或行的所有可能组合。M_S 是挑出来的列组成的子矩阵。简单来说，它把矩阵乘积的行列式，化成了对所有子方阵行列式乘积的求和。

前置的定理说完了，可以开始讲证明了。

根据矩阵树定理，我们要计算删掉 L 第 i 行、第 i 列后的矩阵 L_i 的行列式。 由于 L = B B^T，我们同步删掉 B 的第 i 行，得到一个 (n-1) \times m 的矩阵 B_i。显然有：

现在，对 L_i 套用柯西-宾纳定理。我们要从 m 条边中选出 n-1 条边，构成边集的子集 S。

由于转置矩阵的行列式不变，即 \det((B_i^T)_S) = \det(((B_i)_S)^T) = \det((B_i)_S)，上式可化简为：

这个公式的含义就是选出任意 n-1 条边构成一个矩阵，算出它的行列式并将其平方，然后把所有选法的结果加起来，就是拉普拉斯矩阵的值。

从图 G 的 m 条边中任意挑出 n-1 条边（子集 S），只有两结果：

1. 这 n-1 条边包含环

   如果 S 中有环，那么环上的边对应的列向量在矩阵中是线性相关的。我们只要顺着环的方向赋予系数 1，逆着环的方向赋予系数 -1，这些列向量的线性组合就恰好为全 0 向量。知周所众列向量线性相关的方阵，其行列式为 0。也就是

   [\det((B_i)_S)]^2 = 0

2. 这 n-1 条边不包含环（即恰好构成一棵生成树）

   如果 S 是一棵树，由于树有 n 个节点和 n-1 条边，它必然至少包含两个度数为 1 的叶子节点。 所以除去被我们提前删掉的节点 i 外，子矩阵 (B_i)_S 内一定还能找到至少一个叶子节点 v。

   观察矩阵中节点 v 对应的那一行。因为它是叶子节点，只连接了一条边，所以这一行只有一个非零元素（必然是 1 或 -1）。

   我们按这一行对行列式进行拉普拉斯展开。有 \det = (\pm 1) \times \det(\text{子余式})。展开后，相当于我们在图中砍掉了这个叶子。剩下的结构仍然是一棵树。

   不断重复肘击叶子的过程，直到矩阵缩小至 1 \times 1，每次提出来的系数都是 \pm 1。因此，连续相乘的结果必定是 \pm 1。所以它的平方为：

   [\det((B_i)_S)]^2 = 1

现在，我们将刚刚的结论代回前面的求和公式中：

在这个求和式中，凡是不能构成生成树的边集 S，贡献的值是 0，凡是能构成生成树的边集 S，贡献的值是 1。

把它们全加起来的结果正好就是图 G 中生成树的总个数 \tau(G)。

至此，矩阵树定理证明完毕。