相鄰的點不能同色，最少要幾種顏色？從排課到暫存器分配都是它

難度定位

• \(k=2\)：等於判斷二部圖，BFS 一次 \(O(V+E)\) 搞定。

• \(k\geq 3\)：3-Coloring 是 NP-Complete（由 3-SAT 歸約），又一個「2 到 3 的懸崖」。

• 近似也難：除非 P=NP，不存在能保證 \(\chi(G)^{1-\varepsilon}\) 倍以內的多項式近似演算法。著色是出了名地難近似。

• 特例是綠洲：平面圖 \(\chi \leq 4\)（四色定理）、區間圖可貪心求得精確色數、樹 \(\chi\leq 2\)。

幾個基本事實

演算法一：回溯 \(k\)-著色

逐點嘗試 \(1..k\) 每種顏色，只要與已著色鄰居衝突就跳過；全部點著完即成功：

bool dfs(int u) {
    if (u == n) return true;                 // 全著完
    for (int c = 0; c < k; ++c) {
        if (!feasible(u, c)) continue;       // 剪枝：鄰居已用 c
        color[u] = c;
        if (dfs(u + 1)) return true;
        color[u] = -1;                       // 回溯
    }
    return false;
}

最壞 \(O(k^n)\)，但衝突剪枝讓實際樹小得多。求色數：\(k\) 從 1 開始遞增，第一個可行的 \(k\) 就是 \(\chi(G)\)（因為可行性對 \(k\) 單調）。

演算法二：貪婪著色（Welsh–Powell）

按度數遞減排序，逐點塗上「鄰居沒用過的最小顏色」：

\[T = O(V^2 + E) \qquad \text{保證用色} \leq \Delta(G)+1\]

快但不保證最優；甚至存在讓貪心用到 \(\Omega(n)\) 色而 \(\chi=2\) 的壞順序（皇冠圖）。實務上它是回溯法的好前鋒：先跑貪心拿到上界 \(k_0\)，回溯只需測 \(k < k_0\)。

手算範例：C5 五邊環

點 \(0\!-\!1\!-\!2\!-\!3\!-\!4\!-\!0\)。貪心（度數全為 2，按編號）：\(0\to\) 紅、\(1\to\) 藍、\(2\to\) 紅、\(3\to\) 藍、\(4\to\) ？——鄰居 3（藍）與 0（紅）都衝突，開第三色。\(\chi(C_5)=3\)：奇環無法二著色（沿環交替塗色，環長為奇數時首尾必撞）。

完整 C++ 程式

包含：回溯 \(k\)-著色（含著色方案輸出）、遞增法求色數、Welsh–Powell 貪心、K3/C4/C5/Petersen 與排課實例。編譯：

g++ -std=c++17 -O2 -Wall -Wextra -o graph_coloring graph_coloring.cpp

執行結果與解讀

=== Example 1: triangle K3 ===
K3: chromatic number = 3 | greedy used = 3
  optimal coloring: v0=c0 v1=c1 v2=c2

=== Example 2: even cycle C4 (bipartite) vs odd cycle C5 ===
C4: chromatic number = 2 | greedy used = 2
  optimal coloring: v0=c0 v1=c1 v2=c0 v3=c1
C5: chromatic number = 3 | greedy used = 3
  optimal coloring: v0=c0 v1=c1 v2=c0 v3=c1 v4=c2

=== Example 3: Petersen graph ===
Petersen: chromatic number = 3 | greedy used = 3
  optimal coloring: v0=c0 v1=c1 v2=c0 v3=c1 v4=c2 v5=c1 v6=c0 v7=c2 v8=c2 v9=c1

=== Example 4: exam scheduling as coloring ===
6 courses, 8 conflicts -> minimum time slots = 3
  slot 0: Calculus    slot 1: LinAlg     slot 2: Physics
  slot 0: Chem        slot 1: Prog       slot 2: English

實務應用

• 編譯器暫存器分配：變數為點、生命週期重疊為邊，\(k\) 個暫存器 = \(k\)-著色；塗不進去的變數 spill 到記憶體。Chaitin (1981) 的經典演算法就是圖著色。

• 排課排考：本篇 Example 4 的直接放大版，大學排考系統的核心。

• 無線電頻譜分配：地理相鄰的基地台不能用同頻段——頻段 = 顏色。

• 數獨：81 個格子的圖著色（9 色），行、列、宮相鄰。

• 製程排程：互斥資源的任務分批，每批一色。

練習題

1. 手算輪圖 \(W_5\)（C5 加中心點連向全部）的色數。

2. 實作「對稱破除」：第 \(u\) 個點只准用顏色 \(0..\min(u, k-1)\)。實測 Petersen 圖的節點數變化。

3. 構造一個圖與一種點順序，讓貪心用 4 色而 \(\chi=2\)（提示：皇冠圖 crown graph）。

4. 把回溯的點順序改成「度數遞減」，比較 Petersen 圖上的節點數。

5. 挑戰：實作 DSATUR（動態飽和度優先）貪心，跟 Welsh–Powell 在隨機圖上比誰用色少。

小結

延伸閱讀：四色定理（Appel & Haken 1976，第一個電腦輔助證明）；Brooks 定理；Chaitin (1981) Register Allocation via Coloring；Lewis A Guide to Graph Colouring。