最小生成树的计数问题（Kirchhoff 矩阵树定理）
问题描述
给定一个无向连通图 \(G=(V, E)\)，每条边没有权重（或权重相同）。我们需要求出图 \(G\) 的不同最小生成树（确切说是生成树）的数量。注意，这里“最小”是冗余的，因为所有边权相同，任何生成树都是最小生成树。但算法本身可用于加权图中统计特定权值生成树数量，不过今天先聚焦在无权图的生成树计数。
核心方法
Kirchhoff 矩阵树定理（Matrix-Tree Theorem）可以在多项式时间内解决此问题。其基本思想是：构造图的拉普拉斯矩阵，然后计算该矩阵的任意一个代数余子式，其值即为生成树的数目。
第一步：构造图的度矩阵和邻接矩阵
假设图有 \(n\) 个顶点（标记为 \(1, 2, \dots, n\)）和 \(m\) 条边。
- 度矩阵 \(D\)：一个 \(n \times n\) 的对角矩阵，其中 \(D_{ii} = \deg(i)\)（顶点 \(i\) 的度），非对角线元素为 0。
- 邻接矩阵 \(A\)：一个 \(n \times n\) 的矩阵，如果顶点 \(i\) 和 \(j\) 之间有边，则 \(A_{ij} = 1\)，否则为 0（对于无向图，\(A\) 是对称的）。
例子
考虑一个 4 个顶点的简单图，边集为：{(1,2), (1,3), (2,3), (3,4)}。
度矩阵：
\[D = \begin{pmatrix} 2 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \]
邻接矩阵：
\[A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} \]
第二步：计算拉普拉斯矩阵
拉普拉斯矩阵 \(L\) 定义为 \(L = D - A\)。
对上面例子：
\[L = \begin{pmatrix} 2 & -1 & -1 & 0 \\ -1 & 2 & -1 & 0 \\ -1 & -1 & 3 & -1 \\ 0 & 0 & -1 & 1 \end{pmatrix} \]
第三步：选择一个代数余子式
Kirchhoff 定理说：生成树的数量等于 \(L\) 的任意一个代数余子式的值。
代数余子式 \(C_{ij}\) 是从 \(L\) 中删除第 \(i\) 行和第 \(j\) 列后得到的 \((n-1) \times (n-1)\) 矩阵的行列式。
通常我们选择 \(i=j=1\)（即删除第一行第一列），因为计算方便。
例子：删除第一行第一列得到矩阵：
\[L' = \begin{pmatrix} 2 & -1 & 0 \\ -1 & 3 & -1 \\ 0 & -1 & 1 \end{pmatrix} \]
第四步：计算行列式
计算 \(\det(L')\) 即可。这里我们逐步计算：
\[\det(L') = 2 \cdot \det\begin{pmatrix} 3 & -1 \\ -1 & 1 \end{pmatrix} - (-1) \cdot \det\begin{pmatrix} -1 & 0 \\ -1 & 1 \end{pmatrix} + 0 \cdot \det(\dots) \]
先算第一个二阶行列式：\(3 \times 1 - (-1) \times (-1) = 3 - 1 = 2\)。
第二个二阶行列式：\((-1) \times 1 - 0 \times (-1) = -1\)。
代入：
\[\det(L') = 2 \times 2 + 1 \times (-1) = 4 - 1 = 3 \]
所以这个图的生成树数量是 3。
我们可以手动验证：这个图的 3 棵生成树分别是：
- 边集 {(1,2), (1,3), (3,4)}
- 边集 {(1,2), (2,3), (3,4)}
- 边集 {(1,3), (2,3), (3,4)}
为什么定理成立？（直观解释）
拉普拉斯矩阵 \(L\) 的行和与列和均为 0，所以它有一个特征值为 0，对应的特征向量是全 1 向量。
定理本质是 Cauchy–Binet 公式的一个推论：把 \(L\) 写成关联矩阵 \(B\) 与其转置的乘积（\(L = B B^T\)），然后 Binet–Cauchy 公式表明，\(\det\) 的子式对应选取 \(n-1\) 条边构成生成树的计数。
加权图的扩展
如果图是加权的（权重为正值），并且想求所有生成树的权重乘积之和，那么可以将拉普拉斯矩阵中的边权纳入：
- 度矩阵 \(D\) 的对角线是相连边的权重和。
- 邻接矩阵 \(A_{ij}\) 是边 \((i,j)\) 的权重（如果存在边），否则为 0。
然后同样计算代数余子式，得到的是所有生成树的边权乘积之和。如果要统计最小生成树的数量（权重不同），需先求最小生成树权值 \(W\)，然后只保留权值等于 \(W\) 的边构成的子图，用 Kirchhoff 定理计算该子图的生成树数量（注意子图可能不连通，此时生成树数为 0）。
算法复杂度
计算一个 \(n \times n\) 矩阵的行列式，用高斯消元法需要 \(O(n^3)\) 时间，对于无向图计数生成树是高效的。