矩陣樹定理

在圖論中，矩陣樹定理（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 的任意一個代數餘子式的值（特別地，這些代數餘子式的值全部相等）。

## 舉例

<image>

對於右圖的例子，首先求出拉普拉斯矩陣 $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 < j），則令 $E_{ik} = 1$，$E_{jk} = -1$，該列其餘元素為 0。

以先前的例子為例（n = 4, m = 5）：

$$E = \left[ \begin{array}{rrrrr} <pre> 1 & 1 & 0 & 0 & 0 \\ </pre> -1 & 0 & 1 & 1 & 0 \\ <pre> 0 & -1 & -1 & 0 & 1 \\ 0 & 0 & 0 & -1 & -1 </pre> \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} <pre> n-1 & -1 & \cdots & -1 \\ -1 & n-1 & \cdots & -1 \\ \vdots & \vdots& \ddots & \vdots \\ -1 & -1 & \cdots & n-1 \\ </pre> \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$ 項的係數。