Tree Decomposition

释义 Definition

（图论/算法）树分解：把一个图按某种规则“拆成”一棵树状结构（由若干“袋子/子集”组成），使得图的边与顶点关系能在这棵树上被一致地表示。常用于定义与计算树宽（treewidth），并用来把一些在一般图上很难的问题，在“树状程度较高”的图上变得更容易求解。

例句 Examples

A tree decomposition can make some hard graph problems easier to solve.
树分解可以让一些困难的图问题更容易求解。

Using a tree decomposition of small width, we can run dynamic programming to compute the optimal solution efficiently.
利用一个宽度较小的树分解，我们可以用动态规划高效地计算最优解。

发音 Pronunciation

/triː ˌdiːkəmˈpoʊzɪʃən/

词源 Etymology

tree 源自古英语 trēow / trēo（树、木材）；decomposition 来自拉丁语构词：de-（分开、向下）+ componere（组合、放在一起）→ “拆开/分解”。作为图论术语，tree decomposition 在20世纪后期的算法图论中被系统化使用，尤其与 Robertson 与 Seymour 的图小子（Graph Minors）研究及“树宽”概念紧密相关。

相关词 Related Words

• Treewidth
• Bag
• Separator
• Chordal
• Clique
• Minor
• Dynamic Programming
• Graph

文学与著作 Literary Works

• Graph Minors. II. Algorithmic aspects of tree-width — Neil Robertson & P. D. Seymour（提出并系统讨论与树宽相关的树分解思想）
• Graph Theory — Reinhard Diestel（常用 “tree-decomposition(s)” 讲解树宽与结构理论）
• Parameterized Algorithms — Marek Cygan 等（将树分解作为参数化算法与动态规划的重要工具）
• Algorithmic Graph Theory and Perfect Graphs — Martin Charles Golumbic（在算法图论语境中涉及相关分解与结构方法）