Path Decomposition

释义 Definition

路径分解（Path Decomposition）：图论中的一种表示方法，把一个图的顶点集合组织成按顺序排列的一串“袋（bags）”，使得每条边的两个端点会同时出现在某个袋中，并且每个顶点出现在这些袋中的位置必须形成一个连续区间。常用于定义与研究路径宽度（pathwidth）等结构参数。（该短语在一般语境下也可直译为“路径的分解/拆分”，但最常见的是图论义项。）

发音 Pronunciation (IPA)

/pɑːθ ˌdiːkəmˈpoʊzɪʃən/

例句 Examples

A path decomposition can help us analyze a graph step by step.
路径分解可以帮助我们一步一步地分析一个图。

Using a path decomposition of small width, the algorithm becomes more efficient on sparse graphs.
利用宽度较小的路径分解，该算法在稀疏图上会更高效。

词源 Etymology

path 来自古英语 pæþ，意为“道路、路径”；decomposition 来自拉丁语系词根 *de-*（“向下、分开”）+ componere（“组合、构成”），引申为“分解”。在图论中，“path decomposition”强调用“像路径一样的线性顺序”来组织分解结构。

相关词 Related Words

• Bag
• Tree Decomposition
• Pathwidth
• Treewidth
• Graph
• Separator
• Minor
• Dynamic Programming

文学与著作 Literary Works

• Diestel, **Graph Theory**（多版教材中讨论树分解、路径分解及相关宽度参数）
• Robertson & Seymour, Graph Minors 系列论文（图结构理论背景下与分解思想相关）
• Bodlaender, “A Tourist Guide through Treewidth”（综述性文章中涉及路径/树分解与宽度概念）
• Cygan et al., **Parameterized Algorithms**（参数化算法中常以分解为工具进行动态规划）