• 2007-05-30

    [星丛]四色定理理论证明及推广 - [星丛]

    版权声明:转载时请以超链接形式标明文章原始出处和作者信息及本声明
    http://www.blogbus.com/sgzxy-logs/6296345.html

        注意:以下证明已被推翻,请参看我后续的文章。
        这绝对是本BLOG有史以来最搞笑的一篇文章……如果你学过图论并知道什么叫“四色定理”的话,或者你了解这个理论证明悬而未决的定理的悠久历史的话……好吧,贴出这篇文章只是想把今天晚饭时的胡思乱想给推翻,那么,有请各位数学达人登场,尽情地有根据地讽刺以下的文字吧。
        
         2007.5.31
        睡了一觉起来发现有些小毛病,主要是用词不准确和概念不够清晰统一,遂作了少量修改,并把推广部分的叙述更加详细化。事实上我发现以下证明需要的数学知识是少得相当可怜的,即使对于完全没有学过图论者,我也只需补充几个小概念的解释即可:
        平面图:图论中研究的最重要问题之一,一个图为平面图即此图本身或者它的同构图(即所有性质相同的,只是表现形式有差别)中所有连接线条都不交叉。
        K5图:K是对图性质的标记,在图论中即表示此图为完全图,而完全图浅白来说即为我们所谓的所有点两两相交的图(但是在对于图论中的“二分图”则另有说法,这里要理解的话就先不考虑这个)。K5表示含有5个点的两两相交图,不妨自己画一下?一个五边形中间嵌一个五角星。这一图被证明为非平面图,从而和另一个叫K(3,3)的基本图形构成了对平面图判定的充要条件。
        对偶图:这个概念是为研究“四色猜想”应运而生的,至于解释没有图示说明很难表达,只能说这一概念成功将平面区域染色问题转化为点染色问题,故研究对偶图的染色等价于研究平面地图的染色。

        再补充一些关于“四色猜想”证明的历史……
        这个猜想有一百多年历史,直到1972年被两个数学达人宣布用计算机证明。我一度认为这个所谓“用计算机证明”是计算机推理证明(当时看关于有限状态自动机等推理机的介绍时提到这个证明,说是计算机学界的轰动,所以被误导了),而昨天上课才知道那个证明是穷举证明(即对“四色猜想”涉及到的所有情况——不知道那两位是怎么去概括归纳的,进行穷举)。而1996年有另一位达人进行了更优的穷举证明,反正我英文版的离散数学书上说至今未有成功的理论证明。故而在实用领域上“四色猜想”可以被称为“四色定理”,但是在理论证明方面这仍然是个猜想。
        而我的离散老师给我们讲了一个NB的故事,说是多少年前美国一个顶顶顶NB的数学家在给学生上数学课时才第一次知道这个“四色猜想”,知道后不屑一顾道“靠这么简单我马上证给你们看”……于是提笔就写,写了几大黑板,没解决,第二天继续,没解决……就这样听说他写了几个礼拜,写到学生都走光了……才突然说:“噢,原来真是有点难度的。”
        这个故事告诉我们,以下证明一定是错的。

    四色定理理论证明及推广


    概念定义:
    n点完全平面图:指n个点两两相连的平面图。
    最小染色数:指将图中所有点染色,且相邻连接点颜色不同所需要的最少颜色种数。

    引理1:一个平面中最多容纳4点完全平面图。
    证明:完全图n必然包含完全图n-1,已知K5图非平面图,则n>5的图同样非平面图。

    引理2:四点完全平面图在平面中必有一点处于封闭平面域。
    证明:可简单穷举得证,或者依据拓扑学相关理论。

    引理3:n点完全平面图的最小染色数必为n
    证明:由完全图定义得证。

    猜想:任意n点平面图最小染色数等于其包含的最大完全平面图的点数。
    证明:
          n=1时,染色数为1,猜想成立。
          n=2时,两点连接时最小染色数为2;若两个点不连接,即包含最大完全平面图为一个点,只需一种颜色。猜想成立。
          n=3时,三点完全平面图最小染色数为3(不连接情况相应容易考虑,不赘叙)
          n=4时,穷举易证,包含最大完全平面图点数为1、2、3时,最小染色数相应为1、2、3;包含最大完全平面图点数为4时(即本身是个4点完全平面图),引理3知,最小染色数为4。猜想成立。
          现在利用数学归纳法。
          设n=k(k>=4)时猜想成立,则添加一点o使n=k+1。
    (1)当原k点的图中包含4点完全平面图时,则由引理2知,o点最多能与k-1个点连线。而对于o点着色的问题,只需要考虑包括o点在内的k个点之间的连接情况(即由引理2所知被围的点无需考虑),则由n=k时猜想成立的前提可证,o点不会增加颜色使用的种数(直观来说即o点可以使用被围点的颜色)。故最小染色数仍为4(图中最大包含的是4点完全平面图)
    (2)当原k点不包含4点完全平面图时,则o点最多与k个点连线。设原k点所包含的最大完全平面图的点数为p(0(3)若o点与原k点的连接不充分(即至少有一点不连),则对于o点着色问题,只需考虑o点以及与o点相连点之间的连接情况,设这些点数量为m,则必有m<=k。故由n=k时猜想成立的前提可证。
        故对于n=k+1时,猜想也成立。

    综上所述,猜想成立。

    “四色定理”证明:
    平面中任意对偶图均满足上述已证明的猜想,而由引理1可知,一个对偶图所能包含的最大完全平面图点数为4,故任意对偶图的最小染色数为4。由对偶图与连通平面图的等价关系,可知四色定理成立。
    P.S:四色定理只是原猜想的特殊情况。

    关于猜想证明的一点补充讨论:
    证明中最关键的步骤是数学归纳法部分(所以错误应该也出于此),而这一部分分成三种情况讨论是因为想达到证明的最完备性,事实上第三部分是显而易见的,而仅仅证明“四色定理”的话则第二部分都可以省略。

    推广:
    在研究的过程中发现以下更具拓展性的猜想:

    推广1.把“图”仅看作一个由点和线组成的结构概念,则上面证明的猜想显然可以有推广:
       任意n点图最小染色数等于其包含的最大完全图的点数。

    推广2.如果将类似问题延伸到任意n维空间的染色问题,则可以得到下述猜想:
    概念定义:
    (1)m单位:如果点相对于二维空间为一种几何单位,则m单位是相对于m维空间与“点在二维空间”等价的几何单位。
    (2)结构:若把“图”仅看作一个二维概念,则把“图”概念延伸到任意m维空间称为“结构”。而m单位之间的连接方式会因m维空间维度的不同而改变(如三维空间中的连接方式应该是“面”)。
    (3)完全结构:指由m单位构成的,并且其中所有m单位两两相连的结构。
    (4)完全m维结构:对应于二维中的概念“完全平面图”,即此时结构中的连接在m维空间中不会交叉。

    猜想1:m维空间最大容纳m+2个“m单位”的“完全m维结构”。

    猜想2:任意n个“m单位”结构的最小染色数等于其包含的最大“完全结构”的m单位数。

    而在猜想1和猜想2的基础上可以得到“四色定理”的m维空间推广:
    猜想3:若m维空间被任意m-1维几何形分割成区域,则对每个区域染色,适应于所有分割情况的最小染色数必为m+2。

    推广证明的初步讨论:
    推广1:这一猜想的证明按照同样的证明思路显然可得,因此若原证明思路无误,则此猜想易证。

    推广2:猜想1即引理1的推广,在二维空间中这涉及图的平面化问题,而在m维空间则涉及“m维结构的m维化问题”……不知道拓扑学对此是否有所研究。
            猜想2即推广1的m维空间推广,这依赖于引理3的推广,即:含n个m单位的完全m维结构最小染色数必然为n。这个证明不言自明。
            猜想3的证明除了依赖于猜想1、2外,还依赖于引理2的推广,即:含m+2个m单位的完全m维结构在m维空间中必有一个m单位处于封闭m维空间域中。
    分享到:

    评论

  • 如果那是个错误的话,应该是致命的吧
  • 数学归纳法的第三步,我觉得有问题,前两步个人觉得是对的,但第三步运用条件假设有误吧?只能前推后,不能后推前(也可能是我没看明白)由于我只是略微看过一下四色定理,对其中的问题还没有一些深刻的理解。P.S.太佩服大饼啦,很有数学家的feel哦!