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