图论中，无向图的树宽（treewidth）是描述图与树的距离的正整数。树宽为1的图就是树或森林。树宽不大于2的图叫做系列并行图。树宽恰为k的最大图称作k树，树宽不大于k的图称作部分k树。很多有充分研究的图族的树宽也是有界的。

树宽可用几种等价方式正式定义：图的树分解中最大顶点集的大小、图的弦补全中最大团的大小、描述图上追逃对策的港的最大阶数、刺藤（bramble，相互接触的连通子图的集合）的最大阶数。

树宽常用作图算法的参数复杂性分析中的参数。对一般图NP困难的许多算法，将树宽固定于常数时就变得容易了。

树宽的概念最初由提出，叫做“维度”（dimension）。后来，根据树宽和哈德维格数的共同属性，重新发现了树宽。又重新发现了树宽，自此才获得了学界的关注。

定义
图G=(V,\ E)的树分解是结点为X_1,\ \dots,\ X_n的树T，其中X_i都是V的子集，满足下列性质（为避免与G的顶点混淆，“结点”仅指树T的顶点）：

\bigcup_i X_i=V.即，图顶点至少包含在一个树结点中。

若X_i,\ X_j共同包含顶点v，则在X_i到X_j的（唯一）路径上，T的所有结点X_k也都包含v。即，包含顶点v的树结点构成T的连通子树。

对图中每条边(v,\ w)，存在同时包含v、w的子集X_i。即，只有当相应的子树有共同结点时，图顶点才是相邻的。

树分解的宽是其最大集X_i的大小减一。图G的树宽{\rm tw}(G)等于G的树分解的最小宽度，按这定义，最大集的大小减一，树的树宽才能等于一。

等价地，G的树宽等于团数最小的含G弦图中最大团的大小减一。在G中属于X_i的两顶点间添加一条边，就可得到团大小相符的弦图。

树宽也可用港描述，其是在图上定义的追逃对策中逃逸策略的函数。若有至多k+1阶的港——函数\beta，将G中最多k个顶点的集合X映射到G\backslash X的一个连通分量中，并且具有X\subseteq Y\Rightarrow \beta(Y)\subseteq\beta(X)的单调性，就称图G的树宽为k。

，其存在表明图的树宽至少为3]]
使用刺藤（bramble）也可做出类似描述。刺藤是指一族相互接触的连通子图（即共享一个顶点，或由一条边连接）。刺藤的阶数是子图族的最小命中集（hitting set），图的树宽等于刺藤最大阶数减一。

例子
完全图K_n的树宽为n-1。这用树宽的弦图定义很容易看出来：完全图已经是弦图，添加更多边不能减小最大团的大小。

当且仅当至少2顶点的连通图是树，连通图的树宽为1。树的树宽为1，与完全图同理（即它已经是弦图，且最大团大小为2）。反之，若图中有循环，则所有弦补全都至少包括一个由循环的3个连续顶点组成的三角形，由此可见其树宽至少为2。

有界树宽
有界树宽图族
树宽不大于常数k的图称作部分k树。其他具有有界树宽的图族，有仙人掌图、伪森林、系列并行图、外平面图、哈林图、阿波罗尼奥斯网络等。在结构化编程的编译阶段出现的控制流图，树宽也是有界的，使寄存器配置之类任务可在其上高效执行。

平面图的树宽不一定有界，因为n\times n格图是树宽恰为n的平面图。于是，若F是树宽有界的子式闭图族，则它不可能包含所有平面图。反之，若某平面图不能作为F族中图的子式出现，则存在常数k，使F中所有图的树宽不大于k。即，以下3个条件等价：

F是树宽有界图的子式闭图族；

表征了F的有限多禁子式（forbidden minor）中，有一个是平面的；

F是不含平面图的子式闭图族。

禁子式
对每个有限值k，树宽不大于k的图都可用禁子式的有限集表示（即，任意树宽大于k的图，都包含集合中的一个图作为子式）。每个这样的禁子式集都包含平面图。

对于k=1，唯一的禁子式是3-顶点循环图。
对于k=2，唯一的禁子式是4-顶点完全图K_4。

对更大的k，禁子式的增长速度不小于k的平方根指数。但已知的禁子式的大小与数量的上界远高于这个下界。

算法
计算树宽
判断给定图G的树宽是否不大于给定值k的问题，是NP完全的。而当k为任意固定常数时，可在线性时间内识别出树宽为k的图，并为之构造出树宽为k的树分解。这算法的耗时对k是指数级的。

由于树宽在众多领域中的作用，人们开发了计算树宽的各种算法。根据具体的应用，我们可以选择更好的近似率，或运行时间与输入或树宽大小更相关的算法。
下表概述了一些树宽算法。其中，k是树宽，n是输入图G的顶点数。每种算法都能在f(k)\cdot g(n)的时间内输出宽度等于“近似”栏中的分解图。例如，的算法在2^{O(k^3)}\cdot n时间内，要么为输入图G构建树宽不大于k的树分解，要么报告G的树宽大于k。相似地，的算法在2^{O(k)}\cdot n时间内，要么为输入图G构建树宽不大于5k+4的树分解，要么报告G的树宽大于k。在同样运行时间内，将其改进到2k+1。

目前还不知道确定平面图树宽的问题是不是NP完全的，也不知道其树宽能否在多项式时间内计算出来。

实践中，的算法可以确定顶点数最多为100、树宽最多为11的图的树宽，并以最优树宽找到这些图的弦补全。

对更大的图，可以用基于搜索的技术，如分支定界搜索（BnB）与最佳优先搜索，以计算树宽。它们是任意时间算法，提前停止时会输出树宽的上界。

第一个计算树宽的BnB算法叫做QuickBB算法，是Gogate与Dechter提出的。BnB算法的质量在很大程度上取决于所用下限的质量，Gogate与Dechter使用最佳优先搜索改进了QuickBB算法，在某些图上快了一个数量级。

解小树宽图上的其他问题
20世纪70年代初，人们发现，只要图的“维度”有界，就可通过非序列动态规划，高效解决一大类定义在图上的组合优化问题。的研究表明，“维度”等同于树宽。后来，多名学者在80年代末独立观察到，很多对任意图来说NP完全的问题，对树宽有界的图来说，可用动态规划，利用树分解高效解决。
举例来说，k树宽图的着色问题可通过对树分解使用动态规划算法解决。将X_i（树分解的所有集合）的顶点划分为颜色类，算法会结合储存在结点的相似类信息确定着色是否有效、扩展到树分解中所有的子结点。由此产生的算法能在O(k^{k+O(1)}n)时间内找到n顶点图的最优着色，这个时间约能束使问题固定参数可解。

古赛尔定理
对于一大类问题，如果提供具有有界常值树宽的树分解，就可用线性时间算法求解。具体来说，古赛尔定理指出，若图问题可用一元二阶逻辑表为图的逻辑，就可在树宽有界图上用线性时间求解。一元二阶逻辑是一种描述图属性的语言，有下列结构：

逻辑运算，如 \wedge ,\vee ,\neg ,\Rightarrow
成员检验，如e\in E,\ v\in V
对顶点、边、顶点集和/或边集的量词，如\forall v\in V,\ \exists e\in E,\ \exists I\subseteq V,\ \forall F\subseteq E
邻接检验（如u是e的端点），及一些允许优化的扩展。

例如，考虑3着色问题。对图G=(V,\ E)，此问题是说，有没有可能为每个顶点v\in V分配3种颜色中的一种，使得相邻顶点总被分配不同颜色。
这个问题用一元二阶逻辑表为：
: \exists W_1 \subseteq V : \exists W_2 \subseteq V : \exists W_3 \subseteq V : \forall v \in V : (v \in W_1 \vee v \in W_2 \vee v \in W_3) \wedge
: \forall v \in V : \forall w \in V : (v,w) \in E \Rightarrow (\neg (v \in W_1 \wedge w \in W_1) \wedge \neg (v \in W_2 \wedge w \in W_2) \wedge \neg (v \in W_3 \wedge w \in W_3)),
其中W_1,\ W_2,\ W_3分别代表3种颜色的顶点子集。于是，根据古赛尔定理，对具有有界常值树宽的树分解的给定图，3着色问题可在线性时间内求解。

相关参数
径宽
图的径宽也是经过树分解定义的，不过其底树是径图，也可通过区间图定义，类似于由弦图定义树宽。因此，图的径宽总不小于树宽，但只能比树宽大一个对数因子。f的已知最佳区间：对某常数d>0，下界为\Omega(r^d)，上界为
:O \left( \sqrt{ r / \log r} \right).

关于下界中的Ω记号，见大O符号。对有约束的图族，区间也更严。双维理论为这些图族上的很多图优化问题提供了高效算法。
哈林格定理提供了无限图的树宽与格子式大小关系的类比。

直径与局部树宽
若图族F在取子图下封闭，其中图的树宽有以直径为函数的上界，则称它们具有有界局部树宽或直径树宽性。若假设该族在取图子式下也封闭，则当且仅当F的一个禁子式是顶点图（apex graph），F才有有界的局部树宽。这一结果的最初证明显示，无顶点子式图族的树宽作为直径的函数，最多呈2倍指数增长；后来降为单倍指数增长，最后抵达线性的界。有界局部树宽与双维理论密切相关，一阶逻辑中可定义的图属性都可用略微超线性的时间来决定一个无顶点子式图族。

对取子式不封闭的图族，也有可能具有有界的局部树宽。特别是对一族有界度图来说，这是一定成立的，因为有界直径子图的大小有界。另一个例子是1-平面图，即可在平面上绘制的、每条边有1交叉的图，以及更广义地说，可在亏格有界的曲面上绘制的、每条边有一定交叉点的图。与局部树宽有界的子式闭图族一样，这一特征为图的高效近似算法指明了方向。

哈德维格数与S函数
定义了一类叫做“S-函数”的图参数，其中包括树宽。这些函数从图映射到整数，无边图映射到0，具有子式单调性（若对函数f、G的子式H，总有f(H)\le f(G)，则称f是“子式单调”的），在与所有现有顶点相邻的位置添加新顶点时，函数值加1，并从团分隔两侧的两子图中取较大值。所有此种函数的集合在逐元素最小、最大化运算下，形成了完全格，当中的顶元素是树宽，底元素是哈德维格数，即给定图中最大完全子式的大小。

注释
参考文献
*.
*.
*.
*.
*.
*
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.

树宽