OI-wiki 弦圖Chordal Graph全解完美消除序列、MCS 最大勢算法與五大線性可解問題【免費下載鏈接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戲線上攻略內含炫酷算術魔法項目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki導讀弦圖是一類結構優美的特殊無向圖任意長度大于 3 的環都至少有一條弦連接環上不相鄰兩點的邊。正是這條看似簡單的性質使得大量在一般圖上屬于 NP-Hard 的問題最大團、最小染色、最大獨立集、最小團覆蓋在弦圖上全部擁有$O(nm)$ 的線性時間復雜度算法。本文以 docs/graph/chord.md 為主體系統梳理弦圖的定義與性質、點割集與單純點理論、完美消除序列、最大勢MCS線性判定算法并給出極大團、色數/團數、最大獨立集/最小團覆蓋五大經典問題的構造方法與完整參考代碼。讀完本文你將掌握弦圖的完整理論脈絡與可直接套用的線性算法實現。一、弦圖基礎定義與基本性質1.1 相關圖論概念在正式定義弦圖之前先建立一組貫穿全文的圖論術語記原圖為 $G(V,E)$子圖點集和邊集均為原圖點集和邊集子集的圖。導出子圖誘導子圖點集為原圖點集子集邊集為所有滿足兩個端點均在選定點集中的邊構成的圖。導出子圖完全由選點決定不能自由增減邊。團完全子圖即其中任意兩點之間都有邊相連。極大團不是其他團子圖的團即無法再加入任何點仍保持為團。最大團點數最大的團。團數最大團的點數記為 $\omega(G)$。最小染色用最少的顏色給點染色使得所有邊連接的兩點顏色不同。色數最小染色所需的顏色數記為 $\chi(G)$。最大獨立集最大的點集使得點集中任意兩點都沒有邊直接相連。其大小記為 $\alpha(G)$。最小團覆蓋用最少的團覆蓋所有的點使用的團數記為 $\kappa(G)$。1.2 弦與弦圖弦連接環中不相鄰兩點的邊。弦圖任意長度大于 $3$ 的環都有一個弦的圖稱為弦圖。直觀理解弦圖是一類沒有大而無弦的環的圖。三角剖分圖、森林、樹、完全圖都是弦圖的典型特例。弦圖的這一強結構約束正是后續所有線性算法的根基。弦圖相關前置知識可參考 docs/graph/concept.md 與 docs/graph/max-clique.md團與最大團問題。1.3 四個基礎引理Lemma 1–4Lemma 1團數 $\omega(G)\le \chi(G)$色數。證明單獨考慮最大團的導出子圖進行染色至少需要 $\omega(G)$ 種顏色團內任意兩點相鄰必須異色。Lemma 2最大獨立集數 $\alpha(G)\le \kappa(G)$最小團覆蓋數。證明每個團中至多選擇一個點團內兩點均相鄰不能同屬一個獨立集。Lemma 3弦圖的任意導出子圖一定是弦圖。證明反證。如果弦圖存在一個導出子圖不是弦圖說明該導出子圖上存在一個大于 $3$ 的無弦環那么無論原圖如何加邊這個無弦環都始終存在原圖不可能是弦圖矛盾。Lemma 4弦圖的任意導出子圖一定不可能是一個點數大于 $3$ 的環。證明點數大于 $3$ 的環不是弦圖環上不存在連接不相鄰兩點的弦由 Lemma 3 直接推出。Lemma 3 與 Lemma 4 揭示了弦圖的遺傳性hereditary property這是后續用歸納法論證任何弦圖都有單純點的關鍵。而 Lemma 1、Lemma 2 則給出了四個經典參數之間的兩對一邊一界關系為后文證明弦圖上 $\omega\chi$、$\alpha\kappa$埋下伏筆。二、弦圖的判定問題與理論工具2.1 問題描述給定一個無向圖 $G$判斷其是否為弦圖。樸素思路是枚舉所有長度大于 $3$ 的環檢查弦但環數量可能是指數級。本節將沿著點割集 → 單純點 → 完美消除序列的路徑構建出線性時間判定算法。2.2 點割集對于圖 $G$ 上的兩點 $u,v$定義這兩點間的點割集為刪除這一集合后$u,v$ 兩點之間不再連通。若關于 $u,v$ 兩點間的一個點割集的任意子集都不是點割集則稱這個點割集為極小點割集注意極小是集合包含關系下的極小而非點數最小。Lemma 5圖關于 $u,v$ 的極小點割集將原圖分成了若干個連通塊。設包含 $u$ 的連通塊為 $V_1$包含 $v$ 的連通塊為 $V_2$則對于極小點割集上的任意一點 $a$$N(a)$$a$ 的鄰域一定包含 $V_1$ 和 $V_2$ 中的點。證明若 $N(a)$ 只包含 $V_1$、$V_2$ 中至多一個連通塊的點則從點割集中刪去 $a$ 后 $u,v$ 仍不連通說明原點割集不是極小點割集矛盾。Lemma 6弦圖上任意兩點間的極小點割集的導出子圖一定為一個團。證明分情況當極小點割集大小 $\le 1$ 時導出子圖顯然是一個團。否則設極小點割集上有兩點 $x,y$。由 Lemma 5$N(x)$ 中有 $V_1,V_2$ 中的點設為 $x_1,x_2$同理設 $y_1,y_2$注意可能有 $x_1y_1,\ x_2y_2$。由于 $V_1,V_2$ 均為連通塊在 $x_1,y_1$ 與 $x_2,y_2$ 兩個點對之間分別存在最短路徑。于是圖上存在一個環 $x-x_1\sim y_1-y-y_2\sim x_2-x$該環大小一定 $\ge 4$。根據弦圖定義該環上一定存在一條弦若這條弦連接了 $V_1,V_2$ 兩個連通塊則刪去點割集后 $u,v$ 仍連通點集不是點割集若這條弦連接單個連通塊內部的兩個點或連接一個連通塊內部點與點割集上的點都會破壞最短路的性質所以這條弦只能連接 $x,y$ 兩點。由此弦圖中每個極小點割集中的任意兩點都有邊直接相連性質得證。Lemma 6 是一個核心結構定理弦圖中割開任意兩點的最小隔斷集合本身必須是一個團這為歸納構造單純點提供了落腳點。2.3 單純點設 $N(x)$ 表示與點 $x$ 相鄰的點集。若點集 ${x}N(x)$ 的導出子圖為一個團則稱點 $x$ 為單純點simplicial vertex。通俗地說單純點的所有鄰居彼此兩兩相鄰即 $x$ 與它的鄰居們共同構成一個團。Lemma 7任何一個弦圖都至少有一個單純點不是完全圖的弦圖至少有兩個不相鄰的單純點。證明數學歸納法單獨考慮每一個連通塊歸納基底當圖與完全圖同構時圖上任意一點都是單純點當圖的點數 $\le 3$ 時引理成立。若圖點數 $\ge 4$ 且不為完全圖則必然存在 $u,v$ 使得 $(u,v)\notin E$。設 $I$ 是圖關于 $u,v$ 的極小點割集$A,B$ 分別是刪去 $I$ 后 $u,v$ 所在的連通塊。由對稱性只考慮 $A$ 一側設 $LAI$若 $L$ 為完全圖則 $u$ 為單純點若 $L$ 不是完全圖因為 $L$ 是原圖的導出子圖由 Lemma 3 知 $L$ 也是弦圖歸納假設給出 $L$ 中至少有兩個不相鄰的單純點。又因 $I$ 是一個團Lemma 6其上兩點都相鄰所以 $A$ 中一定有一個單純點該單純點擴展到全圖仍為單純點。由于每次把圖分成若干連通塊證明塊的大小嚴格減小且都滿足性質歸納成立。2.4 完美消除序列令 $n|V|$完美消除序列Perfect Elimination Ordering, PEO$v_1,v_2,\ldots,v_n$ 是 $1,2,\ldots,n$ 的一個排列滿足 $v_i$ 在 ${v_i,v_{i1},\ldots,v_n}$ 的導出子圖中為單純點。即按序列順序逐個刪點刪到每個點時它都是剩余圖的單純點。Lemma 8一個無向圖是弦圖當且僅當其有一個完美消除序列。充分性點數為 $1$ 的弦圖有完美消除序列。由 Lemma 3 和 Lemma 7點數為 $n$ 的弦圖的完美消除序列可以由點數為 $n-1$ 的弦圖的完美消除序列加上一個單純點得到歸納。必要性反證。假設存在無向圖含有一個結點數 $3$ 的環且擁有完美消除序列。設在完美消除序列中第一個出現的環上的點為 $v$$v$ 在環上與 $v_1,v_2$ 相連。由完美消除序列的性質即單純點的定義$v_1,v_2$ 必須直接有邊相連這與 $v_1,v_2$ 是環上不相鄰兩點的假設矛盾它們之間的邊正是弦。Lemma 8 是整篇文章的樞紐弦圖 ? 存在完美消除序列。于是判定弦圖完全轉化為求完美消除序列與驗證序列合法性兩個子問題。三、求完美消除序列的算法3.1 樸素算法$O(n^4)$最直觀的做法完全照抄定義每次在剩余圖中找到一個單純點$v$將其加入完美消除序列將點 $v$ 與其相鄰的邊從圖上刪除重復上述過程若所有點都被刪除則原圖是弦圖且已求得一個完美消除序列若剩余圖上不存在單純點則原圖不是弦圖。每次找單純點需要掃描所有點并檢查其鄰域是否為團每輪刪除一個點總時間復雜度 $O(n^4)$。樸素算法正確性顯然由 Lemma 8但只適合作為理論基準。3.2 MCS 最大勢算法$O(nm)$最大勢算法Maximum Cardinality Search, MCS是可以在 $O(nm)$ 時間內求出無向圖完美消除序列的方法由 Tarjan 與 Yannakakis 于 1984 年提出見文末參考資料。算法流程逆序給結點編號按從 $n$ 到 $1$ 的順序給點標號即最后標號的點在完美消除序列最前面。設 $label_x$ 表示第 $x$ 個點與多少個已經標號的點相鄰每次選擇 $label$ 值最大的未標號結點進行標號。用鏈表維護對于每個 $i$滿足 $label_xi$ 的結點 $x$ 的集合使得每次取最大 $label$ 與更新 label 都是 $O(1)$。復雜度分析由于每條邊對 $\sum_{i1}^n label_i$ 的貢獻最多是 $2$一條邊 ${a,b}$ 只會在 $a$、$b$ 中先標號的那個點被計數一次所有 label 更新總量為 $O(m)$故總時間復雜度 $O(nm)$。正確性證明設 $\alpha(x)$ 為 $x$ 在這個序列中的位置。需要證明對于任何弦圖MCS 求出的序列一定是完美消除序列即在序列中位于某個點后面且與這個點相連的所有點兩兩相連。Lemma 9考慮三個點 $u,v,w$ 滿足 $\alpha(u)\alpha(v)\alpha(w)$。如果 $uw$ 相連、$vw$ 不相連則 $w$ 只給 $u$ 的 $label$ 貢獻不給 $v$ 貢獻。為了讓 $v$ 比 $u$ 先加入序列需要存在一個 $x$ 滿足 $\alpha(v)\alpha(x)$ 且 $vx$ 相連、$ux$ 不相連即 $x$ 只給 $v$ 貢獻而不給 $u$ 貢獻。Lemma 10任意一個弦圖一定不存在一個序列 $v_0,v_1,\dots,v_k\ (k\ge 2)$ 滿足下列三條性質$v_iv_j$ 相連當且僅當 $|i-j|1$即 $v_0v_1\cdots v_k$ 構成一條誘導路徑/無弦路徑$\alpha(v_0)\alpha(v_i)\ (i\in[1,k])$存在 $i\in[1,k-1]$滿足 $\alpha(v_i)\alpha(v_{i1})\dots\alpha(v_k)$ 且 $\alpha(v_i)\alpha(v_{i-1})\dots\alpha(v_1)\alpha(v_k)\alpha(v_0)$。證明由于 $\alpha(v_1)\alpha(v_k)\alpha(v_0)$且 $v_1v_0$ 相連、$v_kv_0$ 不相連由 Lemma 9 知存在 $x$ 滿足 $\alpha(v_k)\alpha(x)$ 且 $v_kx$ 相連、$v_1x$ 不相連。考慮最小的$j\in(1,k]$ 滿足 $v_jx$ 相連可推出 $v_0x$ 不相連否則 $v_0v_1\cdots v_jx$ 構成一個長度 $\ge 4$ 且無弦的環與弦圖定義矛盾。若 $\alpha(x)\alpha(v_0)$則 $v_0,v_1,\dots,v_j,x$ 也是滿足性質的序列若 $\alpha(v_0)\alpha(x)$則 $x,v_j,\dots,v_1,v_0$ 也是滿足性質的序列。在上面的推導中我們擴大了 $\min(v_0,v_k)$于是不斷重復這個過程一直推下去最終一定會產生矛盾。Theorem 1對于任何一個弦圖最大勢算法求出的序列一定是一個完美消除序列。證明考慮任意三個點 $u,v,w$ 滿足 $\alpha(u)\alpha(v)\alpha(w)$需要證明若 $uv$ 相連、$uw$ 相連則 $vw$ 一定相連。反證假設 $vw$ 不相連那么 $w,u,v$ 就是一個滿足 Lemma 10 中性質的序列$v_0w,\ v_1u,\ v_2v$ 滿足路徑、位置與交叉順序條件而 Lemma 10 已證明這樣的序列在弦圖中不存在矛盾故 $vw$ 相連。3.3 MCS 參考代碼以下是 MCS 算法的參考實現來自 docs/graph/chord.md。代碼中h[i]為 $labeli$ 的結點鏈表的表頭nxt/lst為鏈表的前驅后繼p為完美消除序列rnk為位置數組tf標記已標號deg即 $label$ 值nww為當前非空的最大 label 桶編號while (cur) { p[cur] h[nww]; // 取 label 最大的未標號點 rnk[p[cur]] cur; // 記錄其在序列中的位置 h[nww] nxt[h[nww]]; // 從鏈表中刪除該點 lst[h[nww]] 0; lst[p[cur]] nxt[p[cur]] 0; tf[p[cur]] true; // 標記已標號 for (vectorint::iterator it G[p[cur]].begin(); it ! G[p[cur]].end(); it) if (!tf[*it]) { // 對未標號的鄰居更新 label if (h[deg[*it]] *it) h[deg[*it]] nxt[*it]; nxt[lst[*it]] nxt[*it]; lst[nxt[*it]] lst[*it]; lst[*it] nxt[*it] 0; deg[*it]; nxt[*it] h[deg[*it]]; lst[h[deg[*it]]] *it; h[deg[*it]] *it; // 移入 label1 的桶 } cur--; if (h[nww 1]) nww; // 維護最大桶編號 while (nww !h[nww]) nww--; }重要說明若原圖是弦圖此時求出的就是完美消除序列但若原圖不是弦圖MCS 求出的序列一定不是完美消除序列否則由 Lemma 8 充分性會推出它是弦圖矛盾。所以問題轉化為判斷求出的序列是否是原圖的完美消除序列。四、判斷一個序列是否是完美消除序列4.1 樸素算法$O(nm)$根據定義依次判斷完美消除序列 $v$ 上${v_i,v_{i1},\ldots,v_n}$ 中與 $v_i$ 相鄰的點是否構成了一個團。對每個 $v_i$ 枚舉其相鄰點對并檢查邊存在性總時間復雜度 $O(nm)$。4.2 優化后的算法$O(nm)$根據完美消除序列的定義設 $v_i$ 在 ${v_i,v_{i1},\ldots,v_n}$ 中相鄰的點從小到大按序列位置為 ${v_{c_1},v_{c_2},\ldots,v_{c_k}}$則只需判斷 $v_{c_1}$序列位置最靠前的鄰居與其他點是否直接連通即可。這是因為如果 $v_{c_1}$ 與所有其他鄰居都相鄰則整個鄰居集合構成團其他鄰居兩兩相鄰可遞歸由 $v_{c_1}$ 的團性推出——嚴格地說只需檢查最靠前的鄰居連通其余全部鄰居。時間復雜度降為 $O(nm)$。參考代碼rnk為位置數組st為鄰接集合jud true; for (int i 1; i n; i) { cur 0; for (vectorint::iterator it G[p[i]].begin(); it ! G[p[i]].end(); it) if (rnk[p[i]] rnk[*it]) { // 只保留序列中位于其后的鄰居 s[cur] *it; if (rnk[s[cur]] rnk[s[1]]) swap(s[1], s[cur]); // s[1] 最靠前的鄰居 } for (int j 2; j cur; j) if (!st[s[1]].count(s[j])) { // 最靠前鄰居必須連通其余全部鄰居 jud false; break; } } if (!jud) printf(Imperfect\n); else printf(Perfect\n);至此弦圖判定問題可以在 $O(nm)$ 的時間復雜度內解決先跑 MCS 求候選序列再以 $O(nm)$ 驗證其為完美消除序列。五、弦圖的極大團5.1 極大團的結構刻畫令 $N(x)$ 表示與 $x$ 直接有邊相連且在完美消除序列上位于 $x$ 之后的鄰居集合。則弦圖的極大團一定為 ${x}N(x)$。證明考慮弦圖的一個極大團 $V$取 $V$ 中點在完美消除序列中第一個出現的點 $x$。$V$ 中其余點都在 $x$ 之后$x$ 是第一個出現的且與 $x$ 相鄰所以 $V\subseteq {x}N(x)$又因為 $V$ 是極大團故 $V{x}N(x)$。由該刻畫立即可得弦圖最多有 $n$ 個極大團每個點至多對應一個。5.2 判定每個 ${x}N(x)$ 是否為極大團求出每個 ${x}N(x)$ 后需要剔除其中被包含的非極大團設 $A{x}N(x),\ B{y}N(y)$若 $A\subsetneqq B$則 $A$ 不是極大團。此時在完美消除序列上顯然有 $y$ 在 $x$ 前。設 $nxt_x$ 表示 $N(x)$ 中在完美消除序列上最靠前的點$y^$ 表示所有滿足 $A\subseteq B$ 的 $y$ 中最靠后的點。此時必然有 $nxt_{y^}x$否則 $y^$ 不是最靠后的令 $y^nxt_{y^*}$ 仍然滿足條件。$A\subsetneqq B$ 當且僅當 $|A|1\le |B|$。于是問題轉化為判斷是否存在 $y$滿足 $nxt_yx$ 且 $|N(x)|1\le |N(y)|$總時間復雜度 $O(nm)$。參考代碼fst[p[i]]記錄 $nxt_{p[i]}$N[p[i]]$ 記錄 $|N(p[i])|$vis 標記被包含而非極大團的候選for (int i 1; i n; i) { cur 0; for (vectorint::iterator it G[p[i]].begin(); it ! G[p[i]].end(); it) if (rnk[p[i]] rnk[*it]) { s[cur] *it; if (rnk[s[cur]] rnk[s[1]]) swap(s[1], s[cur]); } fst[p[i]] s[1]; // N(x) 中序列位置最靠前的點 N[p[i]] cur; // |N(x)| } for (int i 1; i n; i) { if (!vis[p[i]]) ans; // 未被標記的點對應一個極大團 if (N[p[i]] N[fst[p[i]]] 1) vis[fst[p[i]]] true; // {x}N(x) 被包含則標記 }注意處理s[1]為空的邊界$N(x)$ 為空集時 ${x}N(x){x}$ 即單點團。六、弦圖的色數與團數在一般圖上最小染色是 NP-Hard 的但在弦圖上借助完美消除序列可以貪心求解。構造方法按完美消除序列從后往前依次給每個點染色給每個點染上可以染的最小顏色即與所有已染色的鄰居都不沖突的最小顏色編號。時間復雜度 $O(mn)$。正確性證明設以上方法使用了 $t$ 種顏色則 $t\ge \chi(G)$任何合法染色都至少需要 $\chi$ 種顏色。另一方面從后往前染色時每當引入一種新顏色被染的這個點與其所有序列位置在其后且已染色的鄰居都相鄰且它們兩兩相鄰完美消除序列性質共同構成一個團故 $t\le \omega(G)$即 $t\omega(G)$。由 Lemma 1 得 $t\omega(G)\le \chi(G)$。綜上 $t\chi(G)\omega(G)$即弦圖色數等于團數貪心染色達到最優。只需數值不求方案當無需具體染色方案、只需求弦圖的色數/團數時可以直接取 $|{x}N(x)|$ 的最大值即最大團的點數一行代碼即可for (int i 1; i n; i) ans max(ans, deg[i] 1);這里deg[i]若為完美消除序列中位于 $i$ 之后的鄰居數 $|N(i)|$則deg[i]1 |{i}N(i)|$恰為包含 $i$ 的那個團的規模。七、弦圖的最大獨立集與最小團覆蓋同樣在一般圖上 NP-Hard 的兩個問題在弦圖上也有線性貪心解法。最大獨立集按完美消除序列從前往后掃描選擇所有沒有與已經選擇的點有直接連邊的點。最小團覆蓋設上面求出的最大獨立集為 ${v_1,v_2,\ldots,v_t}$則團的集合 ${{v_1N(v_1)},{v_2N(v_2)},\ldots,{v_tN(v_t)}}$ 為圖的最小團覆蓋。兩者時間復雜度均為 $O(nm)$。正確性證明設以上方案得到的獨立集大小與團覆蓋數為 $t$。貪心選擇的點集中任意兩點不相鄰故 $t\le \alpha(G)$而每個團 ${v_iN(v_i)}$ 覆蓋了 $v_i$ 且這些團覆蓋全體點故 $t\ge \kappa(G)$。由 Lemma 2 得 $\alpha(G)\le \kappa(G)$所以 $t\alpha(G)\kappa(G)$即最大獨立集等于最小團覆蓋數且貪心同時達到兩者最優。參考代碼vis在此處標記已被已選獨立集點覆蓋/相鄰的點for (int i 1; i n; i) if (!vis[p[i]]) { // 按序列從前往后未被覆蓋則選入獨立集 ans; for (vectorint::iterator it G[p[i]].begin(); it ! G[p[i]].end(); it) vis[*it] true; // 其鄰居不能入選獨立集 }八、弦圖五大問題復雜度一覽問題一般圖復雜度弦圖復雜度算法要點弦圖判定—$O(nm)$MCS 求序列 線性驗證極大團枚舉可能指數級$O(nm)$最多 $n$ 個${x}N(x)$ 刻畫 包含剔除色數 / 團數NP-Hard$O(nm)$序列逆序貪心染色數值取 $\max|x|N(x)|$最大獨立集NP-Hard$O(nm)$序列正序貪心選點最小團覆蓋NP-Hard$O(nm)$由最大獨立集對應團構成從表中可以清晰看到弦圖的價值四個經典 NP-Hard 參數在弦圖上全部退化為線性可解且核心算法共用同一個完美消除序列一套預處理MCS即可支撐全部問題。九、實戰指引與進一步閱讀應用場景弦圖理論在區間圖interval graph染色、完美圖perfect graph理論、超圖無環性檢驗、稀疏線性方程組消元順序消元時保持圖性質等領域都有直接應用競賽中常見模型是區間相交圖類問題其本質即為弦圖。代碼落地完整參考代碼均出自 docs/graph/chord.md實現時注意 MCS 的鏈表桶結構、逆序標號約定以及驗證階段只檢查最靠前鄰居連通其余鄰居這一線性技巧。相關主題團與最大團的一般性算法見 docs/graph/max-clique.mdBron–Kerbosch 算法基礎術語見 docs/graph/concept.md圖染色專題可繼續閱讀 docs/graph/color.md。習題SPOJ FISHNET - Fishing Net弦圖判定模板題P3196 [HNOI2008] 神奇的國度弦圖染色/團數應用P3852 [TJOI2007] 小朋友弦圖相關綜合應用參考資料yhx-12243 的 OI-transit 筆記《弦圖相關》2009 WC 講稿《弦圖與區間圖》陳丹琦租酥雨《弦圖總結》系列博客R. E. Tarjan and M. Yannakakis,Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13 (1984), pp. 566–579.MCS 算法的原始出處【免費下載鏈接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戲線上攻略內含炫酷算術魔法項目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki創作聲明：本文部分內容由AI輔助生成（AIGC），僅供參考 OI-wiki 弦圖（Chordal Graph）全解：完美消除序列、MCS 最大勢算法與五大線性可解問題
OI-wiki 弦圖Chordal Graph全解完美消除序列、MCS 最大勢算法與五大線性可解問題【免費下載鏈接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戲線上攻略內含炫酷算術魔法項目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki導讀弦圖是一類結構優美的特殊無向圖任意長度大于 3 的環都至少有一條弦連接環上不相鄰兩點的邊。正是這條看似簡單的性質使得大量在一般圖上屬于 NP-Hard 的問題最大團、最小染色、最大獨立集、最小團覆蓋在弦圖上全部擁有$O(nm)$ 的線性時間復雜度算法。本文以 docs/graph/chord.md 為主體系統梳理弦圖的定義與性質、點割集與單純點理論、完美消除序列、最大勢MCS線性判定算法并給出極大團、色數/團數、最大獨立集/最小團覆蓋五大經典問題的構造方法與完整參考代碼。讀完本文你將掌握弦圖的完整理論脈絡與可直接套用的線性算法實現。一、弦圖基礎定義與基本性質1.1 相關圖論概念在正式定義弦圖之前先建立一組貫穿全文的圖論術語記原圖為 $G(V,E)$子圖點集和邊集均為原圖點集和邊集子集的圖。導出子圖誘導子圖點集為原圖點集子集邊集為所有滿足兩個端點均在選定點集中的邊構成的圖。導出子圖完全由選點決定不能自由增減邊。團完全子圖即其中任意兩點之間都有邊相連。極大團不是其他團子圖的團即無法再加入任何點仍保持為團。最大團點數最大的團。團數最大團的點數記為 $\omega(G)$。最小染色用最少的顏色給點染色使得所有邊連接的兩點顏色不同。色數最小染色所需的顏色數記為 $\chi(G)$。最大獨立集最大的點集使得點集中任意兩點都沒有邊直接相連。其大小記為 $\alpha(G)$。最小團覆蓋用最少的團覆蓋所有的點使用的團數記為 $\kappa(G)$。1.2 弦與弦圖弦連接環中不相鄰兩點的邊。弦圖任意長度大于 $3$ 的環都有一個弦的圖稱為弦圖。直觀理解弦圖是一類沒有大而無弦的環的圖。三角剖分圖、森林、樹、完全圖都是弦圖的典型特例。弦圖的這一強結構約束正是后續所有線性算法的根基。弦圖相關前置知識可參考 docs/graph/concept.md 與 docs/graph/max-clique.md團與最大團問題。1.3 四個基礎引理Lemma 1–4Lemma 1團數 $\omega(G)\le \chi(G)$色數。證明單獨考慮最大團的導出子圖進行染色至少需要 $\omega(G)$ 種顏色團內任意兩點相鄰必須異色。Lemma 2最大獨立集數 $\alpha(G)\le \kappa(G)$最小團覆蓋數。證明每個團中至多選擇一個點團內兩點均相鄰不能同屬一個獨立集。Lemma 3弦圖的任意導出子圖一定是弦圖。證明反證。如果弦圖存在一個導出子圖不是弦圖說明該導出子圖上存在一個大于 $3$ 的無弦環那么無論原圖如何加邊這個無弦環都始終存在原圖不可能是弦圖矛盾。Lemma 4弦圖的任意導出子圖一定不可能是一個點數大于 $3$ 的環。證明點數大于 $3$ 的環不是弦圖環上不存在連接不相鄰兩點的弦由 Lemma 3 直接推出。Lemma 3 與 Lemma 4 揭示了弦圖的遺傳性hereditary property這是后續用歸納法論證任何弦圖都有單純點的關鍵。而 Lemma 1、Lemma 2 則給出了四個經典參數之間的兩對一邊一界關系為后文證明弦圖上 $\omega\chi$、$\alpha\kappa$埋下伏筆。二、弦圖的判定問題與理論工具2.1 問題描述給定一個無向圖 $G$判斷其是否為弦圖。樸素思路是枚舉所有長度大于 $3$ 的環檢查弦但環數量可能是指數級。本節將沿著點割集 → 單純點 → 完美消除序列的路徑構建出線性時間判定算法。2.2 點割集對于圖 $G$ 上的兩點 $u,v$定義這兩點間的點割集為刪除這一集合后$u,v$ 兩點之間不再連通。若關于 $u,v$ 兩點間的一個點割集的任意子集都不是點割集則稱這個點割集為極小點割集注意極小是集合包含關系下的極小而非點數最小。Lemma 5圖關于 $u,v$ 的極小點割集將原圖分成了若干個連通塊。設包含 $u$ 的連通塊為 $V_1$包含 $v$ 的連通塊為 $V_2$則對于極小點割集上的任意一點 $a$$N(a)$$a$ 的鄰域一定包含 $V_1$ 和 $V_2$ 中的點。證明若 $N(a)$ 只包含 $V_1$、$V_2$ 中至多一個連通塊的點則從點割集中刪去 $a$ 后 $u,v$ 仍不連通說明原點割集不是極小點割集矛盾。Lemma 6弦圖上任意兩點間的極小點割集的導出子圖一定為一個團。證明分情況當極小點割集大小 $\le 1$ 時導出子圖顯然是一個團。否則設極小點割集上有兩點 $x,y$。由 Lemma 5$N(x)$ 中有 $V_1,V_2$ 中的點設為 $x_1,x_2$同理設 $y_1,y_2$注意可能有 $x_1y_1,\ x_2y_2$。由于 $V_1,V_2$ 均為連通塊在 $x_1,y_1$ 與 $x_2,y_2$ 兩個點對之間分別存在最短路徑。于是圖上存在一個環 $x-x_1\sim y_1-y-y_2\sim x_2-x$該環大小一定 $\ge 4$。根據弦圖定義該環上一定存在一條弦若這條弦連接了 $V_1,V_2$ 兩個連通塊則刪去點割集后 $u,v$ 仍連通點集不是點割集若這條弦連接單個連通塊內部的兩個點或連接一個連通塊內部點與點割集上的點都會破壞最短路的性質所以這條弦只能連接 $x,y$ 兩點。由此弦圖中每個極小點割集中的任意兩點都有邊直接相連性質得證。Lemma 6 是一個核心結構定理弦圖中割開任意兩點的最小隔斷集合本身必須是一個團這為歸納構造單純點提供了落腳點。2.3 單純點設 $N(x)$ 表示與點 $x$ 相鄰的點集。若點集 ${x}N(x)$ 的導出子圖為一個團則稱點 $x$ 為單純點simplicial vertex。通俗地說單純點的所有鄰居彼此兩兩相鄰即 $x$ 與它的鄰居們共同構成一個團。Lemma 7任何一個弦圖都至少有一個單純點不是完全圖的弦圖至少有兩個不相鄰的單純點。證明數學歸納法單獨考慮每一個連通塊歸納基底當圖與完全圖同構時圖上任意一點都是單純點當圖的點數 $\le 3$ 時引理成立。若圖點數 $\ge 4$ 且不為完全圖則必然存在 $u,v$ 使得 $(u,v)\notin E$。設 $I$ 是圖關于 $u,v$ 的極小點割集$A,B$ 分別是刪去 $I$ 后 $u,v$ 所在的連通塊。由對稱性只考慮 $A$ 一側設 $LAI$若 $L$ 為完全圖則 $u$ 為單純點若 $L$ 不是完全圖因為 $L$ 是原圖的導出子圖由 Lemma 3 知 $L$ 也是弦圖歸納假設給出 $L$ 中至少有兩個不相鄰的單純點。又因 $I$ 是一個團Lemma 6其上兩點都相鄰所以 $A$ 中一定有一個單純點該單純點擴展到全圖仍為單純點。由于每次把圖分成若干連通塊證明塊的大小嚴格減小且都滿足性質歸納成立。2.4 完美消除序列令 $n|V|$完美消除序列Perfect Elimination Ordering, PEO$v_1,v_2,\ldots,v_n$ 是 $1,2,\ldots,n$ 的一個排列滿足 $v_i$ 在 ${v_i,v_{i1},\ldots,v_n}$ 的導出子圖中為單純點。即按序列順序逐個刪點刪到每個點時它都是剩余圖的單純點。Lemma 8一個無向圖是弦圖當且僅當其有一個完美消除序列。充分性點數為 $1$ 的弦圖有完美消除序列。由 Lemma 3 和 Lemma 7點數為 $n$ 的弦圖的完美消除序列可以由點數為 $n-1$ 的弦圖的完美消除序列加上一個單純點得到歸納。必要性反證。假設存在無向圖含有一個結點數 $3$ 的環且擁有完美消除序列。設在完美消除序列中第一個出現的環上的點為 $v$$v$ 在環上與 $v_1,v_2$ 相連。由完美消除序列的性質即單純點的定義$v_1,v_2$ 必須直接有邊相連這與 $v_1,v_2$ 是環上不相鄰兩點的假設矛盾它們之間的邊正是弦。Lemma 8 是整篇文章的樞紐弦圖 ? 存在完美消除序列。于是判定弦圖完全轉化為求完美消除序列與驗證序列合法性兩個子問題。三、求完美消除序列的算法3.1 樸素算法$O(n^4)$最直觀的做法完全照抄定義每次在剩余圖中找到一個單純點$v$將其加入完美消除序列將點 $v$ 與其相鄰的邊從圖上刪除重復上述過程若所有點都被刪除則原圖是弦圖且已求得一個完美消除序列若剩余圖上不存在單純點則原圖不是弦圖。每次找單純點需要掃描所有點并檢查其鄰域是否為團每輪刪除一個點總時間復雜度 $O(n^4)$。樸素算法正確性顯然由 Lemma 8但只適合作為理論基準。3.2 MCS 最大勢算法$O(nm)$最大勢算法Maximum Cardinality Search, MCS是可以在 $O(nm)$ 時間內求出無向圖完美消除序列的方法由 Tarjan 與 Yannakakis 于 1984 年提出見文末參考資料。算法流程逆序給結點編號按從 $n$ 到 $1$ 的順序給點標號即最后標號的點在完美消除序列最前面。設 $label_x$ 表示第 $x$ 個點與多少個已經標號的點相鄰每次選擇 $label$ 值最大的未標號結點進行標號。用鏈表維護對于每個 $i$滿足 $label_xi$ 的結點 $x$ 的集合使得每次取最大 $label$ 與更新 label 都是 $O(1)$。復雜度分析由于每條邊對 $\sum_{i1}^n label_i$ 的貢獻最多是 $2$一條邊 ${a,b}$ 只會在 $a$、$b$ 中先標號的那個點被計數一次所有 label 更新總量為 $O(m)$故總時間復雜度 $O(nm)$。正確性證明設 $\alpha(x)$ 為 $x$ 在這個序列中的位置。需要證明對于任何弦圖MCS 求出的序列一定是完美消除序列即在序列中位于某個點后面且與這個點相連的所有點兩兩相連。Lemma 9考慮三個點 $u,v,w$ 滿足 $\alpha(u)\alpha(v)\alpha(w)$。如果 $uw$ 相連、$vw$ 不相連則 $w$ 只給 $u$ 的 $label$ 貢獻不給 $v$ 貢獻。為了讓 $v$ 比 $u$ 先加入序列需要存在一個 $x$ 滿足 $\alpha(v)\alpha(x)$ 且 $vx$ 相連、$ux$ 不相連即 $x$ 只給 $v$ 貢獻而不給 $u$ 貢獻。Lemma 10任意一個弦圖一定不存在一個序列 $v_0,v_1,\dots,v_k\ (k\ge 2)$ 滿足下列三條性質$v_iv_j$ 相連當且僅當 $|i-j|1$即 $v_0v_1\cdots v_k$ 構成一條誘導路徑/無弦路徑$\alpha(v_0)\alpha(v_i)\ (i\in[1,k])$存在 $i\in[1,k-1]$滿足 $\alpha(v_i)\alpha(v_{i1})\dots\alpha(v_k)$ 且 $\alpha(v_i)\alpha(v_{i-1})\dots\alpha(v_1)\alpha(v_k)\alpha(v_0)$。證明由于 $\alpha(v_1)\alpha(v_k)\alpha(v_0)$且 $v_1v_0$ 相連、$v_kv_0$ 不相連由 Lemma 9 知存在 $x$ 滿足 $\alpha(v_k)\alpha(x)$ 且 $v_kx$ 相連、$v_1x$ 不相連。考慮最小的$j\in(1,k]$ 滿足 $v_jx$ 相連可推出 $v_0x$ 不相連否則 $v_0v_1\cdots v_jx$ 構成一個長度 $\ge 4$ 且無弦的環與弦圖定義矛盾。若 $\alpha(x)\alpha(v_0)$則 $v_0,v_1,\dots,v_j,x$ 也是滿足性質的序列若 $\alpha(v_0)\alpha(x)$則 $x,v_j,\dots,v_1,v_0$ 也是滿足性質的序列。在上面的推導中我們擴大了 $\min(v_0,v_k)$于是不斷重復這個過程一直推下去最終一定會產生矛盾。Theorem 1對于任何一個弦圖最大勢算法求出的序列一定是一個完美消除序列。證明考慮任意三個點 $u,v,w$ 滿足 $\alpha(u)\alpha(v)\alpha(w)$需要證明若 $uv$ 相連、$uw$ 相連則 $vw$ 一定相連。反證假設 $vw$ 不相連那么 $w,u,v$ 就是一個滿足 Lemma 10 中性質的序列$v_0w,\ v_1u,\ v_2v$ 滿足路徑、位置與交叉順序條件而 Lemma 10 已證明這樣的序列在弦圖中不存在矛盾故 $vw$ 相連。3.3 MCS 參考代碼以下是 MCS 算法的參考實現來自 docs/graph/chord.md。代碼中h[i]為 $labeli$ 的結點鏈表的表頭nxt/lst為鏈表的前驅后繼p為完美消除序列rnk為位置數組tf標記已標號deg即 $label$ 值nww為當前非空的最大 label 桶編號while (cur) { p[cur] h[nww]; // 取 label 最大的未標號點 rnk[p[cur]] cur; // 記錄其在序列中的位置 h[nww] nxt[h[nww]]; // 從鏈表中刪除該點 lst[h[nww]] 0; lst[p[cur]] nxt[p[cur]] 0; tf[p[cur]] true; // 標記已標號 for (vectorint::iterator it G[p[cur]].begin(); it ! G[p[cur]].end(); it) if (!tf[*it]) { // 對未標號的鄰居更新 label if (h[deg[*it]] *it) h[deg[*it]] nxt[*it]; nxt[lst[*it]] nxt[*it]; lst[nxt[*it]] lst[*it]; lst[*it] nxt[*it] 0; deg[*it]; nxt[*it] h[deg[*it]]; lst[h[deg[*it]]] *it; h[deg[*it]] *it; // 移入 label1 的桶 } cur--; if (h[nww 1]) nww; // 維護最大桶編號 while (nww !h[nww]) nww--; }重要說明若原圖是弦圖此時求出的就是完美消除序列但若原圖不是弦圖MCS 求出的序列一定不是完美消除序列否則由 Lemma 8 充分性會推出它是弦圖矛盾。所以問題轉化為判斷求出的序列是否是原圖的完美消除序列。四、判斷一個序列是否是完美消除序列4.1 樸素算法$O(nm)$根據定義依次判斷完美消除序列 $v$ 上${v_i,v_{i1},\ldots,v_n}$ 中與 $v_i$ 相鄰的點是否構成了一個團。對每個 $v_i$ 枚舉其相鄰點對并檢查邊存在性總時間復雜度 $O(nm)$。4.2 優化后的算法$O(nm)$根據完美消除序列的定義設 $v_i$ 在 ${v_i,v_{i1},\ldots,v_n}$ 中相鄰的點從小到大按序列位置為 ${v_{c_1},v_{c_2},\ldots,v_{c_k}}$則只需判斷 $v_{c_1}$序列位置最靠前的鄰居與其他點是否直接連通即可。這是因為如果 $v_{c_1}$ 與所有其他鄰居都相鄰則整個鄰居集合構成團其他鄰居兩兩相鄰可遞歸由 $v_{c_1}$ 的團性推出——嚴格地說只需檢查最靠前的鄰居連通其余全部鄰居。時間復雜度降為 $O(nm)$。參考代碼rnk為位置數組st為鄰接集合jud true; for (int i 1; i n; i) { cur 0; for (vectorint::iterator it G[p[i]].begin(); it ! G[p[i]].end(); it) if (rnk[p[i]] rnk[*it]) { // 只保留序列中位于其后的鄰居 s[cur] *it; if (rnk[s[cur]] rnk[s[1]]) swap(s[1], s[cur]); // s[1] 最靠前的鄰居 } for (int j 2; j cur; j) if (!st[s[1]].count(s[j])) { // 最靠前鄰居必須連通其余全部鄰居 jud false; break; } } if (!jud) printf(Imperfect\n); else printf(Perfect\n);至此弦圖判定問題可以在 $O(nm)$ 的時間復雜度內解決先跑 MCS 求候選序列再以 $O(nm)$ 驗證其為完美消除序列。五、弦圖的極大團5.1 極大團的結構刻畫令 $N(x)$ 表示與 $x$ 直接有邊相連且在完美消除序列上位于 $x$ 之后的鄰居集合。則弦圖的極大團一定為 ${x}N(x)$。證明考慮弦圖的一個極大團 $V$取 $V$ 中點在完美消除序列中第一個出現的點 $x$。$V$ 中其余點都在 $x$ 之后$x$ 是第一個出現的且與 $x$ 相鄰所以 $V\subseteq {x}N(x)$又因為 $V$ 是極大團故 $V{x}N(x)$。由該刻畫立即可得弦圖最多有 $n$ 個極大團每個點至多對應一個。5.2 判定每個 ${x}N(x)$ 是否為極大團求出每個 ${x}N(x)$ 后需要剔除其中被包含的非極大團設 $A{x}N(x),\ B{y}N(y)$若 $A\subsetneqq B$則 $A$ 不是極大團。此時在完美消除序列上顯然有 $y$ 在 $x$ 前。設 $nxt_x$ 表示 $N(x)$ 中在完美消除序列上最靠前的點$y^$ 表示所有滿足 $A\subseteq B$ 的 $y$ 中最靠后的點。此時必然有 $nxt_{y^}x$否則 $y^$ 不是最靠后的令 $y^nxt_{y^*}$ 仍然滿足條件。$A\subsetneqq B$ 當且僅當 $|A|1\le |B|$。于是問題轉化為判斷是否存在 $y$滿足 $nxt_yx$ 且 $|N(x)|1\le |N(y)|$總時間復雜度 $O(nm)$。參考代碼fst[p[i]]記錄 $nxt_{p[i]}$N[p[i]]$ 記錄 $|N(p[i])|$vis 標記被包含而非極大團的候選for (int i 1; i n; i) { cur 0; for (vectorint::iterator it G[p[i]].begin(); it ! G[p[i]].end(); it) if (rnk[p[i]] rnk[*it]) { s[cur] *it; if (rnk[s[cur]] rnk[s[1]]) swap(s[1], s[cur]); } fst[p[i]] s[1]; // N(x) 中序列位置最靠前的點 N[p[i]] cur; // |N(x)| } for (int i 1; i n; i) { if (!vis[p[i]]) ans; // 未被標記的點對應一個極大團 if (N[p[i]] N[fst[p[i]]] 1) vis[fst[p[i]]] true; // {x}N(x) 被包含則標記 }注意處理s[1]為空的邊界$N(x)$ 為空集時 ${x}N(x){x}$ 即單點團。六、弦圖的色數與團數在一般圖上最小染色是 NP-Hard 的但在弦圖上借助完美消除序列可以貪心求解。構造方法按完美消除序列從后往前依次給每個點染色給每個點染上可以染的最小顏色即與所有已染色的鄰居都不沖突的最小顏色編號。時間復雜度 $O(mn)$。正確性證明設以上方法使用了 $t$ 種顏色則 $t\ge \chi(G)$任何合法染色都至少需要 $\chi$ 種顏色。另一方面從后往前染色時每當引入一種新顏色被染的這個點與其所有序列位置在其后且已染色的鄰居都相鄰且它們兩兩相鄰完美消除序列性質共同構成一個團故 $t\le \omega(G)$即 $t\omega(G)$。由 Lemma 1 得 $t\omega(G)\le \chi(G)$。綜上 $t\chi(G)\omega(G)$即弦圖色數等于團數貪心染色達到最優。只需數值不求方案當無需具體染色方案、只需求弦圖的色數/團數時可以直接取 $|{x}N(x)|$ 的最大值即最大團的點數一行代碼即可for (int i 1; i n; i) ans max(ans, deg[i] 1);這里deg[i]若為完美消除序列中位于 $i$ 之后的鄰居數 $|N(i)|$則deg[i]1 |{i}N(i)|$恰為包含 $i$ 的那個團的規模。七、弦圖的最大獨立集與最小團覆蓋同樣在一般圖上 NP-Hard 的兩個問題在弦圖上也有線性貪心解法。最大獨立集按完美消除序列從前往后掃描選擇所有沒有與已經選擇的點有直接連邊的點。最小團覆蓋設上面求出的最大獨立集為 ${v_1,v_2,\ldots,v_t}$則團的集合 ${{v_1N(v_1)},{v_2N(v_2)},\ldots,{v_tN(v_t)}}$ 為圖的最小團覆蓋。兩者時間復雜度均為 $O(nm)$。正確性證明設以上方案得到的獨立集大小與團覆蓋數為 $t$。貪心選擇的點集中任意兩點不相鄰故 $t\le \alpha(G)$而每個團 ${v_iN(v_i)}$ 覆蓋了 $v_i$ 且這些團覆蓋全體點故 $t\ge \kappa(G)$。由 Lemma 2 得 $\alpha(G)\le \kappa(G)$所以 $t\alpha(G)\kappa(G)$即最大獨立集等于最小團覆蓋數且貪心同時達到兩者最優。參考代碼vis在此處標記已被已選獨立集點覆蓋/相鄰的點for (int i 1; i n; i) if (!vis[p[i]]) { // 按序列從前往后未被覆蓋則選入獨立集 ans; for (vectorint::iterator it G[p[i]].begin(); it ! G[p[i]].end(); it) vis[*it] true; // 其鄰居不能入選獨立集 }八、弦圖五大問題復雜度一覽問題一般圖復雜度弦圖復雜度算法要點弦圖判定—$O(nm)$MCS 求序列 線性驗證極大團枚舉可能指數級$O(nm)$最多 $n$ 個${x}N(x)$ 刻畫 包含剔除色數 / 團數NP-Hard$O(nm)$序列逆序貪心染色數值取 $\max|x|N(x)|$最大獨立集NP-Hard$O(nm)$序列正序貪心選點最小團覆蓋NP-Hard$O(nm)$由最大獨立集對應團構成從表中可以清晰看到弦圖的價值四個經典 NP-Hard 參數在弦圖上全部退化為線性可解且核心算法共用同一個完美消除序列一套預處理MCS即可支撐全部問題。九、實戰指引與進一步閱讀應用場景弦圖理論在區間圖interval graph染色、完美圖perfect graph理論、超圖無環性檢驗、稀疏線性方程組消元順序消元時保持圖性質等領域都有直接應用競賽中常見模型是區間相交圖類問題其本質即為弦圖。代碼落地完整參考代碼均出自 docs/graph/chord.md實現時注意 MCS 的鏈表桶結構、逆序標號約定以及驗證階段只檢查最靠前鄰居連通其余鄰居這一線性技巧。相關主題團與最大團的一般性算法見 docs/graph/max-clique.mdBron–Kerbosch 算法基礎術語見 docs/graph/concept.md圖染色專題可繼續閱讀 docs/graph/color.md。習題SPOJ FISHNET - Fishing Net弦圖判定模板題P3196 [HNOI2008] 神奇的國度弦圖染色/團數應用P3852 [TJOI2007] 小朋友弦圖相關綜合應用參考資料yhx-12243 的 OI-transit 筆記《弦圖相關》2009 WC 講稿《弦圖與區間圖》陳丹琦租酥雨《弦圖總結》系列博客R. E. Tarjan and M. Yannakakis,Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13 (1984), pp. 566–579.MCS 算法的原始出處【免費下載鏈接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戲線上攻略內含炫酷算術魔法項目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki創作聲明：本文部分內容由AI輔助生成（AIGC），僅供參考