矩阵树定理

在图论中，基尔霍夫定理（Kirchoff 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₁₁ 。

\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., , Undergraduate Texts in Mathematics 2nd, Springer, 2008
Maurer, Stephen B., , SIAM Journal on Applied Mathematics, 1976, 30 (1): 143–148, MR 0392635, doi:10.1137/0130017.
Tutte, W. T., , Cambridge University Press: 138, 2001, ISBN 978-0-521-79489-3.
Chaiken, S.; Kleitman, D., , Journal of Combinatorial Theory, Series A, 1978, 24 (3): 377–381, ISSN 0097-3165, doi:10.1016/0097-3165(78)90067-5

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.