树分解与树宽

形式陈述 ​

图 $G=(V,E)$ 的树分解由一棵树 $T$ 和每个节点 $t\in V(T)$ 对应的顶点袋 $B_t\subseteq V$ 构成，满足：

1. 顶点覆盖：$\bigcup _{t\in V(T)}{B}_t=V$；
2. 边覆盖：对每条 $uv\in E$，存在 $t$ 使 $\{u,v\}\subseteq B_t$；
3. 运行交性质：对每个 $v\in V$，集合 $\{t:v\in B_t\}$ 在 $T$ 中诱导连通子树。

该分解的宽度是

$$\underset{t\in V(T)}{max}|B_t|-1,$$

图的树宽 $\mathrm{tw}(G)$ 是所有树分解宽度的最小值。减一使一棵至少含一条边的树具有树宽 $1$，而无边图具有树宽 $0$。

第三个条件也可写成：若 $t_2$ 位于 $T$ 中 $t_1$ 到 $t_3$ 的路径上，则 $B_{t_1}\cap B_{t_3}\subseteq B_{t_2}$。它保证一个顶点在分解树上的出现区间不会中断后重新出现。

直觉 ​

每个 bag 是局部计算能看见的接口，分解树说明这些局部接口如何拼接。运行交性质保证关于同一原图顶点的信息沿树传播时始终连续，否则两个远处子问题可能都使用该顶点，中间却没有地方保持它们的一致性。

树宽衡量图能否用小接口拆成树状结构，而不是测量某棵生成树的宽度。小树宽图可以拥有很多顶点；真正受限的是任何分隔处需要同时记住多少顶点。

例子与边界 ​

把一棵有根树 $G$ 的根袋取为 $\{r\}$，其余顶点 $v$ 的袋取为 $\{v,\mathrm{parent}(v)\}$，并按原树连接这些袋，就得到宽度 $1$ 的树分解。因此非平凡森林的树宽为 $1$。

环 $C_n$ 的树宽为 $2$。按路径排列袋

$$\{v_1,v_2,v_3\},\{v_1,v_3,v_4\},\dots ,\{v_1,v_{n-1},v_n\}$$

给出宽度 $2$ 的分解，而树宽 $1$ 的图必须是森林，所以不能更低。团 $K_n$ 的树宽是 $n-1$：每个顶点出现的节点集是 $T$ 的一棵子树，这些子树因每对顶点相邻而两两相交；树的 Helly 性迫使某个袋同时包含全部 $n$ 个顶点。

bag 不必在原图中诱导连通子图或团。仅满足边覆盖也不够：若同一顶点出现在分解树两端却不出现在中间袋，局部结果无法一致拼合。树分解也通常不唯一，宽度只取所有合法分解中的最优值。

推论与应用 ​

给定宽度 $k$ 的树分解，许多图问题可沿 $T$ 做动态规划公理库动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。：每个状态只记录至多 $k+1$ 个接口顶点的局部信息。因而 Hamilton 路、顶点覆盖等在 $k$ 固定时可获得形如 $f(k)n^{O(1)}$ 的算法；复杂度取决于状态设计，也取决于是否已经给出或能求得分解。

树宽在取图 minor公理库图 minorGraph minor · Minor of a graph通过删顶点、删边和收缩边从原图获得的粗粒度图结构。时不增，团 minor 又给出树宽下界。它因此连接结构图论与固定参数可解类公理库参数化复杂度类 FPTFixed-parameter tractable · FPT可在 f(k)n^O(1) 时间内求解的参数化问题类。：排除某些 minor 的图族往往具有可控的分解结构。这里的定义只建立 bag 语言；nice decomposition 与 Courcelle 型元定理需要额外构造和逻辑假设，不是定义本身的直接同义词。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017, Chapter 12.
• Erik D. Demaine and MohammadTaghi Hajiaghayi, MIT 6.889 lecture notes on treewidth and graph decompositions.