一個圖G=（V,E）的樹分解是將結點集V的子集作為樹T的節(jié)點,使得在T上任意一條路徑上的兩個端節(jié)點的交集包含于該路徑上的任意一個節(jié)點中。將T上最�。ü�(jié)點）對應子集的元素個數減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