跳轉到

07.4 圖論初步#

本節目標#

  • 建立圖（graph）的直覺，學會用 adjacency matrix 表示圖。
  • 用 SymPy 矩陣操作圖，理解「矩陣乘法 = 路徑計數」的意義。
  • 用程式驗證 Euler path 的存在條件。
  • 認識組合計數在圖上的應用（生成樹數目的直覺），並實驗：建立六都市連通圖並數路徑。

一、圖的直覺與 adjacency matrix#

圖由頂點（vertex）與邊（edge）組成，用來描述「哪些東西之間有連結」：城市與公路、人與友誼、網頁與超連結。

adjacency matrix \(A\) ： \(n\) 個頂點的圖用一個 \(n \times n\) 的 0-1 矩陣表示，若頂點 \(i\) 與 \(j\) 有邊相連，則 \(A_{ij} = 1\) 。無向圖的 \(A\) 是對稱矩陣。

例如三個頂點 \(1-2\) 、 \(2-3\) 相連的圖：

\[ A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} \]
from sympy import Matrix, eye, zeros

A = Matrix([[0, 1, 0],
            [1, 0, 1],
            [0, 1, 0]])
print(A.is_symmetric())   # True
print(A[0, 2])            # 0：頂點 1 與 3 不相連

二、矩陣乘法的意義：路徑計數#

圖論最美的結果之一：

\[ (A^m)_{ij} = \text{從頂點 } i \text{ 到 } j \text{ 恰走 } m \text{ 步的路徑數} \]

原因： \((A^2)_{ij} = \sum_{t} A_{it} A_{tj}\) ，正好枚舉「先走一步到 \(t\) 、再走一步到 \(j\) 」的所有中間點 \(t\) 。依數學歸納法可推廣到任意 \(m\) 。

用例子驗證：上面的三頂點圖， \(A^2\) 的 \((1,3)\) 元素應為 1（路徑 \(1 \to 2 \to 3\) ）：

A2 = A**2
print(A2)
# Matrix([[1, 0, 1],
#         [0, 2, 0],
#         [1, 0, 1]])
print(A2[0, 2])   # 1：1 到 3 走兩步恰有一條路

A3 = A**3
print(A3[0, 2])   # 0：1 到 3 走三步沒有路（會走回頭）
print(A3[0, 0])   # 2：1 走三步回到自己的路有兩條（1-2-1-2？不，是 1-2-3-2 與 1-2-1-2 需重畫圖檢查）

自環數 \((A^2)_{ii}\) 等於頂點 \(i\) 的度數（degree）——與它相連的邊數。這也是一個矩陣語言翻譯圖論概念的例子：

print([A2[i, i] for i in range(3)])   # [1, 2, 1]，頂點 2 的度數是 2

三、Euler path 條件的驗證實驗#

Euler path：走過圖中每一條邊恰好一次的路徑。Euler circuit（一筆畫回到起點）則要求起點也是終點。

Euler 的經典定理：

  • 圖連通且恰有 0 或 2 個奇度數頂點時，存在 Euler path；
  • 0 個奇度數頂點時存在 Euler circuit（可以一筆畫回原點）。

七橋問題就是因為四個頂點度數都是奇數而無解。寫一個檢查器驗證：

def degrees(A):
    """無向圖：度數 = A^2 對角線"""
    return [A**2[i, i] for i in range(A.shape[0])]

def has_euler_path(A):
    """檢查連通性（用所有頂點兩兩有路徑；此例以 A 的冪判斷）與奇度數頂點個數"""
    n = A.shape[0]
    # 連通性：所有非對角元素在 A + A^2 + ... + A^(n-1) 中不為 0
    reach = zeros(n)
    P = eye(n)
    for _ in range(1, n):
        P = P * A
        reach = reach + P
    connected = all(reach[i, j] + reach[j, i] != 0
                    for i in range(n) for j in range(i + 1, n))
    odd = sum(1 for d in degrees(A) if d % 2 == 1)
    return connected and odd in (0, 2)

# 測試 1：三頂點路徑圖 1-2-3，度數 [1,2,1]，奇度數 2 個 -> 有 Euler path
print(has_euler_path(A))          # True

# 測試 2：三角形，度數 [2,2,2]，奇度數 0 個 -> 有 Euler circuit
T = Matrix([[0, 1, 1],
            [1, 0, 1],
            [1, 1, 0]])
print(has_euler_path(T))          # True

# 測試 3：星形圖（中心連三葉），度數 [1,1,1,3]，奇度數 4 個 -> 無 Euler path
S = Matrix([[0, 1, 0, 0],
            [1, 0, 1, 1],
            [0, 1, 0, 0],
            [0, 1, 0, 0]])
print(has_euler_path(S))          # False

用 Euler path 的定義人工驗證測試 1： \(1 \to 2 \to 3\) 走完兩條邊各一次，確實是 Euler path。

四、組合計數在圖上的應用：數生成樹的直覺#

生成樹（spanning tree）：保留原圖所有頂點、邊數恰為 \(n-1\) 且連通的子圖。一個連通圖可能有非常多棵生成樹——這是組合計數問題。

經典結果（Matrix-Tree 定理的直覺版）：**完全圖 \(K_n\) **（任兩點都有邊）的生成樹數目是

\[ n^{n-2} \quad \text{（Cayley 公式）} \]

用小圖驗證： \(K_3\) 有 \(3^1 = 3\) 棵生成樹（三條邊去掉任何一條）：

# K3：3 條邊，生成樹需 2 條邊且連通 -> 3 種
print(3**(3 - 2))   # 3

# K4：理論值 4^2 = 16，可以用暴力枚舉驗證
K4 = Matrix([[0, 1, 1, 1],
             [1, 0, 1, 1],
             [1, 1, 0, 1],
             [1, 1, 1, 0]])
edges = [(i, j) for i in range(4) for j in range(i + 1, 4)]
from itertools import combinations

def connected(n, chosen_edges):
    reach = eye(n)
    P = eye(n)
    for _ in range(n - 1):
        B = zeros(n)
        for i, j in chosen_edges:
            B[i, j] = B[j, i] = 1
        P = P * B
        reach = reach + P
    return all(reach[i, j] > 0 for i in range(n) for j in range(n) if i != j)

count = sum(1 for c in combinations(edges, 3) if connected(4, c))
print(count)                 # 16
print(4**(4 - 2))            # 16，Cayley 公式吻合

另一個組合計數視角：完全圖的邊數是 \(\binom{n}{2}\) ——「任兩點連一條邊」就是從 \(n\) 點中選 2 點：

from sympy import binomial
print(binomial(5, 2))    # 10 條邊

五、動手實驗：六都市連通圖並數路徑#

建立六都市的公路連通圖（無向），並用矩陣冪數路徑：

cities = ['台北', '桃園', '台中', '嘉義', '台南', '高雄']
# 邊：台北-桃園, 台北-台中, 桃園-台中, 台中-嘉義, 台中-台南, 嘉義-台南, 台南-高雄
edges = [(0, 1), (0, 2), (1, 2), (2, 3), (2, 4), (3, 4), (4, 5)]

C = zeros(6)
for i, j in edges:
    C[i, j] = C[j, i] = 1
print(C)

# 數路徑：台北到高雄走 2 步、3 步、4 步各有幾條
P2 = C**2
P3 = C**3
P4 = C**4
print('台北->高雄 2 步路徑數:', P2[0, 5])   # 0
print('台北->高雄 3 步路徑數:', P3[0, 5])
print('台北->高雄 4 步路徑數:', P4[0, 5])

列出台北到高雄 4 步的所有路徑（人工對照矩陣結果）：

def all_paths(cur, target, visited, path):
    if cur == target and len(path) - 1 == 4:
        print(' -> '.join(cities[v] for v in path))
        return
    if len(path) - 1 > 4:
        return
    for nb in range(6):
        if C[cur, nb] == 1 and nb not in path or (nb == target and C[cur, nb] == 1):
            all_paths(nb, target, visited, path + [nb])

all_paths(0, 5, set(), [0])

實驗 2：用 Euler 條件檢查這個都市圖：

print([C**2[i, i] for i in range(6)])
# 度數：台北 2、桃園 2、台中 4、嘉義 2、台南 3、高雄 1
# 奇度數頂點有 2 個（台南、高雄）-> 存在 Euler path，起訖點正是台南與高雄！

實驗 3：把圖加密一點——若新闢「台北-台南」高速道路，路徑數怎麼變？

C2 = C.copy()
C2[0, 4] = C2[4, 0] = 1
print('新增道路後台北->高雄 3 步路徑數:', (C2**3)[0, 5])

觀察重點： 1. adjacency matrix 把圖論問題翻譯成線性代數；矩陣乘冪自動「枚舉」所有路徑。 2. 度數藏在 \(A^2\) 的對角線，Euler 條件只需數對角線上的奇數。 3. 新增一條邊會以組合的方式增加大量路徑——這正是「連通性」的價值。

小結與練習#

本節我們學會了： - 用 adjacency matrix 表示圖，並理解 \((A^m)_{ij}\) 是 \(i\) 到 \(j\) 的 \(m\) 步路徑數。 - Euler path 條件：連通且奇度數頂點恰 0 或 2 個。 - 生成樹計數的直覺與 Cayley 公式 \(n^{n-2}\) （完全圖）。 - 用 SymPy 矩陣對六都市圖做路徑計數。

練習： 1. 畫出 \(K_4\) 的 adjacency matrix，驗證 \((A^3)_{ii} = 6\) 對每個頂點成立（每點有 6 條 3 步迴路）。 2. 構造一個連通但沒有 Euler path 的 4 頂點圖，用本節的 has_euler_path 驗證。 3. 對六都市圖計算 \(C + C^2 + C^3\) ，檢查是否所有頂點對都可達（連通性驗證）。 4. 用 Matrix-Tree 定理的完整版（刪去度數矩陣與 adjacency 的差的任一餘子式的行列式）計算六都市圖的生成樹數目，並與暴力枚舉比較。