余江二中学生证照片：图片3-着色问题论P≠NP，应用四色定理

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

胡钱元(湖南大学数学2000级)

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

E-mail:

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

本文定义了一种特殊的顶点3-着色图-简单胡图，严格完整地证明了简单胡图3-着色问题没有多项时间算法，从而获得一般图3-着色问题没有多项时间算法，证明了P≠NP。

附录中给出了平面图4-着色算法。

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

中图分类O157.5

本文考虑的图片简单(无环，无重边)。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(否则G有对等点)。

以下五种性质是显而易见的。

性质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-着色问题没有多项时间算法，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的顶点使标0的顶点不相邻，使标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子图三边后得到的图为胡图，三度为2的顶点两两之间形成相邻点。

因为平凡4-正则图是平面图，每个顶点的度都是4。如果极小的胡图只有限制，那么就有足够大的阶数4-正则图G'，G极小胡图中没有子图。G去掉任何一个K3子图三边后得到的图为胡图矛盾。

综上所述，有无数的极小胡图和任何正整数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任何对等点都相邻；

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

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

包含对等点的要求vj、va必须有胡图H一定要有边(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。

四色定理和平面图着色

定义(素图):设置G=(V,E)大平面图，G如果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-正则图。

易知，任何平面图的顶点都可以4-着色只能作为任何素图的顶点4-着色只是任何平凡的东西4-正则图顶点可以3-着色。下面给出任何平凡4-适用于正则图3-着色算法。

对平凡4-正则图的3-着色算法

第一步，开始

第二步，输入平凡4-正则图G

步骤三、令G中间的所有顶点均为待定点

步骤四、在G中任取一个待定vi，将vi标0，将vi所有邻点标1

步骤五、G有待定点吗？是的，转步骤6，否则转步骤12

步骤六、G满足优先级的存在Ⅰ的待定点vj？是则转步骤七，否则转步骤八

步骤七、将vj标0

步骤八、G满足优先级的存在Ⅱ的待定点vj？是转步11，否则转步9

步骤九、G满足优先级的存在Ⅲ的待定点vj？是转步十一，否则转步十一

步骤十、任
取一个有邻点标1的待定点vj

{n}

步骤十一、将vj标0，将vj的所有还是待定点的邻点标1

{n}

步骤十二、结束

{n}{x