[原创]证明四色猜测的几种不同方法的比较

雷明85639720

[watermark]              证明四色猜测的几种不同方法的比较
                            雷  明
                   （二○一○年二月十八日）
    我在《数学中国》网上已经发表了用三种不同的方法证明四色猜测的文章，其中每一种方法中还有一种比较简单的方法，总共用了六种方法。现在对它们进行比较如下：
   
    1、用“着色法”进行证明的两种方法：
    较复杂一点的方法：该方法主要依据的是任何平面图中至少存在着一个顶点度小于等于5，对4—轮与5—轮构形的中心顶点在其外围顶点均已用完了4 种颜色的情况下，运用坎泊的“颜色交换”法，对其中心顶点着上已用过的4—种颜色之一。
    其比较简单的方法是：该方法主要是基于地图的对偶图是一个极大图。当对最小的极大图K3图着上3种颜色后，再在图中增加一个顶点，并使其与图中已有的顶点均相邻，这个顶点只能用第4种颜色；若继续在图中的任何一个面中增加一个顶点时，由于图中的每一个面均是有3条边（或3个顶点）的3—边形面，所增加的这个顶点也只能与3个顶点相邻（若再与别的顶点相邻，图就会变成非平面图），所以这个顶点仍可用已用过的4种颜色之一；继续这样进行下去，所增加的顶点所用的颜色总是在已用过的4种颜色之内。由此可以得出，任何极大图着色时最多4种颜色就够用了。极在图又是平面图中相邻关系最复杂的情况，即边数最多的；极大图着色时最多4种颜色就够用了，那么，非极大的平面图着色时最多4种颜也就够用了。
   
    2、用“图论法”进行证明的两种方法：
    比较复杂一点的方法：该方法主要是依据任意图的色数与其最小顶独立集数和最小完全同态的顶点数相等这一观点，分析图的结构，找到了任意图同化的最终线果——最小完全同态的顶点数与图的密度的关系，确立了图的着色数与其密度之间的关系：任何图的色数总是大于等于其密度值，而小于等于其密度值的一倍半。这就是任何图着色时色数的界。把平面图的密度不大于4的这个特点再代入到上述的色数的界中，就可以得到任何平面图着色时的色数一定是小于等于4的。
    比较简单的方法是：这一方法主要是依据平面图的色数等于其同化时的最小完全同态的顶点数和平面图的最小完全同态的顶点数总是不大于4的完全图这一理论的。
    由于任意图顶点着色的色数就等于其同化时的最小完全同态的顶点数，那么现在只要能证明平面图的最小完全同态的顶点数小于等于4，就能够说明四色猜测是正确的。
    通过完全图的边数e＝v(v－1) 和极大图的边数e＝3v－6列一元二次方程，可求出平面图中最大团的顶点数一定是小于等于4的。这样其最小完全同态的顶点数也一定是小于等于4的。因为平面图的色数等于其最小完全同态的顶点数，所以有任何平面图着色时4种颜就一定够用了的结论。
    3、用纯数学推导的“公式法”进行证明的两种方法：
    比较复杂一点的方法：该方法主要是通过多阶曲面上的欧拉公式直接进行推导。首先推导出任意图的亏格公式n≥［1+(e－3v)/6］（v≥3，式中v、e、n分别是图的顶点数、边数和亏格数），然后再把完全图的边数与顶点的关系式e＝v(v－1)/2 代入到上式中去，得到完全图的亏格公式n≥［(v＋3)(v－4)/12］（v≥3），对这个公式进行变形后，求出完全图的顶点数v≤＜(7+√(1+48n))/2＞公式。由于完全图的色数是同顶点数图中最大者，所以把该公式中的顶点换成色数时，就是赫渥特在1890年给出的多阶曲面上的地图着色公式γn≤＜(7+√(1+48n))/2＞。该公式中当n＝0时，γn≤4，这就是四色猜测：任意平面图（n＝0）的色数都小于等于4。四色猜测得证是正确的。
    比较简单的方法是：这一方法主要是基于Hadwiger的“若图G 是k色的，则G可收缩为一个Kk完全图”这一结论的。平面图中是不存在K5团作其分子图的，因此平面图也就不可能收缩为K5图；平面图中只含有k≤4的Kk团，所以平面图也只能收缩为k≤4的完全图Kk。这个完全图着色四种颜色就够用了，所以任何平面图着色时四种颜色也就够用了。
    4、四种证明方法的比较：5Ry
    第一种方法——着色法，实际上是在进行着色实践，证明过程是“画图—着色”反复进行，严格来说这不应叫做证明。它只能解决平面图的四色问题，解决不了任意图的着色问题，特别是线着色与全着色等问题；
    第三种方法——公式推导法，完全是纯数学推导，证明过程“不要画任何图”，它只能解决任意图的色数的上界，而解决不了其下界，对与平面图的四色猜测也只能证明是正确的，但不能解决具体图的具体色数问题。该方法同样也解决不了线着色与全着色等问题；=9
    第二种方法——图论法，证明过程只是在为了得到任意图的最小完全同态的顶点数与图的密度的关系时，而画了少量的图，但不对其进行着色。它不但解决了任意图的色数的上界，而且也解决了其下界，对于平面图的四色猜测不但能证明其是正确的，而且也能决具体图的具体色数问题，也能解决线着色与全着色问题。
    综合以上讨论，三种证明方法各有其特点，各有各的用处。但总的来说，可能要算第二种方法——图论法要好一些。

                                  雷  明
                        二○一○年二月十八日于长安

[补充该文...]
  







编辑　2010/02/23 11:59pm　IP: 已设置保密 [本文共4653字节]　  
  [/watermark]