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