图的弦图与完美消除序 我们先从一个直观的例子开始。假设你有一个社交网络图，其中顶点代表人，边代表两人互相认识。如果这个图具有一种特殊的性质： 图中每个长度大于3的环都有一条“弦” （即环中两个不相邻顶点之间有一条边），那么这个图就称为 弦图 。弦图之所以重要，是因为许多在图的一般情形下困难的计算问题，在弦图上可以高效解决。 1. 弦图的定义与例子 定义 ：一个无向图 \(G=(V,E)\) 是弦图，如果它的每个长度至少为4的环都有一个弦（连接环上两个非连续顶点的边）。 等价的说法是：弦图中没有长度大于3的无弦环（即诱导环的长度只能是3）。 例1 ：树是弦图，因为树中根本没有环，自然满足定义。 例2 ：完全图是弦图，因为任何环都有弦。 例3 ：环 \(C_ 4\)（4个顶点构成的环）不是弦图，因为它没有弦。 弦图也称为 三角化图 ，因为可以在图中添加一些边使之变成弦图的过程称为“三角化”。 2. 弦图的等价刻画：完美消除序 弦图有一个极重要的等价性质，涉及顶点排序。 定义 ：设 \(v_ 1, v_ 2, \dots, v_ n\) 是图 \(G\) 的顶点的一个排序。这个排序称为 完美消除序 ，如果对于每个顶点 \(v_ i\)，它的邻居中排在 \(v_ i\) 后面的那些顶点构成一个团。 形式化：令 \(N^+(v_ i) = \{v_ j \mid (v_ i,v_ j) \in E, j>i\}\)，则要求 \(N^+(v_ i)\) 是一个团（即其中任意两点相邻）。 关键定理 （Fulkerson & Gross 1965, Dirac 等）：一个图是弦图，当且仅当它有一个完美消除序。 例 ：考虑一个简单弦图：4个顶点 \(a,b,c,d\)，边为 \(ab, ac, bc, bd, cd\)（实际上这是一个三角形 \(abc\) 加上一条边到 \(d\) 与 \(b,c\) 相连，这是弦图）。 一个完美消除序可以是 \(a, d, b, c\)： 对于 \(a\)，后面的邻居是 \(\{b,c\}\)，它们相邻（团）。 对于 \(d\)，后面的邻居是 \(\{b,c\}\)，它们相邻。 对于 \(b\)，后面的邻居是 \(\{c\}\)，单个顶点是平凡团。 对于 \(c\)，后面无邻居，满足。 3. 如何找到完美消除序：最大势算法（LexBFS） 有一个线性时间算法（Lexicographic Breadth-First Search, LexBFS）可以生成弦图的一个完美消除序，如果图是弦图，这个排序就是完美消除序；如果不是弦图，可以在排序的基础上检验是否满足完美消除性质，从而判断是否为弦图。 LexBFS 基本思想 ： 从最后一个顶点开始选，每次选一个与 已选出顶点集合 的邻居最多的顶点（按字典序打破平局），逆向记录顺序，最后得到的就是一个候选完美消除序。 检验：对每个顶点 \(v_ i\)，检查 \(N^+(v_ i)\) 是否构成团，即检查 \(N^+(v_ i)\) 中下标最小的那个顶点是否与其他所有顶点相邻。可在 \(O(|V|+|E|)\) 内完成。 4. 弦图与树分解的关系 弦图与图的树宽有深刻联系： 弦图是那些存在团树（clique tree）的图。 团树：将弦图的所有极大团作为节点，连成树，使得对于任意顶点 \(x\)，包含 \(x\) 的极大团在这棵树中形成一个连通子树。 弦图的树宽 = 最大团的大小 \(-1\)。 因此，在弦图上计算树宽很容易：找出所有极大团（弦图中最大团数量 ≤ |V|），取最大团大小减1。 5. 弦图上的算法应用 因为弦图具有完美消除序，许多 NP 难问题在弦图上有多项式时间算法： 图着色 ：用贪心算法按完美消除序逆序着色，可得到最优着色（弦图是完美图，χ=ω）。 最大团 ：在弦图中，最大团可以在线性时间找到（通过检查每个顶点与其后邻居构成的团的大小）。 最大独立集、最小顶点覆盖、最小团覆盖 等问题在弦图上也可高效求解。 弦图也是 树宽有界图 的一个重要子类，很多动态规划在弦图上更易实现。 6. 弦图的判定 总结判定步骤： 用 LexBFS 生成一个顶点排序。 检验这个排序是否为完美消除序（对每个顶点检查其后邻居是否构成团）。 若是，则为弦图；否则不是。 整体复杂度 \(O(|V|+|E|)\)。 7. 弦图在应用中的例子 稀疏矩阵的高斯消元法：消元顺序对应于图的完美消除序时，不会产生多余的填充边，当且仅当该图是弦图。 贝叶斯网络、语法分析树等结构化模型中，弦图对应着可分解模型。 计算机视觉中的马尔可夫随机场推理。