OI Wiki 弦图如何判定弦图并利用其性质求解问题【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wikiOI Wiki 图论部分的 弦图 文档回答了一个具体任务给定一个无向图先判断它是否为弦图如果是则借助完美消除序列在 O(nm) 时间复杂度内求出极大团、色数/团数、最大独立集和最小团覆盖。这些内容之所以有用是因为很多在一般图上 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(nm) 内求序列最大势算法Maximum Cardinality Search是文档给出的主路径逆序给结点编号即按从 n 到 1 的顺序给点标号设 labelₓ 表示第 x 个点与多少个已经标号的点相邻每次选择 label 值最大的未标号结点进行标号用链表维护对于每个 i满足 labelₓi 的 x。由于每条边对 Σ labelᵢ 的贡献最多是 2时间复杂度 O(nm)。文档中 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 (vectorint::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(nm)。文档给出的优化验证代码st[s[1]]为原实现中 s[1] 的相邻点集合s[1]始终保存 rnk 最小的邻居即序列中最早出现的邻居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]); } 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(nm) 时间复杂度内解决。确认为弦图后从完美消除序列读取各性质判定通过之后序列 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_yxnxt_x 为 N(x) 中序列上最靠前的点且 |N(x)|1 ≤ |N(y)|时间复杂度 O(nm)。文档代码fst存 nxtN存邻居个数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[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(mn)文档同时给出了 tχ(G)ω(G) 的正确性证明即该方案用掉的色数恰等于团数也等于色数。求最大独立集与最小团覆盖最大独立集沿完美消除序列从前往后选择所有与已选点没有直接连边的点。设最大独立集为 {v₁,…,v_t}则团的集合 {{vᵢ}N(vᵢ)} 就是图的最小团覆盖两者时间复杂度均为 O(nm)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; }注意这段代码与极大团部分复用vis数组实际使用时两组计算应使用各自独立的标记。适用边界与可练的题上述结论只对弦图成立若验证输出Imperfect则极大团、色数等线性做法全部不可用应退回一般图算法。朴素删除单纯点法 O(n⁴)、朴素验证 O(nm) 是文档列出的复杂度基线文档的主路径MCS 优化验证 各性质计算全部为 O(nm) 级别。文档在习题一节列出了几道可用于练习的题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），仅供参考