“四色问题”的探索与论证.doc

精品论文大集合“四色问题”的探索与论证肖开洲 重庆邮电大学计算机科学与技术学院，重庆 (400065) E-mail：xiaokz28摘要：本文在图论已有的定义、公理、定理的基础上，证明“四色问题”。首先，对所需的 基础理论进行了归纳总结，并逐一列出证明过程中需要的定义、公理及定理；其次，通过两 种在极大平面图上增加新结点和连线的方法，证明任意极大平面图色数 x(G)4；最后，通 过在简单平面图增加点和连线构成极大平面图，证明了任意简单平面图的色数 x(G)4，完 成了“四色问题”的证明。关键词：加点，加线，极大平面图，圈，平面图，三角面，色数1引言四色问题：连通简单平面图的色数不超过4。 在1852年，盖思里(Guthrie)把四色猜想转告了他的老师德摩根(Augustus De Morgan)，德摩根向数学界公布了它。历史上曾有很多人宣布证明了它，但都被后人一一否定。1976 年，美国数学家肯尼思阿佩尔(Kenneth)和沃尔夫冈黑肯(Wolfgang Haken)宣布了一个借助 于计算机的证明。但是，这个证明引起了广泛争论，原因是在他们的证明中使用的超过1000h 的机时，它是不是真正的证明？1通过研究，我得出了一种可行的论证方法。2所用的基础理论定义 11：如果图 G 能够示画在曲面 S(如平面)上，且使得它的边仅在端点处相交，则 称 G 可嵌入曲面 S。如果图 G 可以嵌入平面上，则称 G 是可平面图，已经嵌入平面上的图 G称为 G 的平面表示。定义 21：设 G 是一个平面图，由 G 中的边所包围的区域，在区域内既不包含 G 的结 点，也不包含 G 的边，这样的区域称为 G 的一个面。有界区域称为内部面，无界区域称为 外部面。定义 31：设 G 是阶大于等于 3 的简单可平面图，若在任意两个不相邻的结点 vi，vj 之 间加入边，就会破坏图的平面性，则称 G 是极大平面图。极大平面图的平面表示称为三角 剖分平面图。若 G 是极大平面图，显然 G 是连通的，且 G 中不存在割边。V(3)阶简单平 面图 G 是极大平面图的充要条件：(1)G 中每个面的度数都是 3；(2)设 G 有 e 条边 r 个面， 则 3r=2e；(3)设 G 带有 v 个顶点、e 条边和 r 个面，则 e=3v6，r=2v4。最大平面图的点数、边数和面数间的函数关系用数据列表如下：表 1 最大平面图的点、线、面的关系Tab1 The relationship about vertex, edge and plane in the maximal planar graphV123456789101112E0136912151821242730R112468101214161820定义 43：图的着色是对该图的每个顶点都指定一个种颜色，使得没有两个相邻的顶点 指定为相同的颜色。定义 51：图 G 的色数是着色这个图 G 所需要的最少颜色数，记作 x(G)。- 5 -定义 65：一个“圈”内的一些点，称为“圈内点”；一个“圈”外的一些点，称为“圈外点”； 一个“圈”上的一些点，称为“圈上点”；如果一个图内仅有一点，则这个“圈”称为这个点的“最小圈”。公理 1：任何直接相连接的两点，必须采用不相同的颜色。 公理 2：任何不直接相连接的两点可以采用相同的颜色着色。公理 32：在平面上任何一个“封闭圈”(若干首尾相连的线所构成的图形)都可将平面分 隔为不能直达的两部份，即“圈内”(一部份)的点必须经过“封闭圈”上的点才能达到“圈外”(另 一部份)的点，在平面图着色问题中，线与线之间是不能交叉的。因为如果线与线之间交叉 则它们显然不能处于同一个“平面”上了。定理 14：对任何平面图 G，面的度数之和为边数的二倍。定理 2(欧拉公式) 3：设 G 是带 e 条边，v 个顶点和 r 个面的平面图，则 ver=2。 定理 32：一个图是双可着色的，当且仅当它没有“奇圈”。定理 42：每一个没有三解形的可平面图的色数 x(G)3。 定理 52：在“平面”上的完全图 K 的着色数为 4。定理 62：如果一个图中仅有一个“圈”及圈内仅有一人点，且这个点与“圈上点”都分别 相连接，则这个图的着色数：x(G)4。证明：如图 1，ABCDE的着色数 X3(由定理 1)当再加上圈内一点 O 之后，由于点 O 与圈上所有点都相连，所以点 O 必须取与圈上的点颜色都不同的另一种颜色。于是有 x(G)4。图 1 色数 X3 的情况图 2 圈着色Fig1 one case of chromatic number X3Fig2 coloring of the circle定理 72：在平面图中增一条连接原图中尚未连接的两点之间的连线，都不会减少原图 的色数。定理 82：一个仅有“圈上点”的三角剖分图是 3 可着色的，即 x(G)=3。证明：如图 2，有圈 ABCDEFG先对其中的某一个三角形的三个顶点着色。如对 A、 B、C 三个顶点分别着上第 1、第 2、第 3 三种不同的颜色。然后对下一个与ABC 有公共 边 AC 的ACD 的顶点 D 着上与 B 点相同的第 2 种颜色。接着对下一个与ACB 有公共边 AD 的ADF 中的顶点 F 着上与 C 点相同的第 3 种色。如此继续下去，就可以用 3 种 不同的颜色给所有的顶点分别着色。3论证四色问题论证思路：首先证明 n 个顶点的极大平面图色数 x(G)4；再证明 n 个顶点的其它简单 平面图可通过添加非重复边来构造成极大平面图，则 n 个顶点的其它简单平面图的色数 x(G)4；于是任意 n 个顶点的简单平面图的色数 x(G)4。3.1 证明任意 n 个顶点的极大平面图的色数 x(G)4。证明：因为以上这四种极大平面图只有一种结构(如图 3)，显然 1 个顶点的极大平面图 色数 x(G)=1，2 个顶点的极大平面图色数 x(G)=2，3 个顶点的极大平面图色数 x(G)=3，4 个 顶点的极大平面图色数 x(G)=4。1 个顶点2 个顶点3 个顶点4 顶点图 3 n4 的极大平面图Fig3 maximal planar graph(n4)在 n 个顶点的极大平面图的任意面内添加一个顶点来得到 n+1 个顶点的极大平面图4 个顶点的极大平面图有 4 个面(1 个外部面，3 个内部面)，要构成 5 个顶点的极大平面 图，可在 4 个顶点的极大平面图的 4 个面中的任意一个面 R 内添加一个顶点 O，则点 O 只 能与面 R 的三个顶点相连接，这三个点已点用 3 种颜色，则，顶点 O 着上第 4 种色就行了， 从而构成 5 个顶点的极大平面图(在这里无需考虑这些极大平面图的同构)的色数 x(G)=4，如 图 4。图 4 5 个点的极大平面图Fig4 maximal planar graph(n=5)从而，6 个顶点的极大平面图也可由 5 个顶点的极大平面图得到，即在 5 个顶点的极大 平面图中的任意一个面 K 中添加一个顶点 Q，Q 点则只能与面 K 上的三个点(v1，v2，v3)连 接，因为这三个点已有三种颜色，则 Q 点只需要着上第 4 种颜色就行了。于是，6 个顶点的 极大平面图的色数 x(G)=4。如此构造，可得出任意 n(n4)个点的任意结构的极大平面图，它的色数 x(G)4。在 n 个顶点的极大平面图的任意面的边上添加一个顶点来得到 n+1 个顶点的极大平面图所选取的边 E 存在两种情况：第一种，(如图 5)边 E 是极大平面图内部的两个三角面的公共边(除了第二种情况里的三条边)。将这两个三角面选取出来，两个三角面的四个点最多 已经着上 4 种颜色。在边 E 上选一点 O(除了边 E 的两个端点)，点 O 可以同其它两个点连 接，而这种情况相当于，将所选取的边 E 删去，两个三角面构成一个四边形的面 R1，然后在这个面内添加一个点 O，则点 O 能与面 R1 的四个点连接，在删除边 E 后，面 R1 的四个点可通过调整使用 2 或 3 种颜色(因为四条边刚好构成偶圈，偶圈的色数为 2)，则点 O 只需 要着上第 3 或第 4 颜色就行了。然后再在此基础上，在每个面内添加点，添加边，构成极大 平面图(若不考虑点 O 以及新添加的与点 O 连接的两条边，则点图与原极大平面图同构)， 再结合上面的证明，就能得到这样构造出来的任意 n(n4)个点的极大平面图(可能有 m 种 极大平面图)，它的色数 x(G)4。图 5 两种选边的情况Fig5 two cases about choosing edge第二种，边 E 是一内部三角面与外部面的公共边。无论怎么变形，极大平面图里始终 有三条边是属于外部面的。但是通过图的变形，也可使原先是属于是外部面的边成为不属于 外部面的边，使原先是不属于是外部面的边成为属于外部面的边。于是，通过调整这也就成 了第一种情况。其实，通过在边(不包括边的两端点)上添加点构造出的新的极大平面图，与在面内添加 点构造出的新的极大平面图的个数应当是相同的，并且的一一对应的同构图。综上得，n 个顶点的任意极大平面图(任意一种结构)的色数 x(G)4。证毕。3.2 证任意 n 个顶点的其它简单平面图可通过添加边形成极大平面图由前面所列出的基础理论，显然，任意 n 个顶点的简单平面图，则必然存在某些不相邻 结的点，将不相邻的顶逐个连接以后，必能形成极大平面图。极大平面图色数 x(G)4，则将刚才所添加的边删去后，还原来还来的简单平面图，色 数不会增加，还有可能减少，所以有任意 n 个顶点的简单平面图色数 x(G)4。3.3 由 3.1 和 3.2 的证明，得到所有的简单平面图的色数 x(G)4。4总结本文首先证明任意极大平面图色数 x(G)4 ；然后再证明了任意简单平面图的色数 x(G)4，详细的描述的论证过程。若论证中存在错误，也希望能对证明“四色问题”提供一种 有价值的参考思路。由于笔者能力有限，难免存在错误，还请读者批评指正。参考文献1殷剑宏，吴开亚图论及其算法中国科学技术大学出版社，20032何宗光，何宗明四色定理的证明中国教育与教学，2005 年，第 3 卷，第 1 期：27-293 徐俊明图论及其应用中国科学技术大学出版社，20004 卜月华，吴建专，顾国华等图论及其应用东南大学出版社，20025 王树禾图论及其算法中国科学技术大学出版社，1994A Probe and Demonstration of “Four-color Problem”Xiao KaizhouCollege of Computer Science and Technology, Chongqing University of Posts andTelecommunications, Chongqing, PRC (400065)AbstractThis paper based on the previous definition, axiom and theorem about graph theory to demonstrate thefour-color problem. Firstly, I made a summary about the necessary theory, and listed all of the definition, axiom and theorem, which involved in the demonstration. Secondly, through two methods of adding vertex and line into maximal planar graph, to demonstrate that the chromatic number of every maximal planar graph is not bigger than four; Lastly, by adding vertex and line into planar graph to construct maximal planar graph, to demonstrate that the chromatic number of every planar graph is not bigger than four, then, completed the demonstration of the four-color problem.Keywords: add vertex; add line; maximal planar graph; circle, planar graph; triangulation; chromatic number作者简介：肖开洲，男，1985 年生，硕士研究生，主要研究方向是网络智能、人工智能。