Pathwidth

释义 Definition

Pathwidth（路径宽度）：图论中的一个“宽度”参数，用来衡量一个图在结构上有多接近“一条路径”。它基于路径分解（path decomposition）：把图的顶点分配到按顺序排列的一串“袋子（bags）”里，使得每条边的两个端点能在某个同一袋子中出现，并且每个顶点出现的袋子位置在序列中必须连续。路径宽度通常定义为“袋子中顶点数的最大值减 1”的最小可能值。
（在不同语境中也可能讨论其他“宽度”概念，但最常见的是上述图论定义。）

发音 Pronunciation

/ˈpæθ.wɪdθ/

例句 Examples

Pathwidth measures how close a graph is to a path.
路径宽度衡量一个图在结构上有多接近一条路径。

If a graph has small pathwidth, many problems can be solved efficiently using dynamic programming on a path decomposition.
如果一个图的路径宽度很小，很多问题就可以在路径分解上用动态规划高效求解。

词源 Etymology

pathwidth 由 path（路径） + width（宽度） 构成，是图论与算法研究中为类比 treewidth（树宽） 而发展出的术语：把“树状结构上的分解”进一步限制为“路径状结构上的分解”，对应得到“路径宽度”。

相关词 Related Words

• Bandwidth
• Graph Minor
• Parameterized Complexity
• Path Decomposition
• Tree Decomposition
• Treewidth
• Width

文献与作品 Literary Works

• Graph Minors. III. Planar tree-width（Robertson & Seymour）：在“图小定理（Graph Minors）”系列研究脉络中讨论与宽度参数相关的思想（常与 treewidth/pathwidth 体系并置理解）。
• Parameterized Algorithms（Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh）：介绍以 treewidth/pathwidth 等结构参数为核心的参数化算法方法。
• Algorithmic Graph Theory 相关教材与讲义（多版本、多作者）：在“图分解 + 动态规划”的章节中常将 pathwidth 作为 treewidth 的重要特例与对照参数出现。