矩阵树定理

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

若 G 有 n 个顶点，λ₁, λ₂, ..., λ_n_-1 是拉普拉斯矩阵的非零特征值，则

t (G) = \frac{1}{n} λ_{1} λ_{2} \dots λ_{n - 1} .

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

举例

对于右图的例子，首先求出调和矩阵 $Q$ :

Q = [\begin{matrix} 2 & - 1 & - 1 & 0 \\ - 1 & 3 & - 1 & - 1 \\ - 1 & - 1 & 3 & - 1 \\ 0 & - 1 & - 1 & 2 \end{matrix}] .

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

Q^{*} = [\begin{matrix} 3 & - 1 & - 1 \\ - 1 & 3 & - 1 \\ - 1 & - 1 & 2 \end{matrix}] .

则

$\det (Q^{*}) = 8 = t (G)$ .

完全图 K_n 的调和矩阵是

[\begin{matrix} n - 1 & - 1 & \dots & - 1 \\ - 1 & n - 1 & \dots & - 1 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ - 1 & - 1 & \dots & n - 1 \end{matrix}] .

任何餘因子的行列式是 n^n-² 。再说L的所有特征值是n，而且L只有n-1个特征向量。所以生成树的总数又是 n^n-² 。

拉氏矩阵有这个属性：任何行或列的元素总和等于0。所以，无论删除什么行或列， $\det (L^{*})$ 都是不变的。或者说L的任何餘因子有同样的行列式。

若 $K$ 是接续矩阵，则拉普拉斯矩阵 $L = K K^{T}$ 。在矩阵 $K$ 中，删除任何一个行或列得到矩阵 $F$ ，那么 $M_{11} = F F^{T}$ ，其中 $M_{11}$ 表示 $L$ 删除第一行第一列后得到的余因子矩阵。

\det (M_{11}) = \sum_{S} \det (F_{S}) \det (F_{S}^{T}) = \sum_{S} \det {(F_{S})}^{2}

可以表示这个行列式给予生成树的数量。