矩阵树定理

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

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

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

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

举例

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

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={\begin{bmatrix}1&1&0&0&0\\-1&0&1&1&0\\0&-1&-1&0&1\\0&0&0&-1&-1\\\end{bmatrix}}.$

完全图 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-² 。再说L的所有特征值是n，而且L只有n-1个特征向量。所以生成树的总数又是 n^n-² 。

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

若K是接续矩阵，L = KK^T。在矩阵K中，删除任何一个行或列得到矩阵F。设 FF^T = M₁₁ 。

使用柯西奈式^[1]

\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

^ Graphs, Matrices, Isomorphism. math.fau.edu. [2020-02-14]. （原始内容存档于2009-03-04）.