摘要
一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度。一个合取范式(Conjunctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示。忽略公式因子图中边上的符号,得到一个二分图。文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。
A tree decomposition of the graph G=(V,E)refers to taking a subset of the node set V as a node of the tree T,to make the intersection of the two endpoints on any path of T included in any node on the path.The number of elements of the mini-mum(node)corresponding subset on T minus 1 is defined as the width of the decomposition tree T,and the tree width of the graph G is defined by the tree width of the decomposition tree T with the smallest width.The CNF formula F can be represented by a bipartite graph G=(V∪C,E)(factor graph of the formula),where the variable node set V corresponds to the variable set,and the clause node set C corresponds to the clause set in the formula F.The positive(negative)occurrence of the element in the clause is represented by the real(virtual)side.In order to study the bipartite graph,the symbols on the edges of the formula factor graph are ignored.This paper studies the tree decomposition algorithm of graphs and applies the tree decomposition algorithm to the factor graph tree decomposition of CNF formula,aiming to explore the relationship between the tree width of the formula factor graph and the difficulty of the solution-finding through experiments.
作者
雷莹
许道云
LEI Ying;XU Dao-yun(College of Computer Science and Technology,Guizhou University,Guiyang 550025,China)
出处
《计算机科学》
CSCD
北大核心
2020年第5期51-58,共8页
Computer Science
基金
国家自然科学基金(61762019,61862051)。
关键词
树分解
CNF公式
树宽度
求解难度
Tree decomposition
CNF formula
Tree width
Difficulty of solution-finding
