NPC問(wèn)題中幾個(gè)基本定理的證明

郭 蕾

(常州紡織服裝職業(yè)技術(shù)學(xué)院信息技術(shù)系，江蘇 常州 213164)

NPC問(wèn)題中幾個(gè)基本定理的證明

郭 蕾

(常州紡織服裝職業(yè)技術(shù)學(xué)院信息技術(shù)系，江蘇 常州 213164)

就NPC問(wèn)題(NP-complete，NP完全問(wèn)題)中的幾個(gè)基本定理給出了證明。首先從基本的團(tuán)問(wèn)題、SAT問(wèn)題和圖的著色問(wèn)題入手，證明了它們都屬于NPC問(wèn)題，再利用獨(dú)立集、頂點(diǎn)覆蓋、有向圖、團(tuán)、SAT和圖的著色等問(wèn)題本身的內(nèi)在關(guān)系，對(duì)其他的定理做了一一證明。

NPC問(wèn)題；SAT；著色；獨(dú)立集；頂點(diǎn)覆蓋；有向圖；無(wú)向圖；哈密頓道路；回路

1 團(tuán)的問(wèn)題屬于NPC問(wèn)題

若G1完全圖是G的子圖，則G1稱(chēng)為G的團(tuán)。

團(tuán)的問(wèn)題描述如下：已知圖G和正整數(shù)k,圖G是否有k個(gè)頂點(diǎn)的團(tuán)？

將SAT問(wèn)題化為團(tuán)的問(wèn)題，方法如下:合取范式中每個(gè)變?cè)捌浞堑囊淮纬霈F(xiàn)對(duì)應(yīng)于一個(gè)圖中的頂點(diǎn),不在同一子句且不互非的變?cè)獙?duì)應(yīng)的頂點(diǎn)以邊相連。 設(shè)合取范式的子句數(shù)為k,問(wèn)題就轉(zhuǎn)化為對(duì)應(yīng)的圖是否有k個(gè)頂點(diǎn)的團(tuán)。

2 3SAT問(wèn)題屬于NPC問(wèn)題

對(duì)于一個(gè)合取范式，若每個(gè)子句有且僅有3個(gè)變?cè)獣r(shí)，它的可滿(mǎn)足性問(wèn)題便稱(chēng)為3SAT問(wèn)題。接下來(lái)說(shuō)明3SAT問(wèn)題屬于NPC問(wèn)題。

證明因?yàn)?SAT是SAT的特殊情況， 所以它屬于NP問(wèn)題。 下證SAT∝3SAT。

1) 短→長(zhǎng):

2)長(zhǎng)→短:

(a)可滿(mǎn)足?(b)可滿(mǎn)足，故得證。

3 圖的著色問(wèn)題屬于NPC問(wèn)題

設(shè)k=n+1，給定k種顏色，下證f可滿(mǎn)足?G可n+1著色。

4 獨(dú)立集和頂點(diǎn)覆蓋問(wèn)題屬于NPC問(wèn)題

圖G=(V,E)，設(shè)S?V，S中任意2點(diǎn)都不相鄰，則稱(chēng)S為G的獨(dú)立集。設(shè)C?V，與C中點(diǎn)關(guān)聯(lián)的邊集就是E，則稱(chēng)C為G的頂點(diǎn)覆蓋。

獨(dú)立集問(wèn)題描述如下：G=(V,E)，k∈Z+，是否存在獨(dú)立集S，使得|S|≥k；

頂點(diǎn)覆蓋問(wèn)題描述如下：G=(V,E)，k∈Z+，是否存在頂點(diǎn)覆蓋C，使得|C|≤k。

定理1獨(dú)立集問(wèn)題屬于NPC問(wèn)題。

定理2頂點(diǎn)覆蓋問(wèn)題屬于NPC問(wèn)題。

證明下面證明獨(dú)立集問(wèn)題∝頂點(diǎn)覆蓋問(wèn)題。G=(V，E)，k∈Z+，另l=|V|-k，若有獨(dú)立集S，|S|≥k,則V-S是G的覆蓋,V-S的頂點(diǎn)個(gè)數(shù)為|V|-|S≤|V||-k=l。反之，若C是G的頂點(diǎn)覆蓋，|C| ≤l，則C=V-C是獨(dú)立集。

5 有向圖的哈密頓道路和回路問(wèn)題屬于NPC問(wèn)題

哈密頓道路問(wèn)題描述如下：已知有向圖D=(V,A)以及u,v∈V，是否存在從u到v的哈密頓道路，使V中所有點(diǎn)到且僅到一次。

定理3有向圖的哈密頓道路問(wèn)題屬于NPC問(wèn)題。

下面證明頂點(diǎn)覆蓋問(wèn)題∝有向圖的哈密頓道路問(wèn)題。

故對(duì)應(yīng)于頂點(diǎn)v∈V，存在一條道路：

↑↓ ↑↓

若圖G中有(u,v)∈E，則G′圖中存在從ai到aj的道路：

和:

圖G′存在有哈密頓道路的充要條件是圖G有k個(gè)頂點(diǎn)的(極小)頂點(diǎn)覆蓋。

2)“?”：若G′有哈密頓道路，則必從a0起到ak止，且過(guò)所有的ai，0

推論1有向圖的哈密頓回路問(wèn)題屬于NPC問(wèn)題。哈密頓回路問(wèn)題是NP問(wèn)題。下面證明哈密頓道路問(wèn)題∝哈密頓回路問(wèn)題。構(gòu)造D′=(V′,A′)，V′=V∪{x}，A′=A∪{(x,u),(v,x)}。于是D有哈密頓道路當(dāng)且僅當(dāng)D′有哈密頓回路。故哈密頓回路問(wèn)題是NPC的。

6 無(wú)向圖的哈密頓道路問(wèn)題屬于NPC問(wèn)題

定理4無(wú)向圖的哈密頓道路問(wèn)題屬于NP問(wèn)題。

下面證明有向圖的哈密頓道路問(wèn)題∝?zé)o向圖的哈密頓道路問(wèn)題。

設(shè)已知有向圖G=(V,E)，構(gòu)造G的一個(gè)對(duì)應(yīng)的無(wú)向圖G′=(V′,E′)如下：

V′={v1,v2,v3|v∈V}E′={(v1,v2),(v2,v3)|v∈V}∪{(u3,u1)|(u,v)∈E}

下證G有哈密頓道路?G′有哈密頓道路。

[1]Dorit S H.Approximation Algorithms for NP-Hard Problems[M].北京：世界圖書(shū)出版公司， 1998.

[2] 陳志平，徐宗本.計(jì)算機(jī)數(shù)學(xué)[M].北京：科學(xué)出版社，2001.

[3] 黃文奇，許如初.近世計(jì)算理論導(dǎo)引:NP難度問(wèn)題的背景、前景及其求解算法研究[M].北京：科學(xué)出版社，2004.

[4] 王樹(shù)禾.圖論[M].北京：科學(xué)出版社，2009.

[編輯] 洪云飛

10.3969/j.issn.1673-1409.2011.12.008

O157.5

A

1673-1409(2011)12-0019-03