矩陣樹定理

在圖論中，矩陣樹定理（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