树分解与树宽 | Codeboy's Blog

形式陈述

设 $G=(V,E)$ 是有限、非空的简单无向图。它的树分解由一棵树 $T$ 和每个节点 $t\in V(T)$ 对应的顶点袋 $B_t\subseteq V$ 构成，满足：

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

该分解的宽度是

\max_{t\in V(T)}|B_t|-1,

图的树宽 $\operatorname{tw}(G)$ 是所有树分解宽度的最小值。减一使一棵至少含一条边的树具有树宽 $1$ ，而非空无边图具有树宽 $0$ 。本文不把空图纳入这些宽度约定。

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

为什么袋确实是分隔边界

将分解树任意选根。对节点 $t$ ，记 $T_t$ 为 $t$ 及其所有后代形成的子树，并令

V_t=\bigcup_{x\in V(T_t)}B_x.

$V_t$ 是这一支处理过的全部原图顶点， $B_t$ 是当前仍保留的接口；二者一般不相等。关键结论是： $V_t\setminus B_t$ 中的顶点不可能与 $V\setminus V_t$ 中的顶点相邻。 换言之，从已经进入内部的顶点走向外部，必须经过当前袋。

先证明一个更直接的事实。若 $v\in V_t\setminus B_t$ 在 $T_t$ 外的袋中也出现，那么从它在后代的出现位置到那个外部位置的树路径经过 $t$ 。运行交性质便迫使 $v\in B_t$ ，矛盾。因此， $v$ 的所有出现位置都在 $T_t$ 内。现在假设有边 $vu$ 且 $u\notin V_t$ 。边覆盖要求某个袋同时包含 $v,u$ ；这个袋因包含 $v$ 必在 $T_t$ 内，又推出 $u\in V_t$ ，仍然矛盾。

这个证明解释了运行交性质与边覆盖如何协作。前者让“已经离开接口”的顶点永久留在这一支，后者让它的每个邻居也必须在这一支出现。算法因此可以忘掉内部顶点的名字，只保留它对当前接口的影响和已经取得的目标值。

还有一个在合并两支时更精确的版本。设 $t$ 的两个孩子为 $l,r$ ，且 $B_t=B_l=B_r=B$ 。若顶点同时属于 $V_l,V_r$ ，连接两次出现的路径经过 $t$ ，故它属于 $B$ ；反向包含显然成立。因此

V_l\cap V_r=B.

同时，左右内部 $V_l\setminus B$ 与 $V_r\setminus B$ 之间没有边。否则，包含该边两端的袋无法同时满足两端各自只能出现于本支的事实。两支唯一需要协调的部分恰好就是 $B$ ，并非某个凭直觉挑选的“小集合”。

直觉

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

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

C₆ 的宽度二树分解，以及顶点在袋树中中断后重现的非法分解 — 树分解的运行交性质

例子与边界

常见图与合法性边界

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

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

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

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

树上 Helly 性可以直接证明。任意选定 $T$ 的根，每棵非空连通子树都有唯一的最浅顶点：若有两个不同的最浅点，连接它们的路径会经过更浅的公共祖先，而连通子树必须包含这条唯一路径，矛盾。给定有限、非空、两两相交的子树族，选最浅顶点深度最大的那棵，记其最浅顶点为 $a$ 。对任意另一棵子树，记最浅顶点为 $b$ ，并取两树的一个交点 $z$ 。 $a,b$ 都在根到 $z$ 的路径上，且 $b$ 不比 $a$ 深，所以 $a$ 位于从 $b$ 到 $z$ 的路径上。另一棵子树包含这条路径，因而也包含 $a$ 。故所有子树都有共同顶点 $a$ 。

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

一张可逐袋核验的宽度二分解

取六个顶点和七条边：

V=\{a,b,c,d,e,f\},\qquad E=\{ab,ac,bc,cd,ae,be,ef\}.

它由共享边 $ab$ 的两个三角形 $abc,abe$ ，以及挂在 $c,e$ 上的两个叶子 $d,f$ 组成。下面给出一棵有根分解树，箭头均指向父节点；两条链在 $J$ 汇合，再通向空根 $Z$ 。

左支，由叶到父	右支，由叶到父
$L_0:\varnothing$	$R_0:\varnothing$
$L_1:\{c\}$	$R_1:\{e\}$
$L_2:\{c,d\}$	$R_2:\{e,f\}$
$L_3:\{c\}$	$R_3:\{e\}$
$L_4:\{a,c\}$	$R_4:\{a,e\}$
$L_5:\{a,b,c\}$	$R_5:\{a,b,e\}$
$L_6:\{a,b\}$	$R_6:\{a,b\}$

$L_6,R_6$ 的父节点都是 $J:\{a,b\}$ ，然后依次是 $A:\{a\}$ 与 $Z:\varnothing$ 。共 $17$ 个袋、 $16$ 条分解树边。

逐项核验定义并不需要猜测：七条原图边分别由 $L_2,L_5,R_2,R_5$ 覆盖； $c$ 的出现位置沿 $L_1$ 到 $L_5$ 连续， $e$ 沿 $R_1$ 到 $R_5$ 连续， $d,f$ 各只出现一次； $a,b$ 在两支中的出现位置通过 $J$ 相连，其中 $a$ 还延伸到 $A$ 。顶点覆盖也立即成立。最大袋大小为 $3$ ，所以这份分解宽度为 $2$ 。

给出一份宽度二分解只证明 $\operatorname{tw}(G)\le2$ 。本例还含三角形 $abc$ ，团必须同处一个袋，故 $\operatorname{tw}(G)\ge2$ ，两边合起来才得到树宽恰为 $2$ 。后面的独立集动态规划只需要这份分解的宽度上界，并不需要先证明它最优。

推论与应用

给定宽度 $k$ 的树分解，许多图问题可沿 $T$ 做动态规划。例如求最大独立集时，当前袋中哪些顶点被选中，就是未来需要知道的全部选择信息；每袋至多有 $2^{k+1}$ 种子集。连通性问题还可能需要记录接口顶点之间的连接关系，因此“小袋”没有自动指定唯一正确的状态设计。

只要所得图 minor仍非空，树宽就不增；非空团 minor 因而给出树宽下界。不过排除一个 minor 并不普遍意味着树宽有常数界：所有平面网格都排除 $K_5$ minor，树宽却可以任意大。结构结论需要说明排除的是何种图，以及允许怎样的宽度依赖。

树宽也连接固定参数可解性。如果输入已经带有小宽度分解，算法可立即在接口上计算；如果输入只有原图，寻找分解的时间必须另计。Bodlaender 的定理保证对每个固定 $k$ ，可以在线性于图顶点数的时间内检验树宽是否至多 $k$ ，成功时输出相应分解，但线性系数依赖 $k$ 。[2] 这与“任意图的最优树分解可以免费取得”是完全不同的结论。

参考资料

[1] Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017, Chapter 12：树分解与树宽的结构背景。

[2] Hans L. Bodlaender, A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM Journal on Computing 25(6), 1996, pp. 1305–1317。Theorem 1.1（印刷页 1306）给出固定 $k$ 的线性时间结果；Lemma 2.1(i)（印刷页 1307）说明团包含于某个袋。

[3] Hans L. Bodlaender, Treewidth: Algorithmic techniques and results, Technical Report UU-CS-1997-31, 1997，§4：边界与部分解方法。

形式陈述 ​

为什么袋确实是分隔边界 ​

常见图与合法性边界 ​

一张可逐袋核验的宽度二分解 ​

反向链接

形式陈述

为什么袋确实是分隔边界

常见图与合法性边界

一张可逐袋核验的宽度二分解