《科学智慧火花》最新退改稿

波斯猫猫

巧证四色猜想
投稿时间：2014-10-28 09:42 投稿人：陈陶
                                               巧证四色猜想

                                           （四川省岳池县白庙职业中学 638350）陈 陶                  

    摘要：对每一幅正规地图的四着色，作者另辟蹊径，采用独特的思维方式和研究方法，找到了恰当的切入点，利用德·摩根定理、数学归纳法和反证法等，严谨、简明地证明了四色猜想。

    关键词：四色猜想 ；德·摩根定理 ；数学归纳法；着色模式T ； 捆绑法； 反证法

一  四色猜想

    画在一张纸（或地球仪）上的每一幅正规地图，只要四种颜色，就能使有共同边界的国家着上不同的颜色（四色猜想指的正规地图有两条限制：1，每个国家必须连成一片；2，两个国家的共同边界必须是条线，而不能是一点或一些离散的点）。

二  背景简介（略，字数所限）

三  证明四色猜想

    下面将给出其严谨、简明的初等证明，文中涉及的示意图，集中附于文后。

    证明：众所周知，对画在一张纸（或地球仪）上的每一幅正规地图着色，要使有共同边界的国家着不同的颜色，四种颜色是必需的。若一幅地图只有一个国家，则四色猜想显然成立。若对国家个数大于1的每一幅地图四着色，分两种情形论证；第Ⅰ种情形又分两种情形。

    Ⅰ若这n﹙n∈N﹡，n≥2﹚个国家是连成一片的，即从任意一国起经共同边界可（重复）走遍所有国家。

    ①如果在这n个国家中，不存在与自身有共同边界的国家个数小于4的国家，即每个国家与自身有共同边界的国家个数都不小于4。根据德·摩根定理“不可能有五个国家处于这样的位置，其中每个国家都和其余四个国家有共同边界” ，从而，满足这个条件的地图其国家个数不小于6。由此，可构建一个着色模式T，并用数学归纳法证明四色（代码为1、2、3、4，不会引起混淆）猜想成立。

    （1）当n＝6时，每个国家与自身有共同边界的国家个数恰好都为四，其中，与“中心”A国有共同边界的有四个国家，与这四个国家有共同边界的另一个R国是“环状”或“半环状”的，如图﹙一﹚；对这6个国家着色，首先，构建一个着色模式：取A国，与A国有共同边界的四个国家用1与2相间着色，其位置有两个选择，若有必要，且又不影响其它国家着色，1与2中的一国可用3或4着色﹙若与A国有共同边界的国家个数m为奇数，则只需一国用到第三种颜色，其位置有m个选择﹚，把这种与A国有共同边界的国家的着色的模式记为T，简称为着色模式T，如图﹙一﹚；其次，缘着着色模式T，按符合四着色要求向外围的国家逐个着色，外围国家只有一个R国，着色3或4 ；再次，最后一个A国着色3或4。这时，四色猜想成立。

    （2）假设n=k（k ∈N﹡,k≥6）时，四色猜想成立，且是在如（1）的着色模式T下，并按（1）的程序和要求对地图完成四着色。也就是，在这幅地图上国家较密集的“中心”处，任取一国作为中心A国，设与A国有共同边界的国家个数为m﹙m满足4≤m ≤k－2，且是某个确定的自然数﹚，总可以：ⅰ，用1与2﹙m为偶数﹚相间着色，若有必要，且又不影响其它国家着色，其中的一国可用3或4着色（类似ⅱ），如图﹙二﹚；ⅱ，用1与2相间着色后，第m个国家着色3或4﹙m为奇数，只需一国用到第三种颜色，其位置有m个选择﹚，如图﹙三﹚；如果存在与这m个国家中的部分国家有共同边界，但与A国只有接触点而无共同边界的其它区域﹙此区域有国家或无国家不确定﹚，跳过此区域，对这m个国家仍按着色模式T着色，如图﹙四﹚；构建如（1）的着色模式T。无论是情形ⅰ或情形ⅱ，对这k个国家着色都是在着色模式T下，并按（1）的程序和要求对地图完成四着色。着色过程分三步，第一步对着色模式T的m 个国家着色；第二步对k－m－1个国家着色，方法是缘着着色模式T，按符合四着色要求向外围国家逐个着色；第三步对最后一个A国着色，即：对ⅰ，A国可用3或4着色；对ⅱ，A国可用4或3着色，且都符合四着色要求。

    那么，当n＝k+1时，因为每个国家与自身有共同边界的国家个数都不小于4，故在这幅地图上国家较密集的“中心”处，总存在两个有共同边界的国家，先将这两个国家视为一个国家G ，这时，与G国有共同边界的国家个数仍不小于4（否则，在这两个国家中至少存在一个与自身有共同边界的国家个数小于4，这与“每个国家与自身有共同边界的国家个数都不小于4”矛盾，如图﹙五）），完全满足归纳假设；因此，对ⅰ，在如（1）的着色模式T下，前两步着色与归纳假设完全一致﹙包括国家个数﹚，第三步，对最后这两个国家、即对G国着色，分别用3、4着色即可，如图﹙六﹚，且符合四着色要求。对ⅱ，为了避免人为造成最后两个国家、即G国中的一国有可能“无法着色”的情况，根据归纳假设，恰当选择着色3（可以不考虑着色4）的位置，这时着色3的位置没有m个选择，只有m－2（m≥4，且是奇数）个选择，在如﹙1﹚的着色模式T下，使最后着色的这两个国家、即G国中的P国与着色3的国家有共同边界，另一个Q国与着色3的国家无共同边界﹙否则，P与Q中有一个国家与自身有共同边界的国家个数小于4，从而产生矛盾﹚，如图﹙七﹚，故，前两步着色与归纳假设完全一致，第三步，对最后这两个国家、即对G国着色，第k个P国着色4，第k+1个Q国着色3，且符合四着色要求。事实上，对ⅰ，取着色3或者4的国家为A 国；对ⅱ，取Q为A国﹙根据对称性和归纳假设，只要恰当选择着色3的位置，在如（1）的着色模式T下，也可取P为A国﹚，无论与A国有共同边界的国家个数m是偶数或奇数，关于A国的着色模式T′与关于G国的着色模式T同结构，如图﹙八﹚、图（九）；也就是，对着色模式T和着色程序的三步的存在性与一致性也作了归纳论证。这就是说，当国家个数n＝k + 1时，四色猜想也成立。

    特别地，当n＝k+1，与A国有共同边界的国家个数m=k－1时，类似于n=6的情形，四色猜想显然成立。

    根据（1）和（2）可知，对国家个数为n﹙n ∈N﹡，n≥6﹚且满足上述条件的每一幅正规地图，四色猜想都成立。

    ②如果在这n个国家中，存在与自身有共同边界的国家个数小于4的B国，则四色猜想成立。

    事实上，（1）当n＝2时，四色猜想显然成立；

    （2）假设n = k（k ∈N﹡，k≥2）时，四色猜想成立。

    那么，当n＝k+1时，暂不考虑B国，对其余的k个国家着色，根据归纳假设（即除B国外，还有与自身有共同边界的国家个数小于4的国家）或根据①的论证（即除B国外，不再有与自身有共同边界的国家个数小于4的国家，而是国家个数不小于4的国家），其着色都符合四着色要求。又因为与B国有共同边界的国家个数小于4，所以，与B国有共同边界的国家着色不超过三种颜色，从而，B国至少可用第四种颜色着色。这就是说，当国家个数n＝k+1时，四色猜想也成立。

    特别地，在这n个国家中，若每个国家与自身有共同边界的国家个数都小于4，则四色猜想显然成立。

    根据（1）和（2）可知，对国家个数为n（n ∈N﹡，n≥2 ）且满足上述条件的每一幅正规地图，四色猜想都成立。

    Ⅱ若这n（n ∈N﹡,n≥2）个国家不是连成一片的。

    这时，这幅地图的n个国家至少由两片组成，且每一片的国家个数（至少有一个）和位置关系无论怎样，根据Ⅰ的论证，每一片的国家着色都符合四着色要求，即四色猜想成立。

    综上所述，对国家个数为n（n ∈N﹡）的每一幅正规地图，四色猜想都成立；且成为四色定理。

    附：证明示意图，其中图（八）由图（六）得到，图（九）由图（七）得到，P着色4 ，Q着色3 （在360或百度搜索：出师表大叔，巧证四色猜想。进入博客中的（完美压缩版），可见图）。

                                                     

                                                                                                                 




智慧火花数学、物理、化学与天文 生命科学与生物技术 地球科学与资源环境 工程技术科学与高技术

学术沙龙新观点新学说沙龙 科学技术前沿沙龙

科学视点青年园地科学家故事