矩陣樹定理

在圖論中，矩陣樹定理（matrix tree theorem）或基爾霍夫定理（Kirchhoff theorem）是指圖的生成樹數量等於調和矩陣的餘子式（所以可以在多項式時間內計算）。

若 G 有 n 個頂點，λ₁, λ₂, ..., λ_n-1 是拉普拉斯矩陣的非零特徵值，則

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

這個定理以古斯塔夫·基爾霍夫名字命名。 這也是凱萊公式的推廣（若圖是完全圖）。

舉例

L是這個鑽石圖的拉氏矩陣

對於右圖的例子，首先求出調和矩陣 ${\displaystyle Q}$:

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

隨後求出餘子式，也即刪除任何一個行和一個列，例如第一行和第一列：

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

則

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

凱萊公式

完全圖 K_n 的調和矩陣是

${\displaystyle {\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。所以，無論刪除什麼行或列，${\displaystyle \det(L^{*})}$都是不變的。或者說L的任何餘因子有同樣的行列式。

若${\displaystyle K}$是接續矩陣，則拉普拉斯矩陣 ${\displaystyle L=KK^{T}}$。在矩陣${\displaystyle K}$中，刪除任何一個行或列得到矩陣${\displaystyle F}$，那麼${\displaystyle M_{11}=FF^{T}}$，其中 ${\displaystyle M_{11}}$ 表示 ${\displaystyle L}$ 刪除第一行第一列後得到的余因子矩陣。

使用柯西-比內公式^[1]

${\displaystyle \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