圖論第10章 - 考前複習重點整理

一、基本概念與術語

1.1 圖的基本元素

頂點 (Vertex/Vertices)
圖中的點，通常用字母表示（如 a, b, c 或 v₁, v₂, v₃）
邊 (Edge)
連接兩個頂點的線，可以是有向或無向的
a b c d

簡單無向圖範例

1.2 度數 (Degree)

無向圖的度數：一個頂點連接的邊數
記號：deg(v) 或 d(v)
有向圖的度數：
  • 入度 (In-degree)：指向該頂點的邊數，記為 deg⁻(v)
  • 出度 (Out-degree)：從該頂點出發的邊數，記為 deg⁺(v)
握手定理：Σ deg(v) = 2|E|
（所有頂點度數總和 = 邊數的2倍）

二、圖的類型

圖的類型 英文 特徵 範例
簡單圖 Simple Graph 無向、無迴圈、無多重邊 一般的朋友關係圖
多重圖 Multigraph 允許多重邊，但無迴圈 城市間的多條道路
偽圖 Pseudograph 允許多重邊和迴圈 電路圖
有向圖 Directed Graph (Digraph) 邊有方向 網頁連結、食物鏈
有向多重圖 Directed Multigraph 有向且允許多重邊 複雜的交通網絡

2.1 特殊頂點

孤立頂點 (Isolated Vertex)
度數為 0 的頂點（沒有連接任何邊）
懸掛頂點 (Pendant Vertex)
度數為 1 的頂點（只連接一條邊）

三、特殊圖形

3.1 完全圖 (Complete Graph) - Kn

n個頂點的完全圖，每兩個不同頂點之間都有邊
頂點數：n
邊數：n(n-1)/2
每個頂點度數：n-1

K₄ 完全圖

3.2 環圖 (Cycle Graph) - Cn

n個頂點形成一個環
頂點數：n
邊數：n
每個頂點度數：2

3.3 輪圖 (Wheel Graph) - Wn

一個中心頂點連接到環上的n個頂點
頂點數：n+1
邊數：2n
中心頂點度數：n
周圍頂點度數：3

3.4 完全二部圖 (Complete Bipartite Graph) - Km,n

頂點分成兩組（m個和n個），每組內部沒有邊，但不同組的頂點都有邊相連
頂點數：m+n
邊數：mn
第一組頂點度數：n
第二組頂點度數：m
K₃,₃ 是判斷平面圖的重要圖形之一！

四、路徑與連通性

4.1 路徑 (Path)

路徑：頂點序列 v₁, v₂, ..., vₙ，其中每個連續的頂點對都有邊相連
路徑長度：路徑中邊的數量（= 頂點數 - 1）
簡單路徑 (Simple Path)：沒有重複頂點的路徑
迴路/環路 (Circuit/Cycle)：起點和終點相同的路徑

4.2 連通性 (Connectivity)

類型 無向圖 有向圖
連通 任意兩頂點間都有路徑 -
強連通 - 任意兩頂點間都有雙向路徑
弱連通 - 忽略方向後是連通的
割點 (Cut Vertex)：移除該頂點（及其相關邊）後，圖變得不連通

五、歐拉路徑與迴路

5.1 歐拉路徑與歐拉迴路 (Euler Path & Circuit)

歐拉路徑：經過每條邊恰好一次的路徑
歐拉迴路：經過每條邊恰好一次且回到起點的迴路
判定定理（無向圖）：
  • 有歐拉迴路 ⟺ 連通且所有頂點度數為偶數
  • 有歐拉路徑 ⟺ 連通且恰好有0個或2個奇度頂點
一筆畫問題：能否不重複地畫完所有邊？
→ 轉換為尋找歐拉路徑的問題

六、哈密頓路徑與迴路

6.1 哈密頓路徑與迴路 (Hamilton Path & Circuit)

哈密頓路徑：經過每個頂點恰好一次的路徑
哈密頓迴路：經過每個頂點恰好一次且回到起點的迴路
注意：沒有簡單的判定定理！
需要具體分析或嘗試構造
檢查技巧：
  • 如果有度數為1的頂點，則沒有哈密頓迴路
  • 如果移除k個頂點後有超過k個連通分量，則沒有哈密頓迴路

七、二部圖（想像成兩邊站隊）

7.1 二部圖 (Bipartite Graph)

簡單理解：想像學生分成兩隊（紅隊和藍隊），規則是：
  • 同隊的人不能手牽手（同組內沒有邊）
  • 只能和對面隊伍的人牽手（邊只連接不同組）
紅隊 藍隊 A B C D E

二部圖範例：K₃,₂

重要判斷法則：如果圖中有奇數個頂點形成的環（如三角形），就不是二部圖！
為什麼？因為奇數個人圍成圈，無法分成兩隊讓相鄰的人在不同隊。
實際例子：
  • ✓ 四邊形（4個頂點的環）：可以分兩隊 → 是二部圖
  • ✗ 三角形（3個頂點的環）：無法分兩隊 → 不是二部圖
  • ✗ 五邊形（5個頂點的環）：無法分兩隊 → 不是二部圖
著色判斷法（最簡單的方法）：
  1. 隨便選一個頂點，塗紅色
  2. 它的所有鄰居都塗藍色
  3. 藍色頂點的鄰居都塗紅色
  4. 繼續塗色...
  5. 如果發現兩個相鄰頂點同色 → 不是二部圖！

八、平面圖（能否畫在紙上不交叉）

8.1 平面圖 (Planar Graph)

簡單理解：就是問你能不能把這個圖畫在紙上，讓所有的線都不交叉（除了在頂點處）
K₅（無法畫成不交叉） 1 2 3 4 5 K₄（可以畫成不交叉） A B C D
歐拉公式的由來（連通平面圖）：
v - e + r = 2

怎麼理解這個公式？
  1. v = 頂點數（vertices）
  2. e = 邊數（edges）
  3. r = 區域數（regions）- 包括外部的無限大區域！
實例：正方形
  • v = 4（四個角）
  • e = 4（四條邊）
  • r = 2（內部1個 + 外部1個）
  • 驗證：4 - 4 + 2 = 2 ✓
為什麼永遠等於2？
歐拉發現這是平面圖的固定性質。你可以想像從一個點開始：
  • 一個點：v=1, e=0, r=1 → 1-0+1=2 ✓
  • 加一個點和一條邊：v+1, e+1, r不變 → 還是2
  • 加一條邊形成環：v不變, e+1, r+1 → 還是2
兩個禁忌圖形（記住它們！）：
  • K₅：5個頂點的完全圖（每兩點都有邊）
  • K₃,₃：3對3的完全二部圖（像是3個房子連到3個工廠）
如果你的圖包含這兩個圖形之一（或它們的變形），就不是平面圖！
快速判斷技巧：
對於簡單平面圖，邊數有上限：e ≤ 3v - 6（當v≥3）

例如：5個頂點的圖，最多有 3×5-6 = 9 條邊
如果超過9條邊，一定不是平面圖！

九、圖的表示方法

9.1 鄰接表 (Adjacency List)

對於圖 a-b-c-d（正方形）：
a: b, d
b: a, c
c: b, d
d: a, c

9.2 鄰接矩陣 (Adjacency Matrix)

同樣的正方形圖：
  a b c d
a[0 1 0 1]
b[1 0 1 0]
c[0 1 0 1]
d[1 0 1 0]
矩陣性質：
  • 無向圖的鄰接矩陣是對稱的
  • A^n 的 [i,j] 元素 = 從頂點i到j長度為n的路徑數

十、同構圖（長得一樣的圖）

10.1 同構 (Isomorphism)

簡單理解：兩個圖是同構的 = 它們本質上是同一個圖，只是畫法不同或頂點名稱不同

想像你有一個用橡皮筋和珠子做的圖，你可以移動珠子的位置，但不能剪斷或增加橡皮筋。 如果能變形成另一個圖，它們就是同構的！
圖 G 1 2 3 4 ≅ 圖 H A B C D

這兩個圖是同構的！（都是4個頂點的環）

判斷同構的步驟（像偵探找線索）：
  1. 數頂點：頂點數量要相同
  2. 數邊：邊的數量要相同
  3. 查度數序列：
    • 列出每個頂點的度數
    • 從小到大排序
    • 兩個圖的序列要相同
  4. 找特殊結構：
    • 有幾個三角形？
    • 有幾個四邊形？
    • 最長的環是幾個頂點？
  5. 嘗試對應：試著找出頂點的對應關係
實例判斷：
檢查項目 圖 G 圖 H 結果
頂點數 4 4 ✓ 相同
邊數 4 4 ✓ 相同
度數序列 [2,2,2,2] [2,2,2,2] ✓ 相同
結構 一個4-環 一個4-環 ✓ 相同

結論：同構！ 對應關係：1→A, 2→B, 3→C, 4→D

注意：如果任何一個檢查項目不同，就一定不同構！ 但即使所有項目都相同，也不一定同構（需要進一步驗證對應關係）。

考試重點提醒

必背公式與定理

  1. 握手定理：Σ deg(v) = 2|E|
  2. 歐拉迴路存在條件：所有頂點度數為偶數
  3. 歐拉路徑存在條件：恰好0或2個奇度頂點
  4. 二部圖判定：不含奇數環
  5. 歐拉公式：v - e + r = 2
  6. 平面圖邊數限制：e ≤ 3v - 6

解題技巧