树宽图论中,无向图的树宽(treewidth)是描述图与树的距离的正整数。树宽为1的图就是树或森林。树宽不大于2的图叫做系列并行图。树宽恰为k的最大图称作k树,树宽不大于k的图称作部分k树。很多有充分研究的图族的树宽也是有界的。 树宽可用几种等价方式正式定义:图的树分解中最大顶点集的大小、图的弦补全中
图子式2014 (英语) . Demaine, Erik D.; Hajiaghayi, MohammadTaghi, Diameter and treewidth in minor-closed graph families, revisited, Algorithmica, 2004, 40 (3):
径宽through treewidth. Acta Cybernetica. 1994a, 11: 1–2. Bodlaender, Hans L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM
带宽 (图论)Böttcher, J.; Pruessmann, K. P.; Taraz, A.; Würfl, A. Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs. European Journal
图同构计量被不随节点数增长的常数上限约束时,图同构问题可被多项式时间求解: 图的树分解(英语:Tree decomposition)的宽度(英语:Treewidth) 亏格 最大的节点度数 (这被认为是图同构理论迄今为止取得的最重要突破性进展之一) 图的邻接矩阵或任何一种拉普拉斯矩阵的特征值的最大重数 惠特尼图同构定理是由Hassler