弦图详解

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

什么是弦图？

弦图，也称三角剖分图，是这样一种图：其中每个含四个或更多顶点的环都有一条弦。弦是一条连接环上两个沿环彼此不相邻顶点的边。换句话说，弦图不含长度为四或更长的诱导环：每个长环都被较短的边切成三角形。

这个定义听起来很窄，但许多你已经熟悉的图都是弦图：树、完全图和区间图都是弦图。下图展示了最小的有趣情形，一个四顶点的环，分别是它的非弦图形式和弦图形式。

弦与诱导环

真正起作用的词是诱导。当一个环的顶点之间仅有的边就是环边本身时，这个环是诱导的。一旦出现一条弦，长环就不再是诱导的：它已经被三角剖分。

所以这两个定义是同一句话的两个视角：

• 每个长度 ≥ 4 的环都有一条弦，或等价地
• 该图没有长度 ≥ 4 的诱导环（没有诱导的 C₄、C₅ 等等）。

三角形作为长度为 3 的环，总是被允许，也从不需要弦。这就是为什么弦图给人一种"由三角形搭起来"的感觉。

单纯点与消去顺序

弦图真正的威力来自一个结构性定理。先给两个定义。

• 若一个顶点的邻居构成一个团（即它们两两相邻），则该顶点是单纯点。
• 完美消去顺序（PEO）是顶点的一个排序 v₁, v₂, …, vₙ，使得在移除 v₁ 到 vₚ₋₁ 之后剩下的图中，每个 vₚ 都是单纯点。

Fulkerson-Gross 定理把这一切串了起来：

一个图是弦图当且仅当它有一个完美消去顺序。此外，每个弦图至少有一个单纯点，所以你总能从剥掉一个开始。

这就是弦图上每一个高效算法背后的引擎。一旦有了 PEO，你就可以按那个顺序处理顶点、贪心地解决问题，因为在每一步，该顶点剩下的邻居都构成一个团，毫无意外。

识别一个弦图

给定一个图，怎么判断它是不是弦图？你可以去搜寻诱导环，但那很慢。优雅的做法利用 PEO 的刻画，运行在线性时间 O(V + E)。

1. 运行字典序广度优先搜索（Lex-BFS）或最大势搜索。两者都通过总是接下来访问已访问邻居最多的顶点，来产生一个顶点顺序。
2. 把那个顺序倒过来。如果图是弦图，那么这个逆序保证是一个完美消去顺序。
3. 验证这个候选顺序确实是 PEO。若是，图就是弦图；若检查失败，则不是。

这种搜索依赖广度优先搜索，并加以改造，使得平局由字典序标签来打破。验证这一步才是值得看代码的部分。

用 Python 验证一个顺序

核心检查如下：给定以邻接集合表示的图和一个候选顺序，判断它是否是完美消去顺序。对每个顶点，它靠后的邻居必须全都与其中最靠前的那个相邻。

def is_perfect_elimination_order(graph, order):
    pos = {v: i for i, v in enumerate(order)}

    for v in order:
        # 在顺序中排在 v 之后的邻居。
        later = [u for u in graph[v] if pos[u] > pos[v]]
        if len(later) <= 1:
            continue

        # 此处 v 是单纯点当且仅当这些靠后的邻居构成一个团。
        # 只需检查它们是否都与最靠前的那个 w 相邻即可。
        w = min(later, key=lambda u: pos[u])
        for u in later:
            if u != w and u not in graph[w]:
                return False   # w 和 u 排在 v 之后，却不相邻

    return True

如果它对倒过来的 Lex-BFS 顺序返回 True，那么图就是弦图。同一个 PEO 随后会被复用来解决下面那些困难问题。

弦图为何重要

弦图是完美图，在这一类图中，色数总是等于最大团的大小。这种结构把若干出了名的困难问题坍缩成容易问题。给定一个完美消去顺序，下面每一个都在线性时间内完成。

还有一颗宝石。一个图是弦图，恰当它拥有一棵团树，即一种树分解，其中的袋子正是极大团。这把弦图与树宽联系起来：任何图的树宽，等于在它所有弦图补全上可能达到的最小最大团大小，再减一。要了解这一类图在更广图景中的位置，见图论的应用和学习路线图。

现实应用

• 稀疏矩阵求解：高斯消元在运行时会把零位置填满，而最小化这种填充恰恰就是加弦使图成为弦图的问题，即弦图补全。
• 编译器：现代 SSA 形式代码上的寄存器分配变成弦图着色，这正是它能被最优且快速求解的原因。
• 概率模型：贝叶斯网络的联结树算法会把图三角剖分，也就是使其成为弦图，然后在它的团树上进行计算。
• 生物信息学与调度：区间图作为弦图的一个子类，用来建模相互重叠的区间，比如基因片段或时间段。