跳轉到

5.3 圖著色與頂點覆蓋#

概念說明#

圖著色（Graph Coloring）：給定無向圖 G 與整數 k，問能否用 k 種顏色為每個頂點上色，使得任何相鄰的兩個頂點顏色不同。能使用 k 種顏色著色時，稱圖是「k-可著色」的。判斷一張圖是否 2-可著色很簡單（等價於判斷是否為二分圖，用 BFS 即可線性時間解決）；但 k ≥ 3 時問題瞬間變成 NP-complete——這是「從特例到一般、從容易到困難」的經典案例。

圖著色的應用非常具體：課表安排（同一時段不能有衝突的課）、頻譜分配（相鄰基地台不能用同一頻率）、暫存器分配（同時存活的變數不能共用同一暫存器，這是編譯器的核心步驟之一）。

頂點覆蓋（Vertex Cover）：給定圖 G 與整數 k，問能否選出至多 k 個頂點，使得圖中每一條邊都至少有一端點被選中。直觀地說，就是選一批「守衛」站崗，讓每條路都被盯到。頂點覆蓋是 NP-complete 的，且與獨立集、集團問題互為補數關係：I 是獨立集 ⟺ V \ I 是頂點覆蓋，因此三個問題的難度完全等價。

頂點覆蓋的應用：網路監控（最少監視器覆蓋所有鏈路）、疫苗接種策略（最少接種者阻斷所有傳染邊）、社交網路中選最少意見領袖覆蓋所有連結。

演算法步驟#

圖著色的回溯解法：

  1. 將頂點依度數由大到小排序（度數大的頂點限制多，先決定能提早剪枝）。
  2. 依序處理每個頂點，嘗試使用現有顏色中「不與已著色鄰居衝突」的顏色。
  3. 若現有顏色都不行且尚未超過 k 種，才開新顏色。
  4. 若某頂點在 k 種顏色下無一可用，回溯到上一個頂點換色。
  5. 所有頂點成功著色即回報可行。

頂點覆蓋的 2-近似貪婪解法（詳見 8.1 節）：

  1. 只要圖中還有邊 (u, v)：把 u 與 v 都加入覆蓋集合，並刪除所有與 u、v 相連的邊。
  2. 重複直到沒有邊。結果保證不超過最佳解的 2 倍。

Python 程式碼範例#

def graph_color_backtrack(n, edges, k):
    """回溯法判斷 n 個頂點、邊集 edges 是否 k-可著色"""
    adj = [set() for _ in range(n)]
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)
    order = sorted(range(n), key=lambda v: -len(adj[v]))
    color = [-1] * n

    def feasible(v, c):
        return all(color[u] != c for u in adj[v])

    def solve(idx):
        if idx == n:
            return True
        v = order[idx]
        for c in range(min(k, idx + 1)):  # 不超過已用顏色數
            if feasible(v, c):
                color[v] = c
                if solve(idx + 1):
                    return True
                color[v] = -1
        return False

    return color if solve(0) else None

def vertex_cover_greedy_2approx(n, edges):
    """頂點覆蓋的 2-近似貪婪演算法"""
    cover, remaining = set(), set(edges)
    while remaining:
        u, v = remaining.pop()
        cover.update((u, v))
        remaining = {e for e in remaining if u not in e and v not in e}
    return cover

# 五頂點的奇環 C5：不是 2-可著色，是 3-可著色
edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]
print(graph_color_backtrack(5, edges, 2))   # None
print(graph_color_backtrack(5, edges, 3))   # 一組著色
print(vertex_cover_greedy_2approx(5, edges))

複雜度分析#

  • 著色回溯法：最壞 O(kⁿ)，每個頂點 k 種選擇；剪枝使平均情形好很多。
  • 2-著色判定：BFS/DFS，O(n + m)。
  • 頂點覆蓋暴力法：O(2ⁿ·m)；貪婪 2-近似：O(m) 每輪、至多 m 輪，整體 O(m²)，可最佳化到近似線性。
  • 著色的判定版本「χ(G) ≤ k？」是 NP-complete；而「求最小顏色數」是 NP-hard 優化問題。

練習#

  1. 寫一個驗證函式，輸入著色結果與邊集，檢查是否為合法著色；用你的程式驗證 C5 在 k = 3 時的輸出。
  2. Petersen 圖（10 頂點、15 邊）的著色數是 3。用你的程式驗證：k = 2 無解、k = 3 有解。
  3. 證明：I 是獨立集 ⟺ V \ I 是頂點覆蓋。並寫程式把獨立集求解轉成頂點覆蓋求解。