树宽

树宽（treewidth）用树分解中所需的最大局部顶点组大小衡量图的结构复杂度。它衡量的是把图组织成一棵“相互衔接的局部袋子树”所需保留的信息量；图中顶点的总数、最大度和边数都不能单独决定树宽。

四边形环 $1-2-3-4-1$ 可以用两个袋 $\{1,2,3\}$、$\{1,3,4\}$ 相连表示。四条边的端点各自在某个袋中同时出现，顶点一、三在两个相邻袋中连续出现。最大袋大小是三，对应分解宽度二。袋内的一、三无需在原图相邻，袋是需要一起保留的顶点组，不是原图中必须存在的团。

同一原图顶点可以在多个袋中出现；两个袋通过共享的顶点一、三衔接。

树分解的三个条件

设 $G=(V,E)$ 为有限无向简单图。树分解由一棵非空有限树 $T$ 和每个树节点 $t$ 对应的袋 $B_t\subseteq V$ 组成，要求：

• 每个原图顶点至少在一个袋中出现，即 $\bigcup _t{B}_t=V$；
• 每条原图边 $uv\in E$ 的两个端点同时属于某个袋；
• 对每个 $v\in V$，含 $v$ 的树节点集合在 $T$ 中连通。

第三项也称运行交集条件：顶点在一条袋间路径的两端出现，就必须在整条路径上出现。分解的宽度为 $\underset{t}{max}|B_t|-1$，树宽 $\mathrm{tw}(G)$ 是所有树分解宽度的最小值。

本文约定空顶点图树宽为负一，可用单个空袋表示；非空无边图树宽为零，用单顶点袋组成任意树即可。文献有时把空图树宽也约定为零，比较边界数值时应说明。

只有覆盖边还不够。例如把三角形的三条边分别放进袋 $\{1,2\},\{2,3\},\{1,3\}$，按此顺序连成路径。虽然边全被覆盖，顶点一却在首末袋出现而中间缺失，这不是树分解。若忽略连续出现的条件，就会把三角形误判为宽度一。

宽度给出的低度顶点

一个非空图若有宽度至多 $k$ 的树分解，就至少有一个度数至多 $k$ 的顶点。证明如下。若相邻袋之一包含于另一个，可以收缩这条树边、保留较大的袋，三个条件仍成立。反复收缩后，或只剩一个袋，此时任意顶点的邻居均在同袋内；或取一个叶袋 $B_t$，它不包含于相邻袋 $B_s$，所以有 $v\in B_t\setminus B_s$。运行交集条件迫使 $v$ 只在叶袋出现。覆盖边条件又迫使它的所有邻居都在 $B_t$ 内，因此 $$\mathrm{deg}(v)\le |B_t|-1\le k.$$ 这个论证还适用于任意非空诱导子图：只需从所有袋里删去不属于该子图的顶点，宽度不会增加。

四边形环的每个顶点度数均为二，所以它不可能有宽度一的分解；开头已经构造宽度二的分解，故树宽恰为二。完全图 $K_4$ 的最小度为三，同理树宽至少三，而单个四元素袋达到三，故恰为三。

树的宽度与边界信息

对一棵至少有一条边的树，指定根。根对应单元素袋，每个非根顶点 $v$ 对应 $\{v,\mathrm{parent}(v)\}$，袋之间沿原树的父子关系相连。每条边被子袋覆盖；含同一顶点的袋由它自己的袋和孩子袋组成一棵星，因而连通。最大袋大小二，宽度至多一；有边又排除宽度零，故树宽为一。森林的各分量分解可任意连在一起，结论仍成立。

中心顶点度数为三，但任何袋只含至多两个顶点，树宽仍为一。

变式。 一百个叶子连接同一个中心的星图树宽是多少？仍为一：沿用同一构造即可。最大度一百并没有迫使袋很大。反过来，从图中取一棵生成树也不能证明原图树宽为一，因为生成树省略的边仍须在原图的分解中被覆盖。

袋间边也给出分隔。删去分解树的一条边，将袋分成两侧；若一个顶点在两侧都出现，它必须属于两个端袋的交。于是删掉这个交集后，不可能有原图边连接两侧剩余顶点，否则覆盖该边的袋会迫使某个端点跨侧出现。这就是动态规划可只通过小交集交换状态的原因。例如袋中有 $k+1$ 个二元变量时，局部赋值有至多 $2^{k+1}$ 种，但具体算法还须处理其约束、合并和输入分解的成本。树宽小提供结构条件，不自动给出所有问题的统一运行时间。