树分解

树分解是图子式理论中发展起来的一个重要概念。图的树分解由于其本身的特性使得它在算法设计中有着极其重要的意义。

研究概述无论是在网络还是人工智能应用中，抑或社会经济领域，都存在着大量的组合优化问题，其中很多都是NP完全问题。求解这些NP完全问题，目前还没有有效的确定性算法。过去在应用领域多采用近似算法求解，某些近似算法在实际应用中也确实能取得非常好的效果。近年来发展起来的参数计算理论对一些NP问题的求解提供了一些新的思路。伴随着参数计算理论的发展，也产生了一些新的算法设计技巧和方法，如核心化、有限搜索树等。而在20世纪80年代发展起来的图子式理论也为参数算法的研究提供了有力的支持。图子式理论从一开始就与算法理论密切相关，并对算法研究产生了深远的影响。一方面借助图子式理论可以用一种非构造的方式从理论上证明某些问题的参数算法的存在性；另一方面图子式理论也发展出一些有效的算法设计技术，其中图的树宽和图的树分解是图子式理论中引入的两个重要概念。图的树宽和树分解的引入给算法的分析和设计带来了一些新的思路。某些NP问题，若将其限定在有限树宽的图中，则其求解是可行的。也就是说，通过对图进行树分解，若图的树宽是有限的，则存在有效的多项式求解算法，这对于很多场合的实际应用问题有着重要的意义。1

图的树宽定义图子式理论是20世纪80年代发展起来的一个重要的图理论分支，其理论体系散见于从1983年开始直至现在的20余篇论文中。从一开始，图子式理论就受到了算法研究者的密切关注。参数计算研究的先驱Fellows等人在20世纪80年代末就研究了图子式理论在算法设计和分析中的应用，借助于该理论对众多组合优化问题的判定问题给出了其多项式判定算法的存在性证明，并研究了如何将判定算法转化为求最优解的构造性算法的方法。例如，对于最多叶子生成树问题，给定一个图集F，若F 中的图没有哪一个具有一棵生成树，使得该生成树有大于等于k个叶子节点，则根据子式运算的规则，图集F中任意图的子式也不会有叶子节点数大于等于k 的生成树，这种特性称为图集F 关于子式运算封闭。那么根据图子式定理，图集F 的障碍集是有限的，而且可以在多项式时间内识别出这些障碍集，因此最多叶子生成树问题可以在多项式时间内判定。

图的树分解算法第一类是利用消元顺序来构造树分解的启发式算法。所谓消元就是在无向图G中删除一个节点v 以及与节点v 关联的边，同时在剩下的图中补充一些边，使得v原来的邻节点能构成一个团。通过在初始的图G 中逐个消元图G 的所有节点，就可以得到一个消元顺序，根据这个消元顺序便能构造出图G 的一个树分解。问题的关键在于不同的消元顺序可以得到不同的树分解，而求解最优消元顺序也是NP难的，所以也需要采用启发式方法，如最大势搜索及其改进算法、词典广度优先搜索、最小缺边搜索，以及其它一些利用消元顺序的启发式算法。

第二类是利用割集来构造树分解的启发式算法，即通过在初始图中寻找一些割集来构造树分解。所谓割集就是连通图G 的节点集的一个子集，记为S，若在原图G 中删除S 所包含的节点和关联的边，则剩余图变为至少两个连通分量。这样的节点集S 称为图G 的一个割集。2

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所