庞加莱公式(1)9页

1、四色定理的非计算机证明：庞加莱定理的一个应用何宗光（浙江科技工程学校）何宗明（上海医疗器械五厂）摘 要 本文在原有的拓朴学、图论、及着色理论的基础上增加了一些必不可少的公理、定理及定义，从而建立了在着色问题上比较完善的理论系统，并采用了一些新的方法，证明了球面上及平面上平面图的四色定理。即在球面或平面上对于任何平面图有X(G)4。 关 键 词封闭圈， 分断隔离， 着色可省略点， 三角剖分图， 着色调整与分析， 添线， 去点， 去线。 一、 引 言 一条定理希望得到证明，必须依靠一个完善的理论系统。在这个系统中有尽可能少但却是足够的公理和基本概念，以及足够的定理、定义、公式等。如果缺少了其中任何

2、一个环节，论证就会变得寸步难行。四色定理之所以长期得不到理论性而非计算机进行的证明，主要就是因为没有建立起一个既简要而又完善的理论系统。下面所列出的公理、定理、定义大都是证明四色定理所需要的，其中绝大部分都是原来拓朴学和图论和着色理论中已有的，极少是新增加的。在“球面”或“平面”上在着色问题中的最重要的特点就是任何“圈”在“球面”或“平面”上的“阻断”作用。同样“圈”在所有“简单多面体”上也有这样的“阻断”作用。但在“非简单多面体”上有些“圈”就不再具有这种“阻断”作用，本文正是利用了这一特点证明了“四色定理”。 另一方面，数学家欧拉在证明“欧拉公式”V+FE=2（其中V是“简单多面体”的顶点

3、数，E是“棱数”F是“面数”）采用了逐步“去线”“去面”“去点”的方法，而本文采用的是先“添线”然后再逐步“去点”与“去线”反复进行，最终完成了证明。这两种方法虽然不完全相同但却有相似之处。 二、预 备公理1：任何直达的（直接相连接的）两点，必须采用不相同的颜色。（注：本文均采用“点着色”的方法）公理2：任何不能直达的两点可以采用相同的颜色着色。公理3：在“平面”或“球面”上任何一个“封闭圈”（指若干条首尾相连的“线”所构成的图形）都可将“平面”或“球面”“分断隔离”成为不能直达的两部份，即这一部份内（即这个“圈”内）的点必须经过“封闭圈”（以后简称为“圈”）上的点才能到达另一部份内（即这个“

4、圈”外）的点（在着色问题中，“线”与“线”之间是不能交叉的。因为如果“线”与“线”之间交叉则它们显然不能处于同一“平面”或“球面”上了。公理4：在“环面”（形如普通的救生圈）上有些“封闭圈”是不能起到“分断隔离”的作用的。即“圈”一侧的“点”可以不必非要通过“圈”上的点就可以到达“圈”的另一侧的点。（这种“环面”实际上是“七可着色”的，但本文不加以讨论）定理1：每一个没有三角形的可平面图是3可着色的（即X（G）3）（注：本文中凡未加证明的定理均为“拓扑学”及“图论”中已有的定理，例如本文中的定理1、定理2、定理3、等。另外本文中所列举的公理也都是各种拓扑学和图论书中经常采用的，只不过是没有明确

5、地列举出来而已）定理2：一个图是双可着色的，当且仅当它没有“奇圈”。定理3：在“平面”或“球面”上的完全图K的着色数为4。定义1：一个“奇圈”或“偶圈”内有一些点，则这些点叫作这个圈的“圈内点”。这个“圈”叫作这些点的“点外圈”。定义2：一个“奇圈”或“偶圈”外有一些点，则这些点叫作这个圈的“圈外点”。实际上“内”与“外”都是相对而言的。特别是在“球面”上更为明显。定义3：一个“奇圈”或“偶圈”上有一些点，则这些点叫作这个圈的“圈上点”。定义4：如果一个圈内仅有一个点，则这个“圈”称为这个点的“最小圈”。定义5：如果去掉了某一个“着色点”之后并不改变原图的“着色数”，那么称这点为“着色可省略点

6、”。定理4：如果一个图中仅有一个“圈”及圈内仅有一个点，且这点与“圈上点”都分别相连则这个图的着色数：X（G）4。证明：如图（1）ABCDE的着色数X（G）3（根据定理1）当再加上圈内一点0之后，由于0与圈上所有的点都相连，所以点0必须取与圈上的点颜色都不相同的另一种颜色。故其着色数应再增加一，故有X（G）4。证明完。 图（1）定理5：在平面图中增加一条连接原图中尚未连接的两点之间的连线，则新图的着色数不小于原图的着色数。证明：假如这后来被连接的两点的原来的颜色是不相同的则连接之后也不会改变原来的着色数。假如这两点原来的着色是相同的，则此时有必要将其中的一个着色点改变为另一种颜色，并对全图的着

7、色进行重新调整。这时新图的着色数仍不会小于原图的着色数。这是因为假设新图的着色数小于原图的着色数，（反证法）设原图的着色数为N,则新图的着色数为N-K,，（N、K都是正整数且KN）。然后再将新增加的那一条连线去掉之后，其它部分可完全采用新图的着色法，也能满足邻点异色的要求。这说明原图的着色数本来就应该至多是N-K。这与前面的假设原图的着色数为N相矛盾。因此新图的着色数小于原图的着色数是不可能的。所以在平面图中增加一条连接原图中尚未连接的两点之间的连线，新图的着色数不小于原图的着色数。证明完。定理6：一个仅有“圈上点”（即既没有“圈内点”又没有“圈外点”）的三角剖分图是3可着色的。即X（G）=3

8、证明：如图（2）有圈ABCDEFG先对其中的某一个三角形的三个顶点着色。例如对A、B、C三个顶点分别着上第1、第2、第3共三种不同的颜色。然后对下一个与ABC有公共边AC的ACD的顶点D着上与B点相同的第2种颜色。然后再对下一个与ACD有公共边AD的ADF中的顶点F着上与C点相同的第3种颜色。如此继续下去，就可以用3种不同的颜色给所有的顶点分别着色。这就证明了对于这种仅有“圈上点”的三角剖分图是3可着色的。即X（G）=3 证明完 图（2）定理6推论：一个仅有“圈上点”的图的着色数有X（G）3证明：在原图的基础上在圈内再增加若干条连线，使其成为“三角剖分图”这样做之后不会减少原图的着色数（根据定

9、理5）。所以有X（G原）X（G新）。但增加了“连线”之后，新图的着色数X（G新）=3（根据定理6）。 故有X（G原）3 证明完。定理7：对于任何平面图有着色数：X（G）5（此定理在本文证明四色定理时可以不利用，但若利用此定理则在叙述本文的证明时会更为方便些，此定理在各图论书中均有证明）定理8: 任何一个封闭的三维空间,只要它里面所有的封闭曲线都可以收缩成一个点,这个空间就一定是一个三维圆球。（庞加莱定理）定理8推论：在“球面”上挖一个“洞”就变成了拓扑学意义上的“平面”了。在“球面”上挖二个“洞”就变成了拓扑学意义上的“圆柱侧面”了。在“球面”上不论挖多少个“洞”都不会改变原来“球面”上的“着

10、色数”。证明：将有限“平面”的“四周”在空间向外收缩为一点，或将“圆柱”的上下底面都收缩为一个点就也成了三维圆球的球面。（庞加莱定理）所以“平面”“圆柱侧面”等曲面在拓扑意义上就是“球面”所以它们的“着色数”也一定相同。（证明完） 三、四色定理的证明四色定理：在球面或平面上对于任何平面图有X（G）4证明：（反证法）假设四色定理不能成立，即存在某平面图是必须用5种或5种以上的颜色来着色。即有X（G）5，不失一般性，可作一个任意复杂的图，如图（3），（注：读者也可在此尝试选择其它任何形状的图）其中的实线部分表示全图的一个很小的局部图，虚线部份表示省略了的大部份图形。其复杂程度可以由读者任意构筑和想

11、象，但必须是“有限图”而不应该是“无限图”。 图（3）然后对此图作以下几个步骤的处理与分析：第一步：在保持原图的所有点与连线的基础下，再将原图中尚未相连但却能够相连的各点两两之间尽可能多地连接起来，（应注意不再增加新的着色点，而仅仅增加连线）直至成为“三角剖分图”为止。由前面定理5可知这样处理之后新图的着色数不会比原图减少，这一步称之为“添线”。第二步：任取图内某一个“圈内点”及围绕这点的“最小圈”进行分析。例如我们取的这个“圈内点”为V，且在“添线”时我们已经连接了V与V及V与V，并且还连接了V与V及V与V已经把原图变成了一个“三角剖分图”这时V的“最小圈”就是VVVVVV。对于这个“局部图

12、形”进行着色调整与分析。根据定理4，我们可以把V的最小“点外圈”安排第一、第二、第三种颜色进行着色。把V安排为第四种颜色进行着色。若然后再给所有“圈外的点”都着上颜色，由假设可知其“着色数”X（G）5，但由前面的“公理2”和“公理3”可知“圈内点”与“圈外点”不可能直达，故可以把V这点的着色由原来安排的第四种颜色调整为第五种颜色，再由定义5可知若这时把V这点连同V直接相连的所有连线都去掉。这样做也并不会减少原图的“着色数”。（因为V这点是被它的四周的“最小圈”阻断隔绝在圈内的，它与“圈外点”的着色是无关的。如果说这样做减少了原图的着色数，例如“着色数”从五减少为四，则说明原图的“着色数”本来就

13、应该是四。）这一步称之为“去点”与“去线”。（这时的V点是“着色可省略点”，而V点既然已经去掉，则与它直接相连的各条线，也就自然没有存在的必要了。因为本文采用的是点着色的方法。）第三步：反复对图中其它各“圈内点”作第一步的“添线”或第二步的“去点”与“去线”，（可交替或不交替地使用）直至对图中的任何一点来说都再也没有“圈内点”可去了为止。最终使它成为一个“三角剖分图”。因为“点”在一个又一个地减少，且“圈内点”与“圈外点”是相对而言的。所以最终的结果只能如图（1）或图（2），即得到只有一个“圈”且圈内只有一个点的图（这时“圈内点”与“圈上点”相连）或一个只有“圈上点”的“三角剖分图”。但这时的

14、“着色数”X（G）4。这显然与开始的假设X（G）5相矛盾，所以一开始的假设X（G）5是错误的。故在“球面”或“平面”上的着色数有X（G）4成立。证明完。为了便于读者更好地理解这一证明，读者可以多自选一些图形，由简单到复杂，按照本文中所提供的方法（即证明中的三个步骤）进行反复试验和思考，便能够悟出本证明其中的无比奥妙和正确性。四、一个细节的说明为了使读者更好地了解本文的思路，作一点补充说明。本文的主要思路是围绕着“全图”中的“局部图”的“圈”及“圈内点”，“圈外点”进行分析与处理的。“三角剖分”图中的“三角”实质上就是由三点构成的“圈”。如果图中出现由大于三点所构成的“圈”，则可以通过“添线”的方法使其成为“三角剖分图”然后再进行分析与处理。如果图中出现由二点构成的“圈”或出现由一点构成的“圈”（例如出现一个区域包围了另一个区域的情况），前文中虽然没有提及，但对于它的分析