矩阵树定理

在图论中，矩阵树定理（matrix tree theorem）或基尔霍夫定理（Kirchhoff theorem）是指图的生成树数量等于拉普拉斯矩阵的代数余子式（所以可以在多项式时间内计算）。

若 G 有 n 个顶点，$\lambda_1, \lambda_2, \dots, \lambda_{n-1}$ 是拉普拉斯矩阵的非零特征值，则

$$t(G)=\frac{1}{n} \lambda_1\lambda_2\cdots\lambda_{n-1}.$$

这个定理以古斯塔夫·基尔霍夫名字命名。这也是凯莱公式的推广（若图是完全图）。

## 定义与定理叙述

设 G 是一个简单的无向图。G 的一个生成树是 G 的一个子图，它是一棵包含 G 所有顶点的树。

G 的拉普拉斯矩阵 L 是一个 n × n 的矩阵（其中 n 为顶点数），定义为图的度数矩阵 D（对角矩阵，对角线元素为各顶点的度数）与邻接矩阵 A（若顶点 i 与 j 相邻则 Aij = 1，否则为 0）之差：

$$L = D - A$$

拉普拉斯矩阵 L 的一个代数余子式是透过删除 L 的某一行（如第 i 行）和某一列（如第 j 列），求剩下小矩阵的行列式，并乘以 (−1)i+j 得到的。

基尔霍夫定理指出：任意图 G 的生成树数量等于其拉普拉斯矩阵 L 的任意一个代数余子式的值（特别地，这些代数余子式的值全部相等）。

## 举例

<image>

对于右图的例子，首先求出拉普拉斯矩阵 $L$:

$$L = \left[\begin{array}{rrrr} 2 & -1 & -1 & 0 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ 0 & -1 & -1 & 2 \end{array}\right].$$

随后求出余子式，也即删除任何一个行和一个列，例如第一行和第一列：

$$L^\ast = \left[\begin{array}{rrr} 3 & -1 & -1 \\ -1 & 3 & -1 \\ -1 & -1 & 2 \end{array}\right].$$

则

$\det(L^*) = 8 = t(G)$.

## 证明大纲

拉普拉斯矩阵有这个属性：任何行或列的元素总和等于 0。因此，无论删除什么行或列，根据线性代数性质，透过行/列变换，所有的代数余子式在数值和符号上完全相同。

下面利用柯西–比内公式证明余子式矩阵 $M_{11}$ 的行列式等于生成树的数量：

- 设 n 为图的顶点数，m 为边数。定义图的定向关联矩阵（Oriented Incidence Matrix）$E$ 为一个 n × m 的矩阵：若第 k 条边连接顶点 i 和 j（且 i < j），则令 $E_{ik} = 1$，$E_{jk} = -1$，该列其余元素为 0。

以先前的例子为例（n = 4, m = 5）：

$$E = \left[ \begin{array}{rrrrr} <pre> 1 & 1 & 0 & 0 & 0 \\ </pre> -1 & 0 & 1 & 1 & 0 \\ <pre> 0 & -1 & -1 & 0 & 1 \\ 0 & 0 & 0 & -1 & -1 </pre> \end{array} \right] .$$

- 已知拉普拉斯矩阵可以分解为 $L = EE^{\mathrm{T}}$。

- 令 $F$ 为删除第一行后的矩阵 $E$（大小为 $(n-1) \times m$），则有 $FF^{\mathrm{T}} = M_{11}$。

- 根据柯西-比内公式，我们可以将行列式展开为：

$$\det\left(M_{11}\right) = \sum_S \det\left(F_S\right)\det\left(F^{\mathrm{T}}_S\right) = \sum_S \det\left(F_S\right)^2$$

其中 S 遍历集合 $\{1, \dots, m\}$ 中所有大小为 n − 1 的子集，而 $F_S$ 表示由矩阵 $F$ 中索引在 S 中的列所构成的 $(n-1) \times (n-1)$ 子矩阵。

每一个子集 S 都对应原图中的 n − 1 条边。可以证明：

- 如果这 n − 1 条边在原图中构成了一棵生成树，则该子矩阵的行列式值 $\det(F_S) = \pm 1$，平方后为 1。
- 如果它们不构成生成树（即含有回路），则 $\det(F_S) = 0$。

这便完成了证明。

## 特殊情况与推广

### 凯莱公式

凯莱公式是基尔霍夫定理的一个经典特例。完全图 Kn 的拉普拉斯矩阵形式如下：

$$\begin{bmatrix} <pre> n-1 & -1 & \cdots & -1 \\ -1 & n-1 & \cdots & -1 \\ \vdots & \vdots& \ddots & \vdots \\ -1 & -1 & \cdots & n-1 \\ </pre> \end{bmatrix}.$$

计算该矩阵的任意一个代数余子式，其行列式结果均固定为 nn-2。这完美印证了完全图包含 nn-2 棵标号生成树的结论。

### 特征值表述法

该定理也可以透过拉普拉斯矩阵的特征值来表达。拉普拉斯矩阵的特征值总是非负的，且必有一个为 0。

设图 G 的特征值按升序排列为 0 = λ0 ≤ λ1 ≤ λ2 ≤ ... ≤ λn-1，则其生成树数量 t(G) 可以表达为所有非零特征值乘积的 1/n：

$$t(G) = \frac{1}{n} \lambda_1\lambda_2\cdots\lambda_{n-1}.$$

### 多重图的基尔霍夫定理

基尔霍夫定理同样适用于包含重边的多重图（Multigraphs），只需对矩阵 L 的定义做微调：

- 元素 Li,j（i ≠ j）等于 −m，其中 m 是顶点 i 和 j 之间的边数。
- 在计算顶点度数时，排除所有的自环（Loops）。

### 生成树的显式枚举

我们不仅可以计算生成树的数量，还可以透过代数方法将它们逐一列举出来：

给图中的每条边赋予一个不定元（变量），并让修改后的拉普拉斯矩阵第 (i, j) 个元素在 i ≠ j 时为顶点 i 与 j 之间所有边的变量之和的相反数，在 i = j 时为从顶点 i 出发的所有边的变量之和。

此时，计算该矩阵任意代数余子式所得到的行列式将是一个齐次多项式（称为基尔霍夫多项式）。将该多项式展开并化简后，其中的每一个单项式都唯一对应一棵生成树（由该单项式包含的变量边组成）。

### 拟阵拓展

在拟阵理论中，图的生成树构成了图形拟阵（Graphic Matroid）的基。因此，基尔霍夫定理实际上提供了计算图形拟阵中“基”的数量的方法。该方法还可以进一步推广到计算正规拟阵（Regular Matroids）中基的数量。

### 有向多重图的基尔霍夫定理

该定理还可以修正为计算有向多重图中有向生成树（又称树形图，Oriented Spanning Trees）的数量。构造矩阵 Q 如下：

- 当 i ≠ j 时，元素 qi,j 等于 −m，其中 m 是从顶点 i 指向顶点 j 的有向边数。
- 对角线元素 qi,i 等于顶点 i 的入度（Indegree）减去 i 处的自环数。

此时，以顶点 i 为根的有向生成树的数量，等于从 Q 中删去第 i 行和第 i 列后剩下子矩阵的行列式值。

### 计算含有 k 个连通分量的生成森林

基尔霍夫定理还能推广到计数无权图中含有 k 个连通分量的生成森林（Spanning Forests）。

给定一个拥有连通分量 $F_1, \dots, F_k$ 的森林 F，定义其权重 $w(F) = |V(F_1)| \cdot \dots \cdot |V(F_k)|$ 为各个分量顶点数的乘积。则所有 k 分量生成森林的权重之和满足：

$$\sum_F w(F) = q_k,$$

这里的 $q_k$ 恰好是多项式

$$(x+\lambda_1) \dots (x+\lambda_{n-1}) x$$

中 $x^k$ 项的系数。