弦图检查器

伪代码

直接检测弦图性质，也就是去搜寻一个较长的无弦环，代价很高。标准做法是间接的：先求出一个候选的完美消除序，再对它进行验证。

// 第一步：最大势搜索（MCS）
权重[v] = 0（对所有 v）; 序列 = []
重复 V 次:
    选出未编号结点中权重最大的 v
    序列.前插(v)
    对 v 的每个未编号邻居 n: 权重[n]++

// 第二步：验证它是否为完美消除序
对 序列 中位于位置 i 的每个 v:
    靠后邻居 = v 的邻居中出现在 i 之后的那些
    若 靠后邻居 为空: 继续
    w = 靠后邻居 中最靠前的那个结点
    若 靠后邻居 中存在某个 u 与 w 不相邻:
        返回 「不是弦图」
返回 「是弦图」

完美消除序是指这样一种排列：每个结点连同它在序列中靠后的邻居一起构成一个团。一个图是弦图，当且仅当存在这样的序。只要图确实是弦图，最大势搜索总能产出一个，因此验证这一步正是把启发式得到的序变成证明的关键；而当这样的序并不存在时，也正是它把失败检测出来。

分步示例演算

先检测一个四元环是否为弦图，再加入一条弦重新检测。

示例图: 先是四元环 A-B、B-C、C-D、D-A。随后是同一个图再加上弦 A-C。

1. 在四元环上运行 MCS. 最大势搜索给出的序列是 D、C、B、A。
2. 验证 D. D 排在最前面。它在序列中靠后的邻居是 C 与 A。其中最靠前的是 C，因此该项检查要问的是：A 与 C 是否相邻。在纯四元环中并不相邻。
3. 判否. 这个序列不是完美消除序；而既然图若为弦图，MCS 本该找到一个，那么这个四元环就不是弦图。这个结论是对的：A-B-C-D-A 是一个长度为 4 且完全没有弦的环。
4. 加入弦 A-C 后重新检测. MCS 仍然给出 D、C、B、A。验证 D 时，它靠后的邻居是 C 与 A，而现在 A 与 C 相邻，因此检查通过。验证 C 时，它靠后的邻居是 B 与 A，而该检查只要求其余结点与最靠前的那个相邻，也就是与 B 相邻；由于 A-B 是一条边，同样通过。其余每个结点至多只有一个靠后邻居，都平凡地通过。

纯四元环不是弦图；只加上 A-C 这一条弦就使它成为弦图。这就是把定义落到实处：一个图是弦图，是指其中每个含四个或更多结点的环都存在一条连接该环上两个不相邻结点的边。四元环是可能存在的最小反例，这也正是它成为标准测试用例的原因。

复杂度及其来源

时间: O(V + E) · 空间: O(V + E)

若用按权重分桶的方式实现，最大势搜索可以做到 O(V + E)，此时选出最大值与递增邻居权重都是摊还常数时间。验证这一趟对每个结点考察一次、对它的每个靠后邻居考察一次，只要相邻性查询借助哈希集合是常数时间，总计就是 O(V + E)。因此整项检测是线性的，这是个相当出人意料的结果：朴素做法是枚举所有环并逐个检查是否有弦，那是指数级的；即便换一种更聪明的基于环的方法，也仍然差得多。字典序 BFS 是 MCS 的替代方案，界相同。

何时使用弦图检查，何时不宜

弦图性质通常是一道门槛：一旦确认某个图是弦图，若干原本 NP 困难的问题在它上面就变成线性的了。

常见陷阱

• 跳过验证这一步. 无论图是不是弦图，MCS 都会产出一个序列。只有验证这一趟才能把两种情形区分开。把 MCS 的输出当作弦图性质的证明，等于对所有图一律放行。
• 把定义误读成「每个环都有弦」. 这个条件只针对长度为 4 或更长的环。三角形根本不存在不相邻的结点对，因此平凡地满足条件。任何仅由三角形构成的图都是弦图。
• 去检查靠后邻居的所有两两组合. 验证时只需要把每个靠后邻居与其中最靠前的那个作比较，而不必与其余每一个都比。检查所有两两组合虽然正确，却会把一个线性算法变成平方级的。
• 以为弦图就意味着稠密或树状. 树是弦图，因为它根本没有环；完全图也是弦图，因为所有可能的弦都已存在。弦图性质并不是稠密程度的度量，它与稠密与否是横向交叉的。
• 忘记逐个检测每个连通分量. 只有当所有连通分量都是弦图时，整个图才是弦图。若 MCS 是在全部结点上实现的，它自然会覆盖各个分量；但若按分量分别实现，就必须对所有分量都迭代一遍。

常见问题

什么是弦图？

弦图是指其中每个含四个或更多结点的环都带有一条弦的图，所谓弦就是连接该环上两个不相邻结点的边。等价地说，它不含长度超过三角形的诱导环。树、完全图和区间图都是弦图；纯四元环则是最小的非弦图。

如何检测一个图是否为弦图？

先运行最大势搜索得到一个候选的完美消除序，再对它进行验证：对每个结点，它在序列中靠后的所有邻居都必须与其中最靠前的那个相邻。验证通过则该图是弦图；验证失败则不存在完美消除序，它就不是弦图。整项检测为 O(V + E)。

什么是完美消除序？

它是一种结点排列，其中每个结点连同排在它之后的邻居一起构成一个团。一个图存在这样的排列，当且仅当它是弦图，这也正是「求出并验证一个这样的序」成为弦图性质标准检测方法的原因。

弦图为什么重要？

因为若干一般情形下 NP 困难的问题在它上面会变成线性的。借助消除序，最大团、图着色、最大独立集与最小团覆盖在弦图上都能以 O(V + E) 求解。此外，弦图恰好就是那些能被分解成团的树分解的图，而这正是基于树宽的各类算法的基础。

所有的树都是弦图吗？

是的，而且是平凡地成立。弦图性质只约束长度为 4 或更长的环，而树根本没有环，因此该条件空洞地被满足。在另一个极端，完全图同样是弦图，因为所有可能的弦都已经存在了。