由图的3-着色问题论P≠NP，及四色定理的应用

胡钱元（湖南大学数学2000级）

江西省鹰潭市余江二中 鹰潭335203

E-mail:[email protected]

摘 要 图的顶点3-着色问题是NP-完全问题，即使我们把图限制为简单无向平面图。

本文通过定义一类特殊的可以顶点3-着色的图——简单胡图，严格且完整地证明了简单胡图的3-着色问题不存在多项式时间算法，从而得到一般的图的3-着色问题不存在多项式时间算法，于是证明了P≠NP。

附录中给出了对平面图进行4-着色的一个算法。

关键词 图的3-着色问题；NP-完全；多项式时间；算法

中图分类 O157.5

1 引言

本文考虑的图都是简单（无环、无重边）无向图。G=(V,E)是一个具有顶点集V和边集E的图。

由图的顶点3-着色问题解决“P=NP?”的失败路径：利用图的关联矩阵的特征多项式、或者二次型的标准型都不能判定一个图的顶点色数是否为3，哪怕事先已经排除了一些特殊情形。因此，必须回归图的结构本身，找到它的内在性质。

2 有关定义

定义（可3-着色）：设G=(V,E)是简单无向图，若存在函数f：V→{0,1,2}，使得只要(u,v)∈E，就有f(u)≠f(v)，则称G是可3-着色的，G的顶点色数为3，f是G的一个正确的(可行的)3-着色方案。

定义（可3-着色）：设G=(V,E)是简单无向图，若存在函数f：V→{0,1}，使得G中标0的顶点构成一个极大独立集，且标1的顶点在G中的导出子图不含奇回路，则称G是可3-着色的，G的顶点色数为3，f是G的一个正确的(可行的)3-着色方案。

定义（对等点）：设G=(V,E)是简单无向图，G的顶点色数为3，va、vb是G中不相邻的两个顶点，若对G的任意一个正确的3-着色方案，va、vb都着相同颜色，则称va、vb是G的一对对等点。

定义（比邻点）：设G=(V,E)是简单无向图，G的顶点色数为3，va、vb是G中不相邻的两个顶点，若对G的任意一个正确的3-着色方案，va、vb都着不同颜色，则称va、vb为G的一对比邻点。

定义（胡图、理想图）：设G=(V,E)是简单无向图，G的顶点色数为3，若G存在对等点或比邻点，则称G为胡图；否则称G为理想图。

定义（极小胡图）：设G=(V,E)是胡图，若G去掉任意一条边之后所得图为理想图，则称G为极小胡图。

定义（简单胡图）：设G=(V,E)是胡图，若G去掉任意一个顶点及其所有关联边之后所得图为理想图，则称G为简单胡图。

定义（收缩）：设G=(V,E)是简单无向图，vi、vj是G中不相邻的两个顶点。将vi的所有邻点都与vj关联(即：若vc是vi的邻点但不是vj的邻点，则添加边(vj,vc)),再去掉vi,得到图G0，称此过程为对G的收缩，G0是G的以vi、vj为对象的收缩图。

定义（素图）：设G=(V,E)是极大平面图，G的阶数大于4。若G的任意阶数大于3的真子图都不是极大平面图，则称G为素图。

定义（平凡4-正则图）：设G=(V,E)是n阶素图，E={e1,e2,...,e(3n-6)},图G'=(V',E')，V'={v1,v2,...,v(3n-6)},若G'中有边(vi,vj)当且仅当G中的两条边ei、ej有公共顶点，则称G'=(V',E')为素图G对应的平凡4-正则图。

3.正文 P≠NP的证明

由定义可知，理想图中不存在对等点、比邻点。并且容易知道理想图的任意4阶子图的边数不大于4（否则G有对等点）。

以下5条性质是显然的。

性质1.简单胡图必有子图是极小胡图。注意：理想图可以有真子图是极小胡图。

性质2.设胡图G有对等点vi、vj，G0是G的以vi、vj为对象的收缩图，则G0也可3-着色，且G与G0的3-着色方案之间存在一一对应。

性质3.若胡图G有对等点，则连接G中的任意一对对等点所得图G'不可3-着色，即G'顶点色数为4。

性质4.若胡图G有比邻点，则G关于任意一对比邻点的收缩图G'不可3-着色，即G'顶点色数为4。

性质5.若胡图G有比邻点，则连接G中的任意一对比邻点所得图G'仍可3-着色。

下面用3个命题证明，即使是简单胡图这种“简单”的胡图，也可以存在任意多对对等点，而且并不存在能逐一找到这些对等点的方法，只能在穷举方法下将每对对等点都着同色，从而证明图的3-着色问题不存在多项式时间算法，P≠NP。

命题1.对任意正整数k，存在阶数大于k的简单胡图、极小胡图。

证明：不妨设k≥12，则3k-6＞k+2。设G=(V,E)是n阶素图，n≥k，G'=(V',E')为G对应的平凡4-正则图，则G'的阶为(3n-6)，令V'={v1,v2,...,v(3n-6)}。

由四色定理，素图G的顶点可以4-着色，从而G'的顶点可以3-着色。我们可用0、1标记G'的顶点，使得G'中标0的顶点互不相邻，标1的顶点的导出子图不含奇回路。易知G'中标0的顶点有(n-2)个。

设G'中有边{(vi,va),(vi,vb),(vi,vc),(vi,vd),(va,vb),(vc,vd)}，将G'去掉边(vi,vc),(vi,vd),加上顶点v(3n-5)及边(v(3n-5),vc)，(v(3n-5),vd)，得到图G0。

下面证明，G0是胡图，且vi、v(3n-5)是G0的一对对等点。

显然，令vi、v(3n-5)着色相同，可以得到G0的一个正确的3-着色方案。

因为G0有(3n-5)个顶点，且每个顶点至少在一个K3图中，每条边都在K3图中，我们用0、1标记G0的顶点，使得标0的顶点互不相邻，且令vi标0。若v(3n-5)不标0，则G0中最多有(n-2)个顶点标0，至少有(2n-3)个顶点标1，这就一定会使得标1的顶点的导出子图含有奇回路，从而不能得到G0的正确的3-着色方案。于是要得到G0的正确的3-着色方案，vi、v(3n-5)必须着色相同。则G0是胡图，阶数为3n-5＞k+2，且vi、v(3n-5)是G0的一对对等点。

设G0的子图中，有对等点的极小胡图为H0。

易知G'去掉任意一个K3子图的3条边之后所得图为胡图，三个度为2的顶点两两之间构成比邻点。

因为平凡4-正则图都是平面图且每个顶点的度都为4，若极小胡图只有有限个，则存在阶数足够大的平凡4-正则图G'，G'中没有任何子图是极小胡图。这与G'去掉任意一个K3子图的3条边之后所得图为胡图相矛盾。

综上，极小胡图有无数个，且对任意正整数n，存在阶数大于n的极小胡图。而简单胡图可以由极小胡图加边得到，故对任意正整数n，存在阶数大于n的简单胡图。

命题2.对任意正整数k，存在简单胡图G，使得G至少有k对对等点。

证明：考虑命题1中的极小胡图H0，H0有至少一对对等点，且其顶点的度都不大于4。

设H0的一对对等点为vi、vj，H0的关于vi、vj的收缩图为H'0。边(vj,va)在H'0中但不在H0中——即在H0中，va与vi相邻但不与vj相邻。当H'0的阶数足够大，就可以在H'0中添加一些边，设这些添加的边构成边集E'，满足：

(1)这些添加的边构成的图是理想图；

(2)这个理想图再加上边(vj,va)构成极小胡图H'1，且H'1中除了vj、va外，任何两个顶点在H0中的距离都足够远；

(3)vj、va在H'1中不是对等点，也不一定与H'1的任何对等点相邻；

(4)这些边的每个端点在H0中都不是对等点也不是比邻点。

现在考虑在H0中添加E'的所有边，得到图H1。因为H'1是H1的收缩图且是胡图，则H1也是胡图。H1的对等点比H0多一对——vj、va——且vj、va在H1中也不相邻。

要得到包含对等点vj、va的胡图，就必须有H'1，就必须有边(vj,va)，就必须能将vj和va放在一个以这两个顶点为对等点的胡图中等效收缩，就必须要整个H1才行。另一方面，其它对等点原先依赖于整个H0才成为对等点，E'中的边的顶点在H0中距离足够远且边数很有限，只能使H1的阶数小于H1的子图仍然是理想图，即H1仍然是简单胡图。

同理，只要H'1足够大，我们可以将H1加一些边得到H2，使得H2仍然是简单胡图且对等点的对数比H1的多。如此继续下去，我们就能得到对等点的对数递增的简单胡图序列H0、H1、H2、...，Hm，m＞k＞2。

Hm中的对等点虽然有关联又相对独立。设Hm的对等点，越是在序列H0、H1、H2、...，Hm前面出现的越“低级”，越是后面出现的越“高级”。为了找到Hm中的高级对等点，就必须先找到Hm中的低级对等点，直到找到H0的对等点，而H0与Hm是同阶的；反之找到了Hm的低级对等点，还要找到其所有高级对等点才能保证对等点着了同色——即若要对Hm正确着色，必须一次性找出Hm的所有对等点。只能通过穷举法才有把握找到Hm的所有对等点。

此外，Hm还可以再添加一些边得到H，使得H仍然是胡图，但H可能不是简单胡图，可能比Hm有更多的对等点以及比邻点，那么H的着色难度不比Hm的更小。

命题3.简单胡图的着色问题不存在多项式时间算法，即P≠NP。

证明：即使含有一对对等点的简单胡图有多项式时间算法，设时间复杂度为O(n^t)，对于命题2中的简单胡图Hm以及胡图H，所需时间复杂度不低于O((n^t)*(n^(2m-2)))，不低于O(n^(t+m))。而m是可以大于任意给定数的整数，从而一般的简单胡图没有多项式时间算法，胡图没有多项式时间算法，图的3-着色问题没有多项式时间算法，即P≠NP。

4 附录

参考文献

[1]M.R.Garey,D.S.Johnson and L.Stockmeyer, Some simplified

NP-complete graph problems,Theoretical Computer Science(1976)

237-267.