NPC问题中几个基本定理的证明

郭 蕾

(常州纺织服装职业技术学院信息技术系，江苏 常州 213164)

NPC问题中几个基本定理的证明

郭 蕾

(常州纺织服装职业技术学院信息技术系，江苏 常州 213164)

就NPC问题(NP-complete，NP完全问题)中的几个基本定理给出了证明。首先从基本的团问题、SAT问题和图的着色问题入手，证明了它们都属于NPC问题，再利用独立集、顶点覆盖、有向图、团、SAT和图的着色等问题本身的内在关系，对其他的定理做了一一证明。

NPC问题；SAT；着色；独立集；顶点覆盖；有向图；无向图；哈密顿道路；回路

1 团的问题属于NPC问题

若G1完全图是G的子图，则G1称为G的团。

团的问题描述如下：已知图G和正整数k,图G是否有k个顶点的团？

将SAT问题化为团的问题，方法如下:合取范式中每个变元及其非的一次出现对应于一个图中的顶点,不在同一子句且不互非的变元对应的顶点以边相连。 设合取范式的子句数为k,问题就转化为对应的图是否有k个顶点的团。

2 3SAT问题属于NPC问题

对于一个合取范式，若每个子句有且仅有3个变元时，它的可满足性问题便称为3SAT问题。接下来说明3SAT问题属于NPC问题。

证明因为3SAT是SAT的特殊情况， 所以它属于NP问题。 下证SAT∝3SAT。

1) 短→长:

2)长→短:

(a)可满足⟺(b)可满足，故得证。

3 图的着色问题属于NPC问题

设k=n+1，给定k种颜色，下证f可满足⟺G可n+1着色。

4 独立集和顶点覆盖问题属于NPC问题

图G=(V,E)，设S⊆V，S中任意2点都不相邻，则称S为G的独立集。设C⊆V，与C中点关联的边集就是E，则称C为G的顶点覆盖。

独立集问题描述如下：G=(V,E)，k∈Z+，是否存在独立集S，使得|S|≥k；

顶点覆盖问题描述如下：G=(V,E)，k∈Z+，是否存在顶点覆盖C，使得|C|≤k。

定理1独立集问题属于NPC问题。

定理2顶点覆盖问题属于NPC问题。

证明下面证明独立集问题∝顶点覆盖问题。G=(V，E)，k∈Z+，另l=|V|-k，若有独立集S，|S|≥k,则V-S是G的覆盖,V-S的顶点个数为|V|-|S≤|V||-k=l。反之，若C是G的顶点覆盖，|C| ≤l，则C=V-C是独立集。

5 有向图的哈密顿道路和回路问题属于NPC问题

哈密顿道路问题描述如下：已知有向图D=(V,A)以及u,v∈V，是否存在从u到v的哈密顿道路，使V中所有点到且仅到一次。

定理3有向图的哈密顿道路问题属于NPC问题。

下面证明顶点覆盖问题∝有向图的哈密顿道路问题。

故对应于顶点v∈V，存在一条道路：

↑↓ ↑↓

若图G中有(u,v)∈E，则G′图中存在从ai到aj的道路：

和:

图G′存在有哈密顿道路的充要条件是图G有k个顶点的(极小)顶点覆盖。

2)“⟸”：若G′有哈密顿道路，则必从a0起到ak止，且过所有的ai，0

推论1有向图的哈密顿回路问题属于NPC问题。哈密顿回路问题是NP问题。下面证明哈密顿道路问题∝哈密顿回路问题。构造D′=(V′,A′)，V′=V∪{x}，A′=A∪{(x,u),(v,x)}。于是D有哈密顿道路当且仅当D′有哈密顿回路。故哈密顿回路问题是NPC的。

6 无向图的哈密顿道路问题属于NPC问题

定理4无向图的哈密顿道路问题属于NP问题。

下面证明有向图的哈密顿道路问题∝无向图的哈密顿道路问题。

设已知有向图G=(V,E)，构造G的一个对应的无向图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] 陈志平，徐宗本.计算机数学[M].北京：科学出版社，2001.

[3] 黄文奇，许如初.近世计算理论导引:NP难度问题的背景、前景及其求解算法研究[M].北京：科学出版社，2004.

[4] 王树禾.图论[M].北京：科学出版社，2009.

[编辑] 洪云飞

10.3969/j.issn.1673-1409.2011.12.008

O157.5

A

1673-1409(2011)12-0019-03