树分解

树分解，属于分解法（Decomposition Method）的一种，也被称为集团树，连接树和连接树，是将图形映射到相关树（Related Tree）的一种方法。它的主要特性是可以有效地计算原始图的某些属性（例如，独立多项式）。 图的树分解不是唯一的，也不需要与原始图同构。树分解常常与树的宽度（Treewidth，简称树宽）的概念联系在一起。在最佳树分解中，映射到任何树顶点的原始图顶点数被称为树宽。

如图所示，假设现有图G =（V，E），G的树分解是一对（T，χ），其中T =（N，F）是树，并且χ：N→2V为每个节点分配一组顶点 （称为节点的包），满足以下条件：

1.对于每个顶点v∈V，存在节点i∈N使得v∈χ（i）。

2.对于每一条边（v，w）∈E，存在一个i∈N且v∈χ（i）且w∈χ（i）。

3.对于每个i，j，k∈N：如果j位于i和k之间的路径上，则χ（i）∩ χ（k）⊆ χ（j）。

树分解的宽度定义为maxi∈N| x（i）| -1，并且图的树宽是所有树分解中的最小宽度。

该图例对应的树分解如下图所示。

AI中的寻路算法主要分盲目式搜索和启发式搜索两种，同图论中的最短路径问题相联系，在图论的数据结构上进行实现。图论中的深度优先搜索算法（DFS）和广度优先搜索算法（BFS）以及Dijksrta最短路径贪心算法都属于盲目式搜索算法。

在AI和概率推理领域中，树分解又称为团树，可以用来提高推理效率，并且给约束满足问题（constraint satisfaction problem）和 NP-hard 问题提供了求解答案，提高了图论在AI方面的效率，比如优化了机器人寻路的方案。

【描述来源：Abseher, M., Dusberger, F., Musliu, N., & Woltran, S. (2015). Tree Decomposition Features.】

发展历史

在20世纪70年代初期，人们观察到，只要图有一个有界的维度和一个与树宽相关的参数，就可以通过非连续的动态规划来有效地解决在图上定义的大类组合优化问题。

1976年，Rudolf Halin提出了树分解和树的宽度的概念，表明网格可以具有任意数值的树宽。 1984年，树分解的概念被Neil Robertson和Paul Seymour重新发现，并且已经被其他许多作者研究过。

后来，一些作者在20世纪80年代末独立观察到，使用这些图的树分解，以及对有界树的图的动态编程可以有效地解决许多任意图的NP完全算法问题。

1990年，Reinhard Diestel解决了单纯树分解的深度问题，使得树分解的概念得以优化。

2013年，Chandra Chekuri和Julia Chuzhoy改进了树分解理论，并且提出了多项式时间算法 （poly-time algorithm）。

主要事件

发展分析

瓶颈

当且仅当图的树宽最多为4，对于任何非负整数k，对于树宽至多为k的图类，存在有限的一组约化规则。但是对于k> 4，基于约简规则的算法可能需要大的（k个指数）存储器。所以仅对于树宽最多为4的图存在实际的线性算法并且可以通过有限的归约规则集来寻找最优的树分解。这种情况导致目前仍然缺少实用的树宽计算算法。

另外在NP-hard问题中，除非P = NP，否则不存在在给定图G计算tw（G）的加法常数内的宽度的树分解的多项式时间算法。

此外，在动态编程中，内存的容量也会成为树分解算法的瓶颈。

未来发展方向

树分解法可用于求解约束满足问题（constraint satisfaction problem）和 NP-hard 问题，目前更专注于生成最小宽度的树分解，未来更适合用于社交图数据（social graph data）的处理，有利于改进图形建模和改进对现实网络数据的推理。

Contributor：Tiange Wang