径宽
維基百科,自由的 encyclopedia
图论中,图G的径分解(path decomposition)是G的“加粗”路径图表示,[1]G的径宽(pathwidth)是衡量形成G的路径被加粗的程度。更正式地说,径分解是G的顶点子集序列,使每条边的端点出现在某一子集中,并使每个顶点都出现在子集连续子序列中,[2]径宽等于这样的分解中最大集的大小减一。 径宽也叫做区间厚度(interval thickness,等于G的区间父图中的最大团大小减一)、顶点分隔数(vertex separation number)或结点搜索数(node searching number)。[3]
径宽与径分解同树宽、树分解关系密切,在图子式理论中起关键作用:在图子式下封闭、不含所有森林的图族可描述为径宽有界,[2]子式闭图族的一般结构理论中出现的“涡”(vortex)的径宽也有界。[4]径宽与径宽有界图在超大规模集成电路设计、图绘制、计算语言学等领域也有应用。
计算任意图的径宽、甚至精确近似径宽都是NP困难的。[5][6]不过,这问题是固定参数可解的:测试图的径宽是否为k,耗时与图的大小呈线性关系,而与k呈上指数关系。[7]另外,对树之类的特殊图,径宽可在多项式时间内算得,而不依赖于k。[8][9] 对图的径分解使用动态规划,可以将图算法中很多问题在径宽有界图上高效解决。[10]径分解也可测量树宽有界图上动态规划算法的空间复杂度。[11]