一個(gè)圖G=（V,E）的樹分解是將結(jié)點(diǎn)集V的子集作為樹T的節(jié)點(diǎn),使得在T上任意一條路徑上的兩個(gè)端節(jié)點(diǎn)的交集包含于該路徑上的任意一個(gè)節(jié)點(diǎn)中。將T上最�。ü�(jié)點(diǎn)）對(duì)應(yīng)子集的元素個(gè)數(shù)減1定義為分解樹T的寬度,用寬度最小的分解樹T的樹寬度定義圖G的樹寬度。一個(gè)合取范式（Conjunctive Normal Form,CNF）公式F可以用一個(gè)二分圖G=（V∪C,E）表示（公式的因子圖）,其中變?cè)Y(jié)點(diǎn)集V對(duì)應(yīng)公式F中的變?cè)?子句結(jié)點(diǎn)集C對(duì)應(yīng)公式F中的子句集,變?cè)谧泳渲械恼ㄘ?fù)）出現(xiàn)用實(shí)（虛）邊表示。忽略公式因子圖中邊上的符號(hào),得到一個(gè)二分圖。文中研究了圖的樹分解算法,并將樹分解算法應(yīng)用到CNF公式的因子圖樹分解。通過實(shí)驗(yàn)觀察公式因子圖的樹寬度與求解難度之間的聯(lián)系。 

【文章來源】：計(jì)算機(jī)科學(xué). 2020,47(05)北大核心CSCD

【文章頁(yè)數(shù)】：8 頁(yè)

【部分圖文】：

圖G=(V,E)的一棵分解樹

圖G=(V,E)的弦圖

一個(gè)CNF公式可以表示為一個(gè)因子圖,這類圖的一側(cè)是以布爾變?cè)癁椴紶栕冊(cè)旤c(diǎn),而另一側(cè)則是以子句集為子句頂點(diǎn)。當(dāng)某個(gè)布爾變?cè)霈F(xiàn)在某個(gè)子句中時(shí),表示有一條邊連接該變?cè)旤c(diǎn)和子句頂點(diǎn),其中用實(shí)線表示變?cè)谧泳渲姓霈F(xiàn),用虛線表示變?cè)谧泳渲胸?fù)出現(xiàn)。將CNF公示轉(zhuǎn)換為因子圖時(shí),用矩形表示子句頂點(diǎn),用圓形表示變?cè)旤c(diǎn)。圖1展示了3-CNF公式的一個(gè)實(shí)例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公式的因子圖中,如果忽略邊上的符號(hào),則得到一個(gè)二分圖。對(duì)于二分圖G=(V∪C,E),如果對(duì)于任意的兩個(gè)不同結(jié)點(diǎn)c,c′∈C,其至多有一個(gè)公共鄰接結(jié)點(diǎn),即|N(c)∩N(c′)|≤1,則稱此二分圖是線性二分圖。其中,N(c)表示結(jié)點(diǎn)c在圖中的鄰接結(jié)點(diǎn)集。線性二分圖概念的引入主要針對(duì)線性CNF公式。一個(gè)CNF公式F稱為線性公式,如果任意兩個(gè)不同子句至多含有一個(gè)公共變?cè)�。文獻(xiàn)[23-25]已經(jīng)證明:限制CNF公式為線性公式,其可滿足性判定問題仍然是NP-完全的。

【參考文獻(xiàn)】：
期刊論文
[1]一個(gè)正則NP-完全問題及其不可近似性[J]. 許道云,王曉峰.  計(jì)算機(jī)科學(xué)與探索. 2013(08)
[2]隨機(jī)可滿足實(shí)例集上警示傳播算法的收斂性[J]. 王曉峰,許道云,韋立.  軟件學(xué)報(bào). 2013(01)
[3]k-LSAT（k≥3）是NP-完全的（英文）[J]. 許道云,鄧天炎,張慶順.  軟件學(xué)報(bào). 2008(03)



本文編號(hào)：3145747