尧图网页设计 
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），仅供参考