树分解与树宽

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

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

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

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

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

bag 不必在原图中诱导连通子图公理库子图Subgraph从母图删除顶点或边、同时保留剩余边端点关系所得的图。或团。仅满足边覆盖也不够：若同一顶点出现在分解树两端却不出现在中间袋，局部结果无法一致拼合。树分解也通常不唯一，宽度只取所有合法分解中的最优值。

给定宽度 $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 型元定理需要额外构造和逻辑假设，不是定义本身的直接同义词。