图的宽度参数 图的宽度参数是图结构复杂性的一种度量，它量化了一个图在多大程度上“偏离”某种简单的结构（如树）。宽度参数越小，图就越接近这种简单结构，许多NP-难问题在该图上就可能存在高效算法。我们首先从最经典和基础的树宽开始。 1. 树宽 树宽的核心思想是用一棵树来“包裹”原图，从而将图分解为一系列有重叠的、规模较小的子图（称为袋）。 定义 ：图G的树分解是一个二元组 \( (T, \{X_ t\}_ {t \in V(T)}) \)，其中T是一棵树，每个树节点t对应一个袋 \( X_ t \subseteq V(G) \)，满足： 顶点覆盖 ：图G的每个顶点至少出现在一个袋中。 边覆盖 ：图G的每条边的两个端点，至少同时出现在某个袋中。 连通性 ：对于图G的任一顶点v，所有包含v的袋对应的树节点t，在T中诱导出一个连通子树。 树宽 ：树分解 \( (T, \{X_ t\}) \) 的宽度定义为 \( \max_ {t \in V(T)} |X_ t| - 1 \)。图G的树宽 \( tw(G) \) 是其所有树分解的宽度的最小值。 直观理解 ：树可以看作是树宽为1的图。如果一个图的树宽为k，意味着它可以通过将一些小规模（最多k+1个顶点）的子图按树状结构粘合而成。树宽是衡量图“类树”程度的核心参数。 2. 路径宽 路径宽是树宽的一个特例，它对分解树的结构施加了更强的限制。 定义 ：如果一个图G存在一个树分解，其分解树T是一条路径，则该分解称为路径分解。 路径宽 ：图G的路径宽 \( pw(G) \) 是其所有路径分解的宽度的最小值。 与树宽的关系 ：显然，有 \( tw(G) \leq pw(G) \)。因为每条路径都是树，所以路径分解是树分解的一种。但反之不成立，例如一棵星形树（有一个中心顶点连接多个叶子）的树宽为1，但路径宽却等于叶子节点的数量。路径宽衡量的是图“类路径”的程度。 3. 团宽 树宽在描述稠密图（如完全图）时表现不佳，因为一个n个顶点的完全图 \( K_ n \) 的树宽是n-1，非常高。团宽就是为了更好地处理稠密图而提出的。 定义 ：团宽是通过一系列图操作来递归定义的。从单个顶点（标号为1）的图开始，允许以下操作： 不交并 ：将两个已构造的图进行不交并。 重染色 ：将某种颜色i全部改为颜色j。 添加边 ：在颜色i的所有顶点和颜色j的所有顶点之间添加所有可能的边（i ≠ j）。 团宽 ：如果一个图G可以通过k种颜色，从单个顶点开始，利用上述操作构造出来，则称其团宽 \( cw(G) \leq k \)。图G的团宽是满足上述条件的最小颜色数k。 直观理解 ：团宽描述了用“分治”策略构建一个图所需的不同“类型”（颜色）的数量。完全图 \( K_ n \) 的团宽 ≤ 2（可以用一种颜色创建顶点，另一种颜色来添加边），这比其树宽n-1要小得多，表明团宽能更好地捕捉稠密图的结构。 4. 其他重要宽度参数 树宽、路径宽和团宽是三个最核心的宽度参数，但图论中还存在许多其他参数，从不同角度衡量图的复杂性。 分支宽 ：与树宽在常数因子内等价，但定义基于将图递归地分割为两部分的“割”的规模。它在算法设计和图子式理论中非常有用。 顶点覆盖数 ：图G的顶点覆盖数 \( \beta(G) \) 是覆盖所有边所需的最小顶点数。它满足 \( tw(G) \leq \beta(G) \)，是一个非常小但很有用的宽度参数。 退化度 ：图G的退化度d是图中所有子图的最小最大度。即，每次移除一个度数最小的顶点，这个最小度数的最大值。它满足 \( tw(G) \leq d \)。退化度衡量了图的“稀疏”程度。 5. 算法意义与应用 宽度参数最重要的价值在于算法设计，特别是固定参数可处理性。 固定参数可处理（FPT） ：对于一个NP-难问题，如果它可以被一个时间复杂度为 \( O(f(k) \cdot n^{O(1)}) \) 的算法解决，其中k是输入的一个参数（如图的树宽），n是输入规模，f是一个任意（通常是指数）函数，则该问题对于参数k是FPT的。 动态规划 ：对于树宽有界（即k较小）的图，可以首先计算其树分解，然后沿着分解树进行动态规划。由于每个袋的规模很小（k+1），状态空间可控，从而可以在线性时间内解决许多难题（如独立集、染色、支配集等）。 算法元定理 ：著名的库拉托夫斯基定理（Courcelle‘s Theorem）指出，任何可以在** monadic二阶逻辑（MSO2）** 中表达的性质，对于树宽有界的图，都可以在线性时间内判定。这为一大类问题提供了统一的、存在性的高效算法。