树分解

树分解用一棵树组织图的一系列顶点集合，使每条原图边都出现在某个集合中，并保证同一个顶点出现的位置在树上连成一片。它把复杂图拆成相互重叠的小部分，是许多图算法中动态规划的基础。

定义

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

• 顶点覆盖：$\bigcup _{t\in V(T)}{B}_t=V$。
• 边覆盖：对每条边 $uv\in E$，有某个袋同时含 $u,v$。
• 连通性：对每个 $v\in V$，含 $v$ 的树节点构成非空连通子树。

分解宽度为 $\underset{t}{max}|B_t|-1$。对非空图，所有树分解宽度的最小值称为树宽 $\mathrm{tw}(G)$。第三条也叫运行交集条件：沿两个含 $v$ 的袋之间的树路径，所有袋都必须含 $v$。

一个星图的分解

设原图有中心 $c$ 和四个叶子 $a,b,d,e$，边是 $ca,cb,cd,ce$。取四个袋 $$B_a=\{c,a\},B_b=\{c,b\},B_d=\{c,d\},B_e=\{c,e\}.$$ 把这些袋作为树节点，以 $B_a$ 为中心连接其他三个袋。每条原图边分别被一个袋覆盖；中心顶点 $c$ 出现在所有袋中，形成连通的整棵树；每个叶子只出现在一个袋中。因此这确是树分解，宽度为 $2-1=1$。

右侧每个袋覆盖原图的一条边；所有袋都含中心顶点 c。

由于原图含有边，任何树分解都必须有袋同时容纳该边的两个端点，因此宽度至少为 1。所构造的宽度又等于 1，故该星图树宽为 1。这个下界依赖边覆盖条件，不能只从图的顶点数推出。

袋和原图的区别

袋不是原图的顶点；它是包含若干原图顶点的集合。分解树的边也不是原图的边。例如原图中的 $a,b$ 不相邻，而袋 $B_a,B_b$ 可以在分解树中相邻。第三条条件尤其重要：如果同一个顶点出现在两个袋中，但它们之间的路径上有袋漏掉该顶点，就不是合法树分解。

将分解树限制为路径，就得到路径分解，最小宽度称为路径宽。任何有边的树都给出原图宽度至多为一的分解：对每条边建一个含其端点的袋，并适当连接袋；含边的树宽至少为一。具体算法在袋上保存的状态和运行时间，还取决于要解决的问题。