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

郭 蕾

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

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

郭 蕾

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

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

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

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

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

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

將SAT問題化為團(tuán)的問題，方法如下:合取范式中每個(gè)變元及其非的一次出現(xiàn)對應(yīng)于一個(gè)圖中的頂點(diǎn),不在同一子句且不互非的變元對應(yīng)的頂點(diǎn)以邊相連。 設(shè)合取范式的子句數(shù)為k,問題就轉(zhuǎn)化為對應(yīng)的圖是否有k個(gè)頂點(diǎn)的團(tuán)。

2 3SAT問題屬于NPC問題

對于一個(gè)合取范式，若每個(gè)子句有且僅有3個(gè)變元時(shí)，它的可滿足性問題便稱為3SAT問題。接下來說明3SAT問題屬于NPC問題。

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

1) 短→長:

2)長→短:

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

3 圖的著色問題屬于NPC問題

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

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

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

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

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

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

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

證明下面證明獨(dú)立集問題∝頂點(diǎ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 有向圖的哈密頓道路和回路問題屬于NPC問題

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

定理3有向圖的哈密頓道路問題屬于NPC問題。

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

故對應(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止，且過所有的ai，0

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

6 無向圖的哈密頓道路問題屬于NPC問題

定理4無向圖的哈密頓道路問題屬于NP問題。

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

設(shè)已知有向圖G=(V,E)，構(gòu)造G的一個(gè)對應(yīng)的無向圖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].北京：世界圖書出版公司， 1998.

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

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

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

[編輯] 洪云飛

10.3969/j.issn.1673-1409.2011.12.008

O157.5

A

1673-1409(2011)12-0019-03