图的消去宽度与消去序 基本定义 首先，我们从“消去序”这个概念开始。对于一个图 \( G = (V, E) \)，一个顶点排序 \( (v_ 1, v_ 2, ..., v_ n) \) 称为一个 消去序 ，其核心在于：当我们按照这个顺序“逐个消去”顶点时，需要考虑被消去顶点与其尚未被消去的邻居之间的关系。这个过程通常用于定义图的“宽度”参数，以衡量图的复杂程度。 具体来说，假设我们有一个消去序。当我们准备消去当前排在最前面的顶点 \( v \) 时，考虑此时 \( v \) 在剩余的图（即由所有尚未被消去的顶点构成的子图）中，它的邻居集合。这个邻居集合称为顶点 \( v \) 在该消去序下的 剩余邻居集 。这个集合的大小（即顶点数）称为 \( v \) 在这个消去序下的 消去代价 。 消去宽度 图的 消去宽度 就是针对所有可能的消去序，取其中出现的最大“消去代价”的最小值。更正式地，对于给定的消去序 \( \pi \)，定义其宽度为 \( \text{width}(\pi) = \max_ {v \in V} |\{ u: u \text{ 是 } v \text{ 的邻居，且在序中 } u \text{ 在 } v \text{ 之后} \}| \)。然后，图 \( G \) 的消去宽度 \( \text{Elimination Width}(G) \) 是所有可能的消去序 \( \pi \) 中 \( \text{width}(\pi) \) 的最小值。 直观理解：消去宽度描述的是，为了按照某种最优顺序“处理”掉图中所有顶点，在任一时刻，你最多需要同时记住当前顶点与多少个尚未处理的顶点直接相关。它是一个衡量图“局部稠密性”或“结构化程度”的参数。 与树宽的等价性 一个关键的理论结果是：对于任意无向图 \( G \)，其 消去宽度等于其树宽 。树宽是图论中一个核心的宽度参数，它衡量一个图与树的接近程度。树宽有很多等价定义，其中一种就是通过消去序来定义的，即树宽 = 消去宽度 - 1（有些定义相差常数1）。这个等价性将消去宽度与树分解、弦图补全等概念紧密联系起来。 证明思路：给定一个最优的树分解，其最大袋子（bag）大小减1就是树宽。我们可以从这个树分解构造一个消去序（例如，通过不断移除包含在某个叶子袋子中的顶点），使得在消去过程中，任一顶点在被消去时，其所有尚未被消去的邻居都包含在该顶点所在的某个树袋子里，从而邻居数不超过树宽+1。反之，给定一个最优消去序，可以逆向构造出一个树分解，其最大袋子大小不超过消去宽度+1。 计算与算法意义 计算图的消去宽度（即树宽）本身是NP难的。然而，对于固定常数 \( k \)，存在线性时间算法判断一个图的树宽是否 ≤ \( k \)。这类算法通常基于动态规划，并利用图的某些结构性质（如存在“分离器”）。 消去宽度/树宽之所以重要，是因为许多在一般图上为NP难的问题，在树宽有界（即存在一个很小的常数上界）的图上，可以在多项式时间甚至线性时间内解决。其核心算法范式是：先计算一个最优或近似的树分解（即对应一个较优的消去序），然后在这个分解上进行动态规划。状态转移的复杂度通常是指数依赖于树宽，但若树宽很小，则算法高效。 与完美消除序的关系 完美消除序是弦图的一个特征性概念：一个消去序是完美的，如果每个顶点在被消去时，其剩余邻居集形成一个团。完美消除序对应消去宽度最小（等于该顶点团大小减1）的一种理想情况。更一般地，弦图的树宽等于其最大团的大小减1。因此，消去宽度的研究可以看作是对弦图（完美消除序）概念的一种广义化，它允许剩余邻居集不一定是团，但要求其大小受到全局约束。