图的顶点排序与完美消除序

在图的顶点排序中，完美消除序是一种具有重要理论意义和算法应用的特殊排序。它源于弦图的研究，并在图的分解和优化问题中发挥关键作用。

1. 基本定义
   完美消除序是图顶点的一个线性排序v₁,v₂,...,vₙ，满足对每个顶点vᵢ，其邻域中排在vᵢ后面的顶点构成一个团（完全子图）。这意味着每个顶点与其"后续邻点"之间必须两两相连。

2. 弦图特征
   完美消除序与弦图密切相关：一个图是弦图（不含长度≥4的无弦环）当且仅当它存在完美消除序。这个等价关系为弦图识别提供了算法基础——通过寻找完美消除序来判定图的弦性。

3. 识别算法
   最大基数搜索（MCS）算法能在O(n+m)时间内生成完美消除序或证明其不存在。该算法从最后一个位置开始逆向构建排序，每次选择当前邻域标记数最大的顶点，通过验证后续邻点是否形成团来确认完美性。

4. 应用扩展
   完美消除序支持弦图上多种优化问题的高效求解：

• 着色数和团数可在线性时间内计算
• 最大团和最小染色问题可快速解决
• 作为树分解的特例，支持单调推理
  其思想已推广到更一般的图类，如弱弦图的推广消除序。