跳轉到

05.2 圖的矩陣表示與連通性：鄰接矩陣與 Laplacian#

1. 前因：為什麼要把圖變成矩陣？#

Euler 1736 創立的圖論是「畫在紙上」的數學：頂點、邊、徒手推理。但 20 世紀的兩股力量迫使圖論數值化：

  1. 電腦誕生：圖必須以數字結構存入記憶體，矩陣是最自然的編碼。
  2. 譜線圖論（spectral graph theory）：1950 年代起，Collatz 與 Sinogowitz 等人發現圖的特徵值蘊含連通性、展開性（expansion）等 訊息，把線性代數與圖論焊接在一起。

歷史的巧合是：矩陣表示早在 1912 年就被用於 Kirchhoff 電路定律的分析， 而 Kirchhoff 1847 年的電網定理正是 Laplacian 矩陣行列式的最早應用—— 物理問題又一次驅動了數學工具。

2. 鄰接矩陣：連接關係的代數化身#

定義 2.1（鄰接矩陣）：設簡單圖 \(G\) 有頂點 \(v_1,\dots,v_n\) 。鄰接 矩陣 \(A \in \{0,1\}^{n \times n}\) 定義為

\[A_{ij} = \begin{cases} 1 & \text{若 } v_i \sim v_j \\ 0 & \text{否則}\end{cases}\]

無向圖的 \(A\) 是對稱的；有向圖一般不對稱。

定理 2.2（走步計數）： \(A^k\) 的 \((i,j)\) 元等於從 \(v_i\) 到 \(v_j\) 長度為 \(k\) 的走步（walk）數。

證明：對 \(k\) 歸納。 \(k=1\) 即定義。設 \(k\) 時成立，則

\[(A^{k+1})_{ij} = \sum_{m} (A^k)_{im} A_{mj} = \sum_{m} (\text{ $i \to m$ 的 $k$ 步數}) \cdot [\,m \sim j\,],\]

即「先走 \(k\) 步到 \(m\) ，再走一步到 \(j\) 」對每個中繼點 \(m\) 加總，正是 長度 \(k+1\) 的走步數。 \(\blacksquare\)

這條定理是矩陣化的第一個紅利：連通性變成矩陣冪的問題。

定義 2.3（連通）：若任意兩頂點間存在路徑，稱 \(G\) 連通。由定理 2.2， \(G\) 連通 \(\iff\) 對某 \(k \le n-1\) ， \(\sum_{k=0}^{n-1} A^k\) 的所有 非對角元皆為正。

3. Laplacian 矩陣：差分算子的離散化身#

定義 3.1（Laplacian）： \(L = D - A\) ，其中 \(D = \operatorname{diag} (d(v_1), \dots, d(v_n))\)。元素形式：

\[L_{ij} = \begin{cases} d(v_i) & i = j \\ -1 & i \sim j \\ 0 & \text{否則}\end{cases}\]

性質 3.2： - \(L\) 是半正定的：對任意 \(\mathbf{x} \in \mathbb{R}^n\) ， $\(\mathbf{x}^\top L \mathbf{x} = \sum_{\{i,j\} \in E} (x_i - x_j)^2 \ge 0.\)$ - \(L \mathbf{1} = \mathbf{0}\) ，故 \(0\) 恆為特徵值。 - \(L\) 的列和皆為 \(0\) 。

二次型 \(\sum (x_i - x_j)^2\) 的直觀：把 \(x_i\) 想成頂點 \(i\) 的「電位」， Laplacian 衡量相鄰頂點間的落差總能量——這正是 Kirchhoff 1847 年分析 電阻網路的角度。

4. 定理與證明：矩陣樹定理與連通性的譜判準#

定理 4.1（Matrix-Tree Theorem, Kirchhoff 1847）：連通圖 \(G\) 的 生成樹數量 \(\tau(G)\) 等於 \(L\) 的任一 \(n-1\) 階主子式：

\[\tau(G) = \det(L^{(i)}), \quad \text{其中 } L^{(i)} \text{ 為刪去第 } i \text{ 列與行的子矩陣。}\]

證明綱要：對 \(L\) 的特徵值 $\lambda_1 = 0 \le \lambda_2 \le \cdots \le \lambda_n \(，可證\) \det(L^{(i)}) = \dfrac{\lambda_2 \cdots \lambda_n}{n}$。 另方面，對每條邊指定方向後， \(L\) 可寫成 \(B B^\top\) （ \(B\) 為關聯矩陣）， Cauchy–Binet 公式將 \(\det(L^{(i)})\) 展開為所有「 \(n-1\) 條邊選擇」的 行列式平方和；再證每棵生成樹恰好貢獻 \(1\) ，非樹的邊集貢獻 \(0\) （其 子矩陣列線性相關）。兩邊合起來得 \(\tau(G)\) 。 \(\blacksquare\)

定理 4.2（譜連通判準）： \(G\) 連通 \(\iff\) \(L\) 的第二小特徵值 \(\lambda_2 > 0\) （此值稱為代數連通度，Fiedler 1973）。

證明： \(0\) 特徵值的重數等於 \(G\) 的連通分量數。若 \(G\) 有 \(c\) 個 分量，每個分量的指示向量 \(\mathbf{1}_{C}\) 都落在 \(\ker L\) 中且彼此 線性無關，故 \(\dim \ker L \ge c\) ；反之對 \(\ker L\) 的任一向量 \(\mathbf{x}\) ，由性質 3.2 的二次型知每個分量內 \(x_i\) 皆相等，故 \(\ker L\) 恰由 \(c\) 個分量常值向量張成。 \(\blacksquare\)

5. 範例與 Python 驗證#

例 5.1：路徑圖 \(P_3\) （ \(v_1 - v_2 - v_3\) ）。

import numpy as np
from itertools import combinations

def laplacian_matrix(n, edges):
    L = np.zeros((n, n))
    for u, v in edges:
        L[u-1, v-1] -= 1
        L[v-1, u-1] -= 1
        L[u-1, u-1] += 1
        L[v-1, v-1] += 1
    return L

def count_spanning_trees(n, edges):
    """Kirchhoff 定理：任一主子式的行列式"""
    L = laplacian_matrix(n, edges)
    idx = list(range(1, n))          # 刪去第 0 列/行
    return round(np.linalg.det(L[np.ix_(idx, idx)]))

# P3：一棵生成樹（就是自己）
L = laplacian_matrix(3, [(1,2), (2,3)])
print(np.linalg.eigvalsh(L))          # [0, 1, 3]
print(count_spanning_trees(3, [(1,2),(2,3)]))   # 1

# 三角形 K3：三棵生成樹（刪任一邊）
print(count_spanning_trees(3, [(1,2),(2,3),(1,3)]))  # 3

# 連通性：λ2 > 0？
def is_connected(n, edges):
    eig = np.linalg.eigvalsh(laplacian_matrix(n, edges))
    return eig[1] > 1e-9
print(is_connected(3, [(1,2),(2,3)]))          # True
print(is_connected(4, [(1,2),(3,4)]))          # False

輸出驗證了定理 4.2： \(P_3\) 的特徵值為 \(\{0,1,3\}\) ， \(\lambda_2 = 1 > 0\) ； 而兩條孤立邊組成的圖 \(\lambda_2 = 0\) ，不連通。

例 5.2（走步計數）： \(K_3\) 的鄰接矩陣平方的對角元皆為 \(2\) ，即每個 頂點各有 \(2\) 條長度 \(2\) 的閉走步（去鄰居再回來）。

6. 前因後果：矩陣視角如何重塑後續章節#

三個深遠的後果：

  1. 生成樹計數變成線性代數：Cayley 1889 年證明 \(K_n\) 有 \(n^{n-2}\) 棵生成樹，用矩陣樹定理一行就算出 \(\det\) ，這是 06.1 的 起點。
  2. 隨機漫遊：歸一化 Laplacian 與轉移矩陣的譜互相支配，Google PageRank 本質上是圖譜問題。
  3. 分群與圖分割：Fiedler 向量（ \(\lambda_2\) 對應的特徵向量）給出 把圖切成兩半的自然切法，譜分群至今是機器學習標準工具。

7. 章末小結#

  1. 鄰接矩陣 \(A\) 編碼連接， \((A^k)_{ij}\) 計數走步；Laplacian \(L = D - A\) 編碼「局部落差」，是離散差分算子。
  2. 矩陣樹定理（Kirchhoff）把生成樹計數化為行列式； \(\lambda_2 > 0\) 等價於連通， \(\lambda_2\) 的大小衡量連通強度（Fiedler）。
  3. 矩陣化不只是儲存技巧：它把圖論接到線性代數的龐大工具箱，譜方法 至今活躍於網路科學與機器學習。

下一步：有了連通與矩陣工具，我們回到周遊問題的另一端——Euler 要求走過每條邊，而 Hamilton 1859 年的 Icosian game 要求造訪每個 頂點：看似相近的兩個問題，命運卻天差地遠（05.3）。