在圖論中，矩陣樹定理（matrix tree theorem）或基爾霍夫定理（Kirchhoff theorem）是指圖的生成樹數量等於拉普拉斯矩陣的代數餘子式（所以可以在多項式時間內計算）。
若 G 有 n 個頂點，\lambda_1, \lambda_2, \dots, \lambda_{n-1} 是拉普拉斯矩陣的非零特徵值，則
: t(G)=\frac{1}{n} \lambda_1\lambda_2\cdots\lambda_{n-1}.
這個定理以古斯塔夫·基爾霍夫名字命名。這也是凱萊公式的推廣（若圖是完全圖）。
定義與定理敘述
設 G 是一個簡單的無向圖。G 的一個生成樹是 G 的一個子圖，它是一棵包含 G 所有頂點的樹。
G 的拉普拉斯矩陣 L 是一個 n × n 的矩陣（其中 n 為頂點數），定義為圖的度數矩陣 D（對角矩陣，對角線元素為各頂點的度數）與鄰接矩陣 A（若頂點 i 與 j 相鄰則 Aij = 1，否則為 0）之差：
: L = D - A
拉普拉斯矩陣 L 的一個代數餘子式是透過刪除 L 的某一行（如第 i 行）和某一列（如第 j 列），求剩下小矩陣的行列式，並乘以 (−1)i+j 得到的。
基爾霍夫定理指出：任意圖 G 的生成樹數量等於其拉普拉斯矩陣 L 的任意一個代數餘子式的值（特別地，這些代數餘子式的值全部相等）。
舉例
對於右圖的例子，首先求出拉普拉斯矩陣 L:
: L = \left[\begin{array}{rrrr}
2 & -1 & -1 & 0 \\
-1 & 3 & -1 & -1 \\
-1 & -1 & 3 & -1 \\
0 & -1 & -1 & 2
\end{array}\right].
隨後求出餘子式，也即刪除任何一個行和一個列，例如第一行和第一列：
: L^\ast =
\left[\begin{array}{rrr}
3 & -1 & -1 \\
-1 & 3 & -1 \\
-1 & -1 & 2
\end{array}\right].
則
\det(L^*) = 8 = t(G).
證明大綱
拉普拉斯矩陣有這個屬性：任何行或列的元素總和等於 0。因此，無論刪除什麼行或列，根據線性代數性質，透過行/列變換，所有的代數餘子式在數值和符號上完全相同。
下面利用柯西–比內公式證明餘子式矩陣 M_{11} 的行列式等於生成樹的數量：
- 設 n 為圖的頂點數，m 為邊數。定義圖的定向關聯矩陣（Oriented Incidence Matrix）E 為一個 n × m 的矩陣：若第 k 條邊連接頂點 i 和 j（且 i E_{ik} = 1，E_{jk} = -1，該列其餘元素為 0。
以先前的例子為例（n = 4, m = 5）：
: E = \left[ \begin{array}{rrrrr}
1 & 1 & 0 & 0 & 0 \\
-1 & 0 & 1 & 1 & 0 \\
0 & -1 & -1 & 0 & 1 \\
0 & 0 & 0 & -1 & -1
\end{array} \right] .
- 已知拉普拉斯矩陣可以分解為 L = EE^{\mathrm{T}}。
- 令 F 為刪除第一行後的矩陣 E（大小為 (n-1) \times m），則有 FF^{\mathrm{T}} = M_{11}。
- 根據柯西-比內公式，我們可以將行列式展開為：
: \det\left(M_{11}\right) = \sum_S \det\left(F_S\right)\det\left(F^{\mathrm{T}}_S\right) = \sum_S \det\left(F_S\right)^2
其中 S 遍歷集合 \{1, \dots, m\} 中所有大小為 n − 1 的子集，而 F_S 表示由矩陣 F 中索引在 S 中的列所構成的 (n-1) \times (n-1) 子矩陣。
每一個子集 S 都對應原圖中的 n − 1 條邊。可以證明：
- 如果這 n − 1 條邊在原圖中構成了一棵生成樹，則該子矩陣的行列式值 \det(F_S) = \pm 1，平方後為 1。
- 如果它們不構成生成樹（即含有迴路），則 \det(F_S) = 0。
這便完成了證明。
特殊情況與推廣
凱萊公式
凱萊公式是基爾霍夫定理的一個經典特例。完全圖 Kn 的拉普拉斯矩陣形式如下：
:
\begin{bmatrix}
n-1 & -1 & \cdots & -1 \\
-1 & n-1 & \cdots & -1 \\
\vdots & \vdots& \ddots & \vdots \\
-1 & -1 & \cdots & n-1 \\
\end{bmatrix}.
計算該矩陣的任意一個代數餘子式，其行列式結果均固定為 nn-2。這完美印證了完全圖包含 nn-2 棵標號生成樹的結論。
特徵值表述法
該定理也可以透過拉普拉斯矩陣的特徵值來表達。拉普拉斯矩陣的特徵值總是非負的，且必有一個為 0。
設圖 G 的特徵值按升序排列為 0 = λ0 ≤ λ1 ≤ λ2 ≤ ... ≤ λn-1，則其生成樹數量 t(G) 可以表達為所有非零特徵值乘積的 1/n：
: t(G) = \frac{1}{n} \lambda_1\lambda_2\cdots\lambda_{n-1}.
多重圖的基爾霍夫定理
基爾霍夫定理同樣適用於包含重邊的多重圖（Multigraphs），只需對矩陣 L 的定義做微調：
- 元素 Li,j（i ≠ j）等於 −m，其中 m 是頂點 i 和 j 之間的邊數；
- 在計算頂點度數時，排除所有的自環（Loops）。
生成樹的顯式枚舉
我們不僅可以計算生成樹的數量，還可以透過代數方法將它們逐一列舉出來：
給圖中的每條邊賦予一個不定元（變量），並讓修改後的拉普拉斯矩陣第 (i, j) 個元素在 i ≠ j 時為頂點 i 與 j 之間所有邊的變量之和的相反數，在 i = j 時為從頂點 i 出發的所有邊的變量之和。
此時，計算該矩陣任意代數餘子式所得到的行列式將是一個齊次多項式（稱為基爾霍夫多項式）。將該多項式展開並化簡後，其中的每一個單項式都唯一對應一棵生成樹（由該單項式包含的變量邊組成）。
擬陣拓展
在擬陣理論中，圖的生成樹構成了圖形擬陣（Graphic Matroid）的基。因此，基爾霍夫定理實際上提供了計算圖形擬陣中「基」的數量的方法。該方法還可以進一步推廣到計算正規擬陣（Regular Matroids）中基的數量。
有向多重圖的基爾霍夫定理
該定理還可以修正為計算有向多重圖中有向生成樹（又稱樹形圖，Oriented Spanning Trees）的數量。構造矩陣 Q 如下：
- 當 i ≠ j 時，元素 qi,j 等於 −m，其中 m 是從頂點 i 指向頂點 j 的有向邊數；
- 對角線元素 qi,i 等於頂點 i 的入度（Indegree）減去 i 處的自環數。
此時，以頂點 i 為根的有向生成樹的數量，等於從 Q 中刪去第 i 行和第 i 列後剩下子矩陣的行列式值。
計算含有 k 個連通分量的生成森林
基爾霍夫定理還能推廣到計數無權圖中含有 k 個連通分量的生成森林（Spanning Forests）。
給定一個擁有連通分量 F_1, \dots, F_k 的森林 F，定義其權重 w(F) = |V(F_1)| \cdot \dots \cdot |V(F_k)| 為各個分量頂點數的乘積。則所有 k 分量生成森林的權重之和滿足：
: \sum_F w(F) = q_k,
這裡的 q_k 恰好是多項式
: (x+\lambda_1) \dots (x+\lambda_{n-1}) x
中 x^k 項的係數。
參見
- 普呂弗序列
- 最小生成樹
閱讀
*
- .
- .
*
參考文獻
评论 (0)