树宽
描述图与树的距离的正整数 / 維基百科,自由的 encyclopedia
图论中,无向图的树宽(treewidth)是描述图与树的距离的正整数。树宽为1的图就是树或森林。树宽不大于2的图叫做系列并行图。树宽恰为k的最大图称作k树,树宽不大于k的图称作部分k树。很多有充分研究的图族的树宽也是有界的。
树宽可用几种等价方式正式定义:图的树分解中最大顶点集的大小、图的弦补全中最大团的大小、描述图上追逃对策的港的最大阶数、刺藤(bramble,相互接触的连通子图的集合)的最大阶数。
树宽常用作图算法的参数复杂性分析中的参数。对一般图NP困难的许多算法,将树宽固定于常数时就变得容易了。
树宽的概念最初由Umberto Bertelè and Francesco Brioschi (1972)提出,叫做“维度”(dimension)。后来,Rudolf Halin (1976)根据树宽和哈德维格数的共同属性,重新发现了树宽。Neil Robertson and Paul Seymour (1984)又重新发现了树宽,自此才获得了学界的关注。[1]:354–355