搜索
，刘国华（重庆汽车研究所，重庆400039）E-mail：lgr0902@msn.com摘要：全文共分两部分。第一部分先证特殊情形，再证一般情形，两相对照，揭示四色问题的本质。第二部分通过GR图对希伍德（Heawood）反例进行了深入的探讨，指出该类型的平面图自身有破绽并给出新的反例类型以取代原反例。最后，通过剖析动态平衡现象，阐明用肯普（Kempe）的方法证明四色问题不可能成功。文中第一部分，由刘国瑞、刘国华二人合作完成。第二部分，由刘国瑞单独完成。关键词：四色问题；希伍德反例；GR图；动态平衡MR（2000）主题分类号：05C15证明题：平面上任何一幅地图，都可以用四种颜色正常着色1引言四色问题自1852年提出以来，已困扰数学界150余年。在这期间，尽管人们已想到了把国家化归为一个结点，也知道任意两个必须着不同色的结点之间必有一条着这两种色的结点交替出现的双色路[1-2]，然而纵览这150多年间各种各样的解法，我们发现，这些解法未能揭示这一问题的本质，对该问题的要害也缺乏深入的探索，致使这一问题变得异常复杂，1976年还不得不借助计算机花费1260小时来加以证明。实际上，四色问题成立的充要条件是“存在四色地图实例且不能用两两不相交的曲线把同一平面上任意五个点里每两个都连结起来”，这就是我们约四十年前曾向中科院数学研究所指出的该问题的本质。四色问题的要害是希伍德反例，对该类型的平面图我们将借助GR图剖析其内在机制及自身存在的漏洞，并给出新的反例类型取代原反例。昀后，通过剖析动态平衡现象，指出用肯普的方法不可能彻底解决四色问题。本文曾征询并采纳苏州大学施武杰（博士导师）、重庆师范大学谢安国、西南大学王佳等数学教授及西南大学李明、清华大学周喆等数学研究生的意见，在此致以衷心的感谢！2基本概念给定平面图G=＜V，E＞，其中，V是非空结点集，E是连接结点的边集[1]。G具有面F1，F2，…，Fn，这些面中，不受边界约束的面称作无限面（也可称外部区域），所有的面除称作面外也可称作国家。图G通常也称作地图。图G的面Fi，Fj若有一条公共边界ek，则称Fi，Fj为相邻面或相邻国家。对图G正常着色（或简称着色），指的是对每一个面（包括无限面）指定一种颜色，使得相邻面必须不同色。如果图G在着色时必须用n种颜色，我们称G为n一色的，并称着色后为n一色的平面图为按昀少着色原则着色的平面图。G或G的子图正常着色所需要的昀少颜色种类数简称色数。G可以用n种颜色正常着色，指的是对G着色所用颜色种类数≤n。若有图G*=＜V*，E*＞满足下述条件：（a）对于图G的任一个面Fi，内部有且仅有一个结点vi*∈V*。（b）对于图G的面Fi，Fj的公共边界ek，存在且仅存在一条边ek*∈E*，使ek*=（vi*，1作者简介：刘国瑞（1949-），男，河北文安县人，重庆汽车研究所工程师，1982年获学士学位。*），且ek*与ek相交。则称图G*是图G的对偶图（对偶图的其他定义因与着色无关，这里略去，不影响下面的讨论）[1]。对偶图中的一个结点代表原图的一个国家，两结点之间若有一条边直接相连即两结点为邻接点，则表示这两结点所代表的国家本是相邻国家。对偶图中所有结点与其所代表的国家着色相同。有了对偶图的概念，对于地图的着色问题，可以归结为对于任一平面（也可推广到任一曲面）图的结点的着色问题[1]。并且，由于对偶图的着色只与点与点的邻接关系有关，因此我们只需考察连通简单平面图就行了[3]，以下提到的对偶图均为连通简单平面图，不再另行说明。另外，对本证明中既涉及到原图G，又涉及到其对偶图的地方，为免混淆，原图G的面F1，F2，F3，F4等，除保留原命名外，另以国名a，b，c，d等命名，其对偶图相应结点则另以A，B，C，D等命名。引理1不能用两两不相交的曲线把同一平面上任意五个点里每两个都连结起来。证明用反证法。K5图为熟知的非平面图[4]，引理1若不成立，则可得到平面的K5图，矛盾！引理2同一平面上任意四个点，如果用两两不相交的曲线把它们中每两个都连结起来，必有一个点被其余三个点两两连结所引的不相交的曲线包围。证明用反证法。对于平面图K4中的四个结点，如果其中任一个点均未被其余三个点两两连结的不相交曲线包围，那么就可以用两两不相交的曲线把这四个点与该平面上另一个点连结起来，其结果与引理1矛盾！3所有国家尽可能两两相邻的平面图定义1给定同一平面上n个点，用两两不相交的曲线连结这n个点里每两个，如果凡是能连结的任意两点均有这样的曲线相连结，则我们将由此形成的平面图作为平面图G的对偶图，图G即为所有国家尽可能两两相邻的平面图。很明显，如果G中有五个国家彼此相邻，那么该五个国家就必须用五种颜色才能区分，这样四色问题也就不能成立，因此我们首先考察每两个国家尽可能相邻的情形。3.1平面上四个国家彼此相邻的情形引理3同一平面上四个彼此相邻的国家中必至少有一个国家被其余三个国家包围（注：本命题证明及后面的部分内容，我们曾于上世纪六十年代提交中科院数学研究所）。证明设同一平面上有四个彼此相邻的国家a，b，c，d，并在a，b，c，d内各任取一点，分别得到A，B，C，D四点。因为a，b，c，d彼此相邻，所以a，b，c，d中每两个国家间必有公共边界。用两两不相交的曲线分别通过a，b，c，d中每两国之间的公共边界把A，B，C，D四点里每两点都连结起来，则据引理2，A，B，C，D中必有一个点被其余三个点两两连结所引的不相交的曲线包围。不妨设被包围的一个点为A点。因为A被B，C，D三点两两连结所引的曲线BC，CD，DB包围（见下图），又因为曲线BC，CD，DB分别只在b和c，c和d，d和b内，而A在a内，所以，a被b，，d包围。引理3成立。推论同一平面上不可能有五个国家彼此相邻。须注意，同一平面上四个彼此相邻的国家中被包围而与外界（该四个国家以外）失去联系的国家可能不止一个，见下图：3.2引理4所有国家尽可能两两相邻的平面图G昀多是4—色的。证明给定符合以上条件的平面图G，对国家数f用归纳法。a）当f=1，2，3，4时显然成立。b）当f=4时，图G是4—色的即存在四色地图实例。这时，由引理3可知，该四个彼此相邻的国家中必至少有一个国家被其余三个国家包围（这种情形以下简称被包围），所以当f=5时，从外界（原有的国家以外）引进的第五个国家F5昀多只能同原有的三个国家相邻，于是F5可以着上不与其相邻的国家的颜色，即图G仍是4—色的。以下继续考察。因为F5若与原有的三个国家两两相邻，则至少又有一个国家被包围，因此当f=6时，新引进的F6又将重复以上情形。依此类推，即每新引进一个同原有国家尽可能相邻的国家，该新引进的国家昀多只能同原有的三个国家相邻。本结论还可简单证明如下：因为同一平面上不可能有五个国家彼此相邻，所以在所有国家尽可能两两相邻的平面图G中，每个国家昀多只能同三个国家相邻。c）逐个把国家从外界引进，设f=k时，图G仍是4—色的。现考察f=k+1，设新引进的国家为Fk+1。因为Fk+1昀多只能同原有的三个国家相邻，所以Fk+1可着上不与其相邻的国家的颜色，即图G仍是4—色的。引理4显然也可通过对对偶图进行讨论而获得，这里先让大家有一个直观的印象。由后面的讨论可知，面着色和点着色结合起来考虑，更有助于弄清四色问题的有关机制。4任何一幅平面图根据对偶图的概念，四色问题可以归结为对任一平面图的结点进行着色，全部结点昀多只需四种颜色就够了。以下我们就对结点进行考察。4.1对偶图中结点着色的一般情形定理1任何一幅平面图，不可能有五个或五个以上必须彼此不同色的结点。证明给定平面图G=＜V，E＞。a）设vi，vj是G中任意两个必须着不同颜色的结点，它们分别着不同的颜色Ci，Cj。再令H为G中所有着Ci与Cj色的结点的集合，那么，若vi与vj属于结点集H所导出子图的两个不同的连通分支中，将vi所在分图中的Ci，Cj两种颜色对调（或简称换色），并不影响图G的正常着色及色数，即vi，vj在这种情况下可以同色，这与所设条件矛盾，因此，vi，vj属于结点集H所导出子图的同一个连通分支中。由此可知：从vi到vj必有一条路P，P上的各个结点都是着Ci或Cj色[1]。为证明的方便，以下称从vi到vj的这条双色路P为vi与vj的联系通道。）设v1,v2,v3,v4,v5是G中的五个必须着不同颜色的结点，它们依次着不同的颜色C1，C2，C3，C4，C5，那么，由于v1,v2,v3,v4,v5必须彼此不同色，因此v1,v2,v3,v4,v5这五个结点里每两个结点之间必有一条联系通道。这些联系通道只可能有以下两种情形：Ⅰ.彼此不相交（端点v1,v2,v3,v4,v5除外，下同）。Ⅱ.有一处或不止一处相交。我们考察后一种情况。设v1到v2,v3的联系通道分别为P1，P2,它们相交于一点vk。因为P1为v1,v2的联系通道（即P1为着C1，C2色的结点交替出现的双色路），而vk在P1中，所以vk只可能着C1或C2色。同理，P2为v1,v3的联系通道，而vk又在P2中，可知vk不可能着C2色。结论：vk必与v1同色，即着C1色。也就是说，由一点出发的两联系通道相交，其交点必与出发点同色。设P1中v1到vk这一段为P1′,P2中v1到vk这一段为P2′，令P1′,P2′收缩，直至vk与v1合并为一点（被P1′,P2′构成的回路包围的所有结点也一并与v1合并）。合并得到的结点仍保持与v2,v3的联系通道，我们仍称其为v1点。而合并后，vk不再成为交点，即P1,P2不再在v1以外的地方相交。见下图：若v1到v2,v3,v4,v5的联系通道不止一处相交，即不止一个交点，则我们仍可仿照以上方法，即令这些联系通道中各交点与v1之间的这一段收缩（另一段保持不变），直至这些交点全部与v1合并。由于这些交点均已与v1合并，因此合并后除v1外，这些联系通道彼此不再相交。对从v2,v3,v4,v5出发的联系通道若有交点也作类似处理，则昀终我们必得到这样的v1,v2,v3,v4,v5五个点：它们每两个点之间的联系通道彼此不再相交。又因为图G中所有结点均在同一平面上，所以按以上方法合并后得到的结点也必在同一平面上。综合以上Ⅰ、Ⅱ两种情况，我们再将联系通道当作平滑的曲线看待，则必然得到以下结论：任何一幅平面图G，如有五个结点必须彼此不同色，则必能在G中得到这样五个点：用两两不相交的曲线可以把这五个点里每两个都连结起来。而这与引理1矛盾。结论：任何一幅平面图，不可能有五个必须彼此不同色的结点。同理，也不可能有五个以上必须彼此不同色的结点。推论平面图上任意四个必须彼此不同色的结点，必有一个被其余三个两两连结的联系通道包围（证明可参考引理2，这里略）。定理2平面图上任一个结点昀多只能同三个必须彼此不同色的结点相邻。证明用反证法。平面图上任一个结点，如果其邻接点有四个必须彼此不同色，则该结点必须着其邻接点以外的第五种色，而这与定理1矛盾！4.2四色问题证明定理3任意平面图G昀多是4—色的。证明给定平面图G，对结点数v用归纳法。a）当v=1,2,3,4时显然成立。且当v=4时，根据定理1的推论，如果该四个结点必须彼此不同色，则必有一个结点被其余三个结点两两连结形成的回路包围。可知当v=5时，G仍昀多是4—色的。b）设v=k时，任意平面图G仍昀多是4—色的。c）v=k+1时，先给G按昀少着色原则着色。在G中删去vk+1，得到G-vk+1。根据b），G-vk+1仍昀多是4—色的，现恢复vk+1并考察vk+1的着色情形。根据定理2，vk+1昀多只能同三个必须彼此不同色的结点相邻，因此，G仍昀多是4—色的。结论平面上任何一幅地图，都可以用四种颜色正常着色。附带说明一下，一直以来证四色问题不能