树分解与 treewidth
Treewidth（树宽）衡量一张图「有多接近一棵树」。它不直接定义在图上，而是借助 tree decomposition（树分解）：把图的顶点装进一棵树的若干 bag（袋）里，在满足三条性质的前提下，让最大的 bag 尽可能小。treewidth 越小，图的结构越像树；而树本身 treewidth = 1。很多在一般图上 NP-hard 的问题，一旦限定 treewidth 有界，就能在 bag 上做 dynamic programming，在多项式甚至线性时间内解决——这正是它被放进图 · 动态规划专题的原因。
1 · 什么是 tree decomposition：三条性质
给定图 G，一个 tree decomposition 是一棵树 T，它的每个节点挂着一个顶点子集，叫 bag。要同时满足三条性质：
**顶点覆盖 (vertex coverage):**每个顶点至少出现在一个 bag 里。
**边覆盖 (edge coverage):**每条边 (u, v) 的两个端点，至少同时出现在某一个 bag 里。
**连通性 (connectivity):**对任意顶点 v,所有包含 v 的 bag 在树 T 上构成一个连通子树——v 不会在树上「断开又出现」。
下面是一张由三个三角形 A-B-C、C-D-E、E-F-G 串成的图（共享顶点 C 与 E），下方是它的一个 tree decomposition——三个 bag 串成一条链 {A,B,C} — {C,D,E} — {E,F,G}。点选某个顶点（或直接点图里的圆点），观察它落在哪些 bag 里、这些 bag
在树上是否相邻。再用「换一种连接」开关，看一个违反连通性的反例。
为什么是「减 1」？ 一个 tree decomposition 的 width = 最大 bag 的大小 − 1。减 1 是为了让树的 treewidth 恰好等于 1：一棵树可以让每个 bag 装一条边的两个端点（bag 大小 2）,width = 2 − 1 = 1。上面这张图的最大 bag 是 3，所以这个分解的 width = 2。
2 · treewidth = 所有分解里最小的 width
同一张图可以有许多不同的 tree decomposition,width 各不相同。图 G 的 treewidth 定义为：在所有合法 tree decomposition 里，width 的最小值。它刻画了这张图「最像树的程度」。切换不同的图族、拖动规模，观察各自（近似）最优分解的 bag 大小与 treewidth 如何变化——树 / 路径 / 环始终很小，网格 / 完全图则随规模增长。
2.1 · 几个参照值
| 图族 | treewidth | 直觉 |
|---|---|---|
| 树 / 森林 (tree / forest) | 1 | 本身就是树，bag 装一条边即可 |
| 环 (cycle) | 2 | 比树多一条回边，升到 2 |
| series-parallel / outerplanar | ≤ 2 | 仍很「窄」 |
| k×k 网格 (grid) | k | 「胖」结构，随边长线性增长 |
| 完全图 Kₙ | n − 1 | 毫无树结构，最坏情形 |
计算 treewidth 本身是 NP-hard。 上面各图族的最优分解是有公式的特例；对任意图求精确 treewidth 很难。但对固定的 w，「treewidth ≤ w？」可在线性时间判定（Bodlaender 算法），实践中也有大量近似与启发式方法。
3 · 为什么重要：bag 是 separator，可在其上做 DP
treewidth 的算法价值，来自一个关键事实：tree decomposition 里的每个 bag 都是图的一个 separator（分隔集）。把分解树从某个 bag 处切开，这个 bag 就是连接两侧的屏障——两侧的顶点之间任何一条路径都必须穿过它。点下方树里的任意一个 bag，看它在图里框出的顶点被「拿掉」后，图怎样断成互不相连的几块。
从 separator 到 DP。 既然每个 bag 都把它的子树与外界隔开，就能自底向上地在分解树上做 dynamic programming：在每个 bag 上，DP 的「状态」只需记录这 ≤ treewidth + 1 个顶点的局部选择（例如「哪些点被选进 independent set」），共
2^(tw+1) 种；子树的其余信息已被这层状态完全屏蔽，无需再看。于是像 maximum independent set、dominating set、graph coloring、Hamiltonian path 这些一般图上 NP-hard 的问题，在 treewidth = w 的图上都能做到
时间——即以 treewidth 为参数的 fixed-parameter tractable (FPT)。
Courcelle 定理把这条思路推到极致：任何能用 monadic second-order logic (MSO) 表达的图性质，在 treewidth 有界的图上都能线性时间判定。配合 grid-minor 定理（treewidth 大 ⟺ 含大网格 minor）,treewidth 成了参数化复杂度与算法图论里最核心的结构参数之一。
4 · 它真实跑在哪里
编译器与寄存器分配：结构化程序的控制流图 treewidth 很小，寄存器分配 / 数据流分析可借此高效求解。
概率图模型推断：贝叶斯网 / 马尔可夫随机场的变量消元与 junction tree 算法，复杂度由图的 treewidth（此处常称 induced width）主导。
组合优化与 OR：有限 treewidth 的约束图上，约束满足(CSP)、整数规划松弛、网络可靠性等可由分解树上的 DP 高效处理。
参数化算法理论:treewidth 是 FPT 算法最常用的结构参数；Courcelle 定理则是一条覆盖面极广的元定理。
5 · 相关链接
- Treewidth — Wikipedia(en.wikipedia.org)——treewidth 与 tree decomposition 的标准定义、各图族的取值、Bodlaender 算法与 grid-minor 定理。
- Tree decomposition — Wikipedia(en.wikipedia.org)——三条性质的形式化、width 的定义，以及在 tree decomposition 上做 DP 的范式。
- Courcelle's theorem — Wikipedia(en.wikipedia.org)——MSO 可表达的图性质在 treewidth 有界图上线性时间可判定的元定理。
- 图 · 动态规划专题（本站 · 同类系列）——shortest-path / MST / tree-DP 等图算法，与本页同属「图 · 动态规划」分类。