树宽(tree width),理学-数学-图论-次模函数-线图,图的所有树分解的宽度中的最小值。图的树分解是这样一棵树,是树的顶点,式中每个是的一个满足下列性质的子集:①所有的并等于;②如果和均包含点中的一个点,则中所有在路上的也包含点;③对图中每条边,都存在一个同时包含和。树分解的宽度等于最大的集合的基数减一。图的树宽是指图的所有树分解的宽度中的最小值,记为。树宽的概念最初是由Umberto Bertelé和朗切斯科·布里奥斯奇(Francesco Brioschi)提出的,当时命名为尺寸(dimension)。后来被R.哈林(Rudolf Halin)在1976年重新提及。之后又被N.罗伯逊(Neil Robertson)和P.西摩尔(Paul Seymour)于1984年提起,至今已被广泛研究。已经证明,对于一般图,计算其树宽是NP困难的。不过对于给定整数,存在多项式时间算法来判断一个图的树宽是否至多为。