图的树分解算法及其应用

摘要：

一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中.将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度.一个合取范式(Conj unctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示.忽略公式因子图中边上的符号,得到一个二分图.文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解.通过实验观察公式因子图的树宽度与求解难度之间的联系.

关键词：树分解、CNF公式、树宽度、求解难度

所属期刊栏目：47

资助基金：国家自然科学基金61762019,61862051

在线出版日期：2020-05-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：51-58