「彼此都不認識的最大群體」與「彼此都認識的最大群體」——在補圖裡它們是同一個問題

三位一體

三個問題可互相歸約，NP-Complete 身分一起確立（Karp 21）。但注意微妙差異：Vertex Cover 有 2-近似與 FPT 演算法，Independent Set / Clique 卻兩者皆無——除非 P=NP，Max Clique 連 \(n^{1-\varepsilon}\) 倍的近似都做不到（Håstad 1999）。「\(n\) 減去好近似的東西」不會自動是好近似，這是近似理論最重要的陷阱之一。

演算法一：最大獨立集的分支剪枝

分支規則

挑剩餘圖中度數最大的點 \(v\)：

• 分支 A：不選 \(v\) —— 從圖中刪 \(v\)。

• 分支 B：選 \(v\) —— 刪 \(v\) 與其全部鄰居（他們不能再選），計數 \(+1\)。

若剩餘點全是孤立點，全收。用 bitmask 表示「剩餘點集合」讓刪點變一個 AND 運算。最壞仍指數，但在 \(n=20\)、43 條邊的隨機圖上只需 339 個節點（暴力枚舉要 \(2^{20}\approx10^6\) 個子集）。

演算法二：最大團的 Bron–Kerbosch

三個集合的舞蹈

維護 \((R, P, X)\)：\(R\) = 目前團、\(P\) = 還能加入的候選（與 \(R\) 全相鄰）、\(X\) = 處理過不准再用（防止重複列舉同一個極大團）：

expand(R, P, X):
    if P and X both empty:  report R as maximal clique
    choose pivot u in P|X maximizing |N(u) & P|
    for each v in P \ N(u):              // 只展開 pivot 蓋不住的
        expand(R+{v}, P & N(v), X & N(v))
        move v from P to X

Pivot 的直覺：若 \(v\in N(u)\)，那麼含 \(v\) 的極大團也會在展開 \(u\) 的分支裡被找到，跳過它不漏解卻大砍分支。理論上限 \(O(3^{n/3})\)——恰等於一張圖最多可能有的極大團數（Moon–Moser 圖），所以這是輸出最優的枚舉法。

手算範例：\(C_5\)

環 \(0\!-\!1\!-\!2\!-\!3\!-\!4\!-\!0\)：任三點必有兩點不相鄰，故 \(\omega=2\)（任一條邊）。獨立集 \(\alpha=2\)（如 \(\{0,2\}\)）；\(\{0,2,4\}\) 不行因為 \(4\!-\!0\) 是邊。驗證三位一體：\(\min VC = 5-2 = 3\)（如 \(\{1,3,4\}\)）。\(C_5\) 是最小的「\(\alpha+\omega\) 都嚴格小於界」的自補圖，也是完美圖理論的著名反例。

完整 C++ 程式

包含：bitmask 暴力枚舉（\(n\leq 20\) 基準）、度數分支剪枝、Bron–Kerbosch with pivot、補圖轉換、三位一體驗證與社群偵測情境。編譯：

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

執行結果與解讀

=== Example 1: cycle C5 ===
max independent set = 2  {0,2}
max clique = 2  {0,1}

=== Example 2: trinity on Petersen graph ===
max IS in G           = 4  {2,4,5,6}
max clique in G'      = 4  {0,2,8,9}
n - maxIS = 10 - 4 = 6  (= minimum vertex cover size)

=== Example 3: branch-and-prune vs brute force (n=20) ===
n=20, |E|=43
brute force  : maxIS=8 (2^20 = 1,048,576 subsets)
branch+prune : maxIS=8 (nodes=339)
agree = yes

=== Example 4: find the largest group of mutual friends ===
max clique size = 4  members {0,1,2,3}  (BK calls=12)

實務應用

• 社群偵測：社交網路中的緊密小圈子 = 團；LinkedIn 的「你們可能是同事」背後是稠密子圖挖掘。

• 生物資訊：蛋白質交互作用網的功能模組、基因共表達群 = 團搜尋；分子對接的相容性圖找最大團是製藥業日常。

• 排程衝突：任務相容圖的最大獨立集 = 可同時執行的最大任務集。

• 無線通訊：干擾圖的最大獨立集 = 可同時發送的最大裝置集合。

• 組合拍賣：標的衝突圖的最大加權獨立集 = 收益最大的得標組合。

練習題

1. 手算 Petersen 圖某個大小 4 的獨立集，並驗證其補集是頂點覆蓋。

2. 樹上的最大獨立集有 \(O(n)\) 的 DP（每點選/不選）——實作並與本篇程式在隨機樹上對答案。

3. 把 MaxISBranch 加上上界剪枝：剩餘點數 + 已選數 \(\leq\) 已知最佳就砍。實測節點數。

4. 修改 Bron–Kerbosch 列出全部極大團（不只最大），數 Petersen 圖有幾個。

5. 挑戰：加權最大獨立集的分支剪枝（點有權重，最大化總權重）。

小結

延伸閱讀：Bron & Kerbosch (1973) 原始論文；Tomita et al. (2006) pivot 版最壞情況分析；Håstad (1999) Clique 不可近似性；Robson (1986) \(O(1.2^n)\) 最大獨立集。