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