OI Wiki 弦图：如何判定弦图并利用其性质求解问题
【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki
OI Wiki 图论部分的 弦图 文档回答了一个具体任务：给定一个无向图，先判断它是否为弦图，如果是，则借助完美消除序列在 O(n+m) 时间复杂度内求出极大团、色数/团数、最大独立集和最小团覆盖。这些内容之所以有用，是因为很多在一般图上 NP-Hard 的问题在弦图上都有线性时间复杂度的算法，所以"先判定、再利用性质"是一条可落地的解题路径。
前提条件：输入是无向图，记点数为 n、边数为 m。下文代码均为该文档给出的 C++ 参考实现片段（依赖G邻接表、p序号数组、rnk秩数组等原实现中的全局变量），用于展示算法核心逻辑，不是可直接编译运行的完整程序。
判定弦图需要掌握的三个概念
判定算法建立在这三个定义之上：
- 单纯点：设 N(x) 为与点 x 相邻的点集，若 {x}+N(x) 的导出子图为一个团，则 x 为单纯点。
- 完美消除序列：v₁, v₂, …, vₙ 是 1…n 的一个排列，满足每个 vᵢ 在 {vᵢ, vᵢ₊₁, …, vₙ} 的导出子图中为单纯点。
- 核心判据（Lemma 8）：一个无向图是弦图，当且仅当它存在完美消除序列。
判定任务由此转化为两件事：求出候选序列（MCS 算法），再验证该序列是否为完美消除序列。
基线方法：反复删除单纯点
文档先给出朴素算法，适合先理解判定原理：
- 每次找到一个单纯点 v，将其加入完美消除序列；
- 将点 v 与其相邻的边从图上删除；
- 重复上述过程：若所有点都被删除，则原图是弦图，且已求得一个完美消除序列；若图上不存在单纯点，则原图不是弦图。
时间复杂度 O(n⁴)，只适合作为理解基线或极小规模图上的做法，不作为主路径。
主路径：用最大势算法（MCS）在 O(n+m) 内求序列
最大势算法（Maximum Cardinality Search）是文档给出的主路径：
- 逆序给结点编号，即按从 n 到 1 的顺序给点标号；
- 设 labelₓ 表示第 x 个点与多少个已经标号的点相邻，每次选择 label 值最大的未标号结点进行标号；
- 用链表维护对于每个 i，满足 labelₓ=i 的 x。
由于每条边对 Σ labelᵢ 的贡献最多是 2，时间复杂度 O(n+m)。文档中 MCS 的核心循环如下（原实现片段，h/deg/nxt/lst为按 label 值分桶的链表结构，tf记录已标号点，cur为当前标号位置）：
while (cur) { p[cur] = h[nww]; 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 (vector<int>::iterator it = G[p[cur]].begin(); it != G[p[cur]].end(); it++) if (!tf[*it]) { 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; } cur--; if (h[nww + 1]) nww++; while (nww && !h[nww]) nww--; }注意：原图可能不是弦图，此时 MCS 求出的序列一定不是完美消除序列，所以不能到此为止，必须接着验证序列本身。
验证：求出的序列是不是完美消除序列
- 朴素算法：根据定义，依次检查序列上每个 vᵢ 在 {vᵢ,…,vₙ} 中与 vᵢ 相邻的点是否构成团，时间复杂度 O(nm)。
- 优化算法：设 vᵢ 在 {vᵢ,…,vₙ} 中相邻的点按序列下标从小到大为 {v_{c₁},…,v_{c_k}}，则只需判断 v_{c₁} 与其他点是否直接连通即可，时间复杂度 O(n+m)。
文档给出的优化验证代码（st[s[1]]为原实现中 s[1] 的相邻点集合，s[1]始终保存 rnk 最小的邻居，即序列中最早出现的邻居）：
jud = true; for (int i = 1; i <= n; i++) { cur = 0; for (vector<int>::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]); } 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");这就是整条判定链的验证方式：jud全程为 true、输出Perfect，说明序列是完美消除序列，原图是弦图；任一检查失败、输出Imperfect，则原图不是弦图。至此，弦图判定问题在 O(n+m) 时间复杂度内解决。
确认为弦图后，从完美消除序列读取各性质
判定通过之后，序列 p 已经可以当作后续一切计算的基础。以下均为文档给出的线性时间做法。
求所有极大团
弦图的极大团一定为 {x}+N(x)（这里 N(x) 指与 x 相邻且在完美消除序列上位于 x 之后的点），弦图最多有 n 个极大团。判断 {x}+N(x) 是否极大：设 A={x}+N(x)、B={y}+N(y)，若 A⊊B 则 A 不是极大团，此时 y 在序列上位于 x 之前；问题转化为判断是否存在 y 满足 nxt_y=x（nxt_x 为 N(x) 中序列上最靠前的点）且 |N(x)|+1 ≤ |N(y)|，时间复杂度 O(n+m)。文档代码（fst存 nxt，N存邻居个数，vis标记被包含因而非极大的团）：
for (int i = 1; i <= n; i++) { cur = 0; for (vector<int>::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[p[i]] = cur; } 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)| 的最大值：
for (int i = 1; i <= n; i++) ans = max(ans, deg[i] + 1);其中 deg[i] 为点 i 在完美消除序列上之后邻居的个数。若还需要染色方案，则按完美消除序列从后往前依次给每个点染色，给每个点染上可以染的最小颜色，时间复杂度 O(m+n)；文档同时给出了 t=χ(G)=ω(G) 的正确性证明，即该方案用掉的色数恰等于团数也等于色数。
求最大独立集与最小团覆盖
最大独立集：沿完美消除序列从前往后，选择所有与已选点没有直接连边的点。设最大独立集为 {v₁,…,v_t}，则团的集合 {{vᵢ}+N(vᵢ)} 就是图的最小团覆盖，两者时间复杂度均为 O(n+m)：
for (int i = 1; i <= n; i++) if (!vis[p[i]]) { ans++; for (vector<int>::iterator it = G[p[i]].begin(); it != G[p[i]].end(); it++) vis[*it] = true; }注意这段代码与极大团部分复用vis数组，实际使用时两组计算应使用各自独立的标记。
适用边界与可练的题
- 上述结论只对弦图成立：若验证输出
Imperfect，则极大团、色数等线性做法全部不可用，应退回一般图算法。 - 朴素删除单纯点法 O(n⁴)、朴素验证 O(nm) 是文档列出的复杂度基线；文档的主路径（MCS + 优化验证 + 各性质计算）全部为 O(n+m) 级别。
- 文档在"习题"一节列出了几道可用于练习的题：SPOJ FISHNET、洛谷 P3196 [HNOI2008] 神奇的国度、洛谷 P3852 [TJOI2007] 小朋友，可据此对照验证上面的实现。
【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
