树宽

树宽是衡量在最优树分解中映射到任何树顶点的原始图顶点的数量的度量。确定任意图的树宽是一个 NP 难问题。然而，许多有界树宽图上的 NP 难问题可以在多项式时间内解决。

一个空图的树宽为 0，一个树或森林的树宽为 1，树宽至多为 2 的图对应于串并联图。每个Halin 图的树宽为 3 (Bodlaender 1988)。

非连通图的树宽等于其连通分量的树宽的最大值。

树宽为 的极大图称为 -树，而树宽 的图被称为部分 -树。

树宽 的图可以用有限的禁用次子图集来表征，如下表所示。对于 的情况，已知超过 75 个结构差异很大的最小禁用次子图 (Sanders 1993, Sanders 1995, Chlebiková 2002)。

树宽界限	禁用次子图
1
2
3	, 八面体图 , 棱柱图 , 瓦格纳图
4	未知的有限数量的次子图；至少已知 75 个

乱数是图的度量（gonality）的最强大的已知下界，并且满足

(1)

其中 是顶点连通度， 是边连通度， 是乱数，而 是 的度量 (Harp et al. 2020, Echavarria et al. 2021)。

特殊情况包括

			(2)
			(3)
			(4)
			(5)
			(6)
			(7)
			(8)

其中 表示任何树， 任何Halin 图， 是一个循环图， 是一个完全图， 是一个完全二分图，并且 是一个 网格图。