图的树分解算法及其应用

发布时间：2021-04-18 15:51

　　一个图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公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。 

【文章来源】：计算机科学. 2020,47(05)北大核心CSCD

【文章页数】：8 页

【部分图文】：

图G=(V,E)的一棵分解树

图G=(V,E)的弦图

一个CNF公式可以表示为一个因子图,这类图的一侧是以布尔变元集为布尔变元顶点,而另一侧则是以子句集为子句顶点。当某个布尔变元出现在某个子句中时,表示有一条边连接该变元顶点和子句顶点,其中用实线表示变元在子句中正出现,用虚线表示变元在子句中负出现。将CNF公示转换为因子图时,用矩形表示子句顶点,用圆形表示变元顶点。图1展示了3-CNF公式的一个实例F=(C1∧C2∧C3∧C4∧C5∧C6)的因子图,其中C1=(x3∨x4∨?x5),C2=(?x1∨?x4∨x5),C3=(x1∨x2∨?x5),C4=(?x1∨?x2∨x3),C5=(?x1∨?x2∨?x4),C6=(x1∨x2∨x3)。在CNF公式的因子图中,如果忽略边上的符号,则得到一个二分图。对于二分图G=(V∪C,E),如果对于任意的两个不同结点c,c′∈C,其至多有一个公共邻接结点,即|N(c)∩N(c′)|≤1,则称此二分图是线性二分图。其中,N(c)表示结点c在图中的邻接结点集。线性二分图概念的引入主要针对线性CNF公式。一个CNF公式F称为线性公式,如果任意两个不同子句至多含有一个公共变元。文献[23-25]已经证明:限制CNF公式为线性公式,其可满足性判定问题仍然是NP-完全的。

【参考文献】：
期刊论文
[1]一个正则NP-完全问题及其不可近似性[J]. 许道云,王晓峰.  计算机科学与探索. 2013(08)
[2]随机可满足实例集上警示传播算法的收敛性[J]. 王晓峰,许道云,韦立.  软件学报. 2013(01)
[3]k-LSAT（k≥3）是NP-完全的（英文）[J]. 许道云,邓天炎,张庆顺.  软件学报. 2008(03)



本文编号：3145747