三色问题成立的条件及其证明

zhangyd2007@soh

                                                             三色问题成立的条件及其证明
            
                                                                   张 彧 典      张 之 光

             内容提要：本文给出任意一幅正规地图染色数的判定方法以及三色地图的有效染色方法。
                              
                关键词：三色地图  判定法   染色法  

                                                                                  一、引言

    王树禾教授在他的《数学聊斋》“3.30五色定理和肯普绝招”【1】中首先充分肯定了肯普1879年证明四色定理时的方法【编者按】即对由某二色交替染色形成的已知色链之二色互换的方法，数学家称肯普链法，是肯普首创的绝招。并指出：在关于平面图的染色研究中，人们不止一次地用过这个绝招。就连阿沛尔也承认，他们在用计算机证明四色定理时，同样借鉴了肯普发明的方法和思路。
     接着，他介绍了赫伍德应用肯普绝招成功证明五色定理的全过程。
     最后，王树禾教授指出：四色定理尚缺可视性证明，进一步的问题更加尖锐，对任意给定的平面图G,如何有效地判定x(G)x表示染色数,是否不大于3。这是比四色定理还要困难的问题，这个三色问题目前计算机也不能有效地解决。
      高希尧先生在《地图着色问题 ， 英、美》【2】一文在介绍了“四色定理”之后写到：一些读者可能会问：能否用三种颜色给地图染色，使得任意两个有共同边界的区域不会有相同的颜色，这就是“三色问题”。
      关于“三色问题”很容易发现，一些地图肯定用三色不行。如图1所示。因此可以说“三色问题”在理论上是解决了，但是不是每一张地图都不能用三色染色呢?这还要作具体分析。对于一张地图，通过检查所有可能的染色条件虽然可能解决问题。但是这样的过程非常冗长。如图2所示的地图就有3的16次方个染色方案。对于解这个问题，目前还没有一个已知的有效算法。不过图2确实可以用三种颜色来染色。这个染色方案大体上是用猜测的方法得到的，假如方案不存在的话，猜测当然没有意义。
       如图2所示：一系列猜测染色到J就中断了。因为J与三种不同颜色，“。”、“/”、“+”区域相邻，故J不能用此三色中的任一种染色。但是这并不能说明三色问题的解不存在。事实上，当互换K、L两个区域的颜色，“+”、“。”后，对剩下的区域继续进行一系列猜测染色，很快便得到答案。
高希尧先生最后写到：“三色问题”尚待人们进一步去探讨。
                           

  
                   图1、右图是左图的对偶图
         
                                                                       二、三色地图的判定方法

        我们在40年研究四色定理可视性证明的实践中，曾构造过大量含有不同区域数、不同相邻组合的一般地图或极大平面图，经过对它们的对比、分析，对含有有限个区域的地图，找到一个简单判定它最多染色数的方法——逐点检查法。
        对于给定的以点代表区域的一般地图或极大平面图G，检查每一个节点【3】, 若所有节点都是偶次点，即为偶数条边的交点，则x(G) ≤3。
       若其中只要含有一个不小于3的奇次点，即为3以上奇数条边的交点,则x(G) ≤4。

                                                三、三色地图的染色方法

      首先，就文献【1】中图1、2所示含有有限区域的地图染色验证上述判定方法的正确性。
图1是一个较简单的四色地图，其对偶图也是较简单的四点极大平面图。
这是因为，1号区域被奇数3个区域包围，实际是四个区域彼此相邻，所以必须用四种 颜色才能把它们区分开。

     

      图2是含有17个区域的平面图，其对偶图不是极大平面图，这17个区域按地理位置可分为两类，G、H、K、O四个区域为内陆区域，其余区域均为边界区域。
      对于每一个边界区域，由于其外围区域不是全封闭回路，而是一条开放的路径，所以不管这条路径上的区域数是奇数个或偶数个，都可以用二色正确染色。最后对其染第三色。如图中B区域虽与A、C、D三个区域相邻，但由于它们是一条开放的路径，所以可以用“。”、
“/”二色正确染色，B可染“+”色，D区域虽与A、B、C、E四个区域相邻，但由于它们也是一条开放的路径，所以也可以用“。”、“+”二色正确染色，D已染“/”色，不发生同色冲突。
       对于每一个内陆区域，由于其相邻区域呈全封闭回路，且回路上的区域数都是偶数个，所以都可以用三色正确染色。图2左图之所以出现一系列染色到J就中断的情形，是由于对边界区域I染色时，其六个邻域C、H、F、J、K、L没有按“。”、“+”二色依次交替染色，
把K、L染色颠倒了。所以需要互换它俩的染色，才能对J及余下的区域三色正确染色。
       如果图2左图中不是I、J相邻，而是F、K相邻。如图2中右图所示，这时K区域就与F、I、L、M、J五个区域相邻了，你再用互换K、L染色，就会使K、F的染色都是“。”而发生同色冲突。三染色不能奏效了——不必互换K、L染色，对J染第四色就是了。
       其次，就已知含有有限偶次点数的极大平面图染色验证上述判定方法的正确性。如图3所示：
                                 

      
                                                                                       图3

        第一步：从图中某一个位于中央位置的偶次点开始对所有点由内到外顺时针螺旋式标号。
        第二步：1号点染A色，其偶数个邻点交替染B、C色。
        第三步：对2号点染色，由于它在1号点染色时已染B色，其三个邻点3、1、7已染C、A、C二色，所以可以对剩下的三个邻点8号、9号、10号点依次用C、A、C色染色。
         第四步：对3号点染色，由于它在2号点染色时已染C色,其四个邻点也在前两步染了A、B色，不需要再染色。
         第五步：对4号点染色，由于它在1号点染色时已染B色，其六个邻点中已有五个邻点染了C、A二色，因此只需要给11号点染A色,不发生同色冲突。
          经过以上五步，图3已正确三染色。
         这种依次对标号点及其邻点的染色方法就是对含有有限个偶次点地图的正确三色染色法。用这种染色法对图2左图染色时，就不必一系列猜测染色而一次三染色成功。这种染色法对含有无限个偶次点地图的染色是否有效，只能用数学归纳法证明。

                                                                        四、三色定理的数学归纳法证明

       对于四色定理的证明，由于肯普用欧拉公式确立了一个只含有四类构形的不可避免集。因此，没有必要对含有无穷区域的地图进行数学归纳法证明。而只对四类最简单构形作数学归纳法证明就可以了。对于三色定理的证明，由于至今没有人确立一个最小不可避免构形集。因此只能对含有无穷区域的地图进行数学归纳法证明。证明如下：
       1、        当极大平面图为只含有三个偶次点的最小极大平面图，即三点极大平面图时，如图4所示：

         这时，1号点染A色,其余二个点染B、C色，三色定理成立。
        2、在图3所示含有有限个点的极大平面图中，从第二点，如2号点染色开始，无论对哪个点，如2号点染色时，由于它一定与同属于前一个已染色点，即1号点之邻点的两个同色点染C色的3、7号点相邻，所以这个点，如2号点的邻点中已有三个点染了二色(如C、A、C)，其余奇数个邻点仍可以染已知的二色，如A、C 、A，与已在前一点，如1号点，染色时已染色，如B色的这个点，如2号点，不会发生同色冲突，三染色成功。这一点也是对三色地图染色法的正确性之证明。
        3、设极大平面图含有K个无限个偶次点时, 三色定理成立,证明极大平面图含有K+1个偶次点时，三色定理仍成立。证明如图5所示：图中1、2、3号点为最内三角形顶点K-2、K-1、K为最外三角形顶点，虚线为连接内外六个点的其余由内到外顺时针螺旋式排序点。

                                                

  图4                                 图5
        设已知极大平面图最外层的三个偶次点为K-2、K-1、K，分别染A、B、C三色。这时再加第K+1 点。为了保证最外层的K-2、K-1、K三点都是偶次点2n+2，n为自然数，因此第K+1 点只能与其中的两个点设K-1、K相邻，实际上相当于在已知极大平面图最外层增加了一个最小极大平面图，可以给第K+1 点染别于A、B色的C色。      证毕
                                                  
            
        最后我想说，“人无完人”，再伟大的科学家也有出错的时候。所以希望官方科学研究机构也好，著名科学家也好，不要忽视那些散兵游勇式的民间科学工作者以及他们的智慧闪光。而要给予他们极大的关心、扶持，比如参加科学论坛或会议啦，发表论文啦等。只有双方共同合作交流，才能顺应科学普及的大潮，从而促进中国科学健康迅速发展，早日登上世界科学强国之巅。

       参考文献
【1】王树禾，数学聊斋，第二版，科学出版社，2004年10月，204-205。
【2】 高希尧，数海钩沉—世界数学名题选辑，陕西科学出版社，1982年8月，191-193。
【3】许寿椿，图说四色问题，北京大学出版社，2008年1月，20-22.
【4】黄文璋，数学欣赏，中国统计出版社，2001年12月，152-159。

朱明君

三色问题不等于四色问题

zhangyd2007@soh

是的，三色问题比四色问题更难。