矩阵树定理

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

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

$t(G)={\frac {1}{n}}\lambda _{1}\lambda _{2}\cdots \lambda _{n-1}.$

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

举例

L是这个钻石图的拉氏矩阵

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

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

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

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

则

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

凯莱公式

完全图 K_n 的调和矩阵是

${\begin{bmatrix}n-1&-1&\cdots &-1\\-1&n-1&\cdots &-1\\\vdots &\vdots &\ddots &\vdots \\-1&-1&\cdots &n-1\\\end{bmatrix}}.$

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

证明大纲

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

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

使用柯西-比内公式

$\det \left(M_{11}\right)=\sum _{S}\det \left(F_{S}\right)\det \left(F_{S}^{T}\right)=\sum _{S}\det \left(F_{S}\right)^{2}$

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

参见

• 普吕弗序列
• 最小生成树

阅读

• Harris, John M.; Hirst, Jeffry L.; Mossinghoff, Michael J., Combinatorics and Graph Theory, Undergraduate Texts in Mathematics 2nd, Springer, 2008 
• Maurer, Stephen B., Matrix generalizations of some theorems on trees, cycles and cocycles in graphs, SIAM Journal on Applied Mathematics, 1976, 30 (1): 143–148, MR 0392635, doi:10.1137/0130017 .
• Tutte, W. T., Graph Theory, Cambridge University Press: 138, 2001, ISBN 978-0-521-79489-3 .
• Chaiken, S.; Kleitman, D., Matrix Tree Theorems, Journal of Combinatorial Theory, Series A, 1978, 24 (3): 377–381, ISSN 0097-3165, doi:10.1016/0097-3165(78)90067-5