树分解（图论） ⇐ 文章草稿

[Guest]

在图论中，“树分解”是图（图论）|图到树（图论）|树的映射，可以用来确定图的树宽并计算图上的某些问题加速了。

== 定义 ==
树分解背后的直觉是，给定图（图论）|graph G 的节点表示为树分解的子树，其中 G 中的节点表示为树分解的子树。 math> 彼此相邻当且仅当它们的子树重叠时才说谎。这意味着G形成了子树的交集图的子图。完整的交集图是弦图。

== 正式定义 ==
G = (V,E) 的“树分解”是一对 (X,T)，其中 T = (I,F)< / math> 是一棵树，X = \{X_i~|~i \in I\} 是一个族（数学）|节点子集族（图论）|节点集 图中的 V，称为口袋，是这样的：

* \bigcup_{i \in I} X_i = V。
* 对于所有边（图论）|边 (v,w) \in E 都有一个 i \in I 和 v,w \in X_i< / 数学>。
* 对于所有 i,j,k \in I，以下情况适用：如果 j 位于从 i 到 k< 的路径上T 中的 /math>，然后 X_i \cap X_k \subseteq X_j。

==文献==
* * *


类别：基本概念（图论）
类别：树木和森林
类别：图论