[原创]平面图的不可避免构形集与四色猜测的证明

雷明85639720

[watermark]

平面图的不可避免构形集
与四色猜测的证明
——与同路人张彧典先生共同商讨
雷  明
（二○一○年十一月九日）
1、平面图的不可避免构形集
平面图的不可避免构形集也叫不可避免集。这个术语是在用坎泊的颜色交换技术证明四色猜测时常用到的一个术语。所谓不可避免，估名思义，就是在任意的平面图中，不可避免的至少都要存在这个集合中的某一个元素。这个集合中的各个元素就是平面图中的某些构形。
地图也是一个平面图，且是一个数3—正则的平面图，也一定存在着不可避免构形集。早在1879年坎泊就指出了任何地图中至少存一个这样的区域，这个区域被另外的一个，两个，三个，四个或五个区域所包围。这相当于在地图的对偶图——一个极大的平面图中总是存在着一个这样的顶点，这样的顶点的度是不大于4的，也即这样的顶点的数量是不可同时为0的。极大图是这样，非极大的平面图就更是这样了。即由顶点度d＝0，d＝1，d＝2，d＝3，d＝4和d＝5的顶点构成的集合就是平面图的不可避免集。
这个结论可以这样证明如下：
因为对于任何平面图来说有：e≤3v－6
图中所有顶点度的总和等于2e，即有：2e≤6v－12
图中各顶点的平均度为：d平＝2e / v≤（6v－12）/ v≤6－12/ v
当v趋于无穷时，对上式求极限得：d平＝ ≤6
平面图的顶点闰均度总达不到6，所以说任何平面图中至少存在着一个顶点的度是小于等于5的。任何平面图中顶点度小于等于5的顶点数是不可能同时为0的。
既是这样，所以我们就可以只对平面图中顶点度不大于5的顶点用坎泊的“最小五色地图”法证明该顶点（该顶点在对应地图中就是一个区域）是“可约的”，即该顶点可以着上该顶点以外的其他顶点已用过的四种颜色之一，就可以说四色猜测就得到了证明是正确的，否则，只要有在某一种情况下的顶点不可约时，猜测就是不正确的。
2、所谓构形和不可避免构形
估名思义，从汉语字面上讲，构形就可理解为结构有形式，简称“构形”。图的各种着色，一般都可以转化成给其图值函数（也是图）的顶点着色，特别是研究四色问题时，更是要对平面图的顶点着色了。比如，对地图（正则平面图）的面上的着色，就可以转化为对地图的对偶图（极大的平面图）的顶点着色。那么，研究图中各顶点的结构就是很有必要的。
图中的顶点各有什么不同之处呢，可以发现各个顶点的度都是不相同的，用度就能描画出各顶点的特征。一个顶点连同它所连接的边和顶点，也都构成一个分子图，我们把这个分子图就叫做“构形”。在极大图中这种构形一般是轮形图。轮形构形中有中心顶点，有轮沿顶点，王树禾教授的《图论》书中把这种中心顶点外的顶点叫构形的“围栏”。这样以来，平面图的不可避免构形集中的元素就是：0—轮构形（W0，即独立顶点，K1图），1—轮构形（W1，即单边图，K2图）2—轮构形（W2，即一条边有平行边的K3图）3—轮构形（W3，即K4图）4—轮构形（W4，偶轮）和5—轮构形（W5，奇轮）。这六种构形在任何平面图中的个数是不可能同时为0的，无论是那一种至少是要存在一个的，当然几个或几种或六种都有也是可能的。这六种构形就叫做平面图的不可避免构形。由不可避免构形所构成的集合就是平面图的不可避免构形集。但对于以顶点度大于5 的顶点为中心顶点所构成的构形，在一个平面图中可以一个都不存在，即是可以避免的，比如n≤4的完全图Kn中就不存在度d＞5的顶点。
3、平面图的不可避免构形集中到底有多少元素
1879年坎泊在对四色猜测的证明中，采用他创造的颜色交换技术证明了顶点度d≤4时都是可约的，唯对d＝5时的5—轮构形只证明了一种情况，就宣布他证明了四色猜测。可到了1890年时，赫渥特发现了坎泊的证明中存在“漏洞”，赫渥特构造了一个图，认为还有另外一种情况下的d＝5时的5—轮构形是“不可约”的。实际上5—轮构形的这一种情况也是可约的（在下面的第4个问题中我们还要专门进行证明）。另外赫渥特的图也是可4—着色的。只是当时赫渥特和坎泊都没有对含有5—轮构形的赫渥特进行4—着色，即没有对该图中的待着色顶点着上其外围顶点已用过的四种颜色之一而已。就这样，四色猜测的证明一下子就直到现在一百六十多年也没有得到一个彻底的证明。
大家认为，坎泊只所以没有证明5—轮构形是可约的，还是因为对构形分得不细。于是多少年来人们都集中于寻找可约的不可避免集上来。1950年Heesch估计不可避免的可约构形集合可能有10000多个元素（请注意，这里只是估计——笔者）；有人又把构形围栏顶点数扩大到了13（请注意，还没有扩大到无穷——笔者）；1976年美图的Appel和Hakend在计算机专业的研究生Koch的帮助下，用计算机花了1200个机器小时，验证了1936个可约构形的不可避免集，这些构形的围栏顶点数都不超过14，当年6月宣布了他们用计算机证明了四色猜测（请注意，无数多个构形是能验证得完的吗——笔者）；1983年更精细的工作得到了一个由1258个可约构形组成的不可避免集；1993（1996）年Robertson，Sanders，Seymour和谐Thomas又得到了一个由633个可约构形组成的不可避免集，1977年声称四色猜测在一台桌面工作站上花大约3小时就可得到证明；最近张彧典所出版的《四色问题探秘》一书中又验证了一个只有九个元素的可约的不可避免集，也宣称解决了四色问题的证明问题。请注意，不可避免构形的数量在不断的变少了。
本来构形围栏内就是一个顶点，可有人硬是把构形围栏内的顶点由单一的顶点扩展到了若干个的一组（请注意，由一个有限的未着色顶点又变成了一个无限的示着色顶点了——笔者）。1904年Wernicke构作了一个不可避免集，他是把坎泊的不可避免集中的5—轮构形用以下两个构形取代，其中一个构形是围栏是6个顶点构成的6—边形，围栏内是两个相邻的度是d＝5的顶点，另一个构形是围栏是7个顶点构成的7—边形，围栏内是两个相邻的顶点，其中一个的度是d＝5，另一个的度是d＝6（请注意，这完全是两个互不相同的构形，能相互代替吗——笔者）；1913年Birkhoff“证明”了围栏顶点数是5，其内不止是一个顶点的任意构形是可约的。所有这些不是明摆着的在回避矛盾吗，既然5—轮构不能证明是可约的，那么我就把你从不可避免集中取掉，用我认为是可约的构形来取代。这是科学的态度吗。这样的相互代替竟然在我们的大学教课书中做为一个经验来宣扬，外国的月亮真圆，外国人放个屁也是香的。
现在来看一看，首先对不可避免构形集中的元素数就是在进行“估计”，另外是用计算机验证有限的各种构形的可约性，三是随意的把构形的中心顶点由一个变成了多个。这都不可能明确的指出不可避免构形集合中的元素到底是多少。请问，在1936个所谓的不可避免构形以外还有没有别的构形是不可约的，平面图的不可避免构形集中是不是就只有这1936元素，理论上证明了没有。因为你只是逐一验证了这1936个构形是可约的，并没有从理论上证明平面图的不可避免构形集中就只有这1936个元素。用机器着色与人有手工着色有什么不同呢，机器着色还不是丝毫不差的按人编写的着色称程序在进行的吗，不也等于是人在对这1936个构形在着色吗。另外，着色肯定是一个顶点一个顶点的着，你把5—轮构形用别的构形代替，其待着色顶点由一个变成了两个，当给其中一个着上颜色时，剩下来的那一个不还是一个5—轮构形吗，能代替得了吗。不知这些大数学家是怎么“证明”出来构形围栏以内的待着色顶点不止一个的任意构形是可约的呢。平面图的不可避免构形是客观存在的，是有限的。不时凭估计得来的，也不是靠用计算速度特快的计算机验证而来的，也并不是能把几个难着色的图进行了4—着色而这几个构形就成了平面图的不可避免构形集，而是要经过理论证明的。可以上的不管是9个元素的集合，还是有1936个元素的集合，都没有从理论上证明再没有超出这些构形以外的不可避免构形了。更不能认为验证的构形越多，都是用了四种颜色，就认为四色猜测就被证明是正确的了。
平面图的不可避免构形集中的元素道底是多少，笔者感到还应该是前面第1个问题中讲到的顶点度d≤5的六种轮的构形，不会再是别的，因为这是经过了理论证明的。只要证明了这六种构形都是可约的，那么四色猜测就可以说得到了证明是正确的。
4、5—轮构形是可约的
5—轮构形是可约的，也就是说含有5—轮构形的平面图是可4—着色的。过去坎泊只证明了d≤4的轮形构形是可约的，现在我们就仍用其创立的颜色交换技术证明5—轮构形是可约的，以对坎泊的证明进行补充和完善。
当5—轮构形的中心顶点V以外的顶点已用完了四种颜色，且5—轮构形的围栏顶点也已用去了四种颜色色时，5—轮构形对角链间的关系只可能有如图1的几种。
图1，a中没有连通的对角链，从任何一个只用了一次颜色的顶点开始进行与其对角顶点所着颜色的色链的交换，即可空出一种颜色给未着色顶点v着上；
图1，b中只有一条连通的对角链r—g（或r—y，用虚线表示），可从顶点2或5（或顶点2或4）开始进行b—y链（或b—g链）的交换，即可空出b或y（或b或g）给v着上（因为在连通的对角链上进行交换是空不出颜色的，所以不能交换r—g链和r—y链）；
图1，c中只有一条连通的对角链b—y（或b—g，也用虚线表示），可从顶点2或4（或顶点2或5）开始进行b—g（或b—y）链的交换，即可空出颜色b或g（或b或y）给v着上；

图1，d中有两条连通且相交叉的对角链r—g和r—y，交叉点着b色，可从顶点2或5（或顶点2或4）开始进行b—y或（b—g）链的交换，即可空出b或y（或b或g）给v着上；
图1，e中有两条连通且相交叉的对角链b—g和b—y，交叉点是顶点2，着b色，可以分别从两个着r色的顶点1和3开始进行r—g链和r—y链的交换，空出r给v着上；
图1，f中也有两条连通且相交叉的对角链b—g和b—y，但两链的交叉点有两个，除了顶点2外，还有另外一个交叉点，也着b色，这个图如果分别从两个着r色的顶点1和3开始进行r—g链和r—y链的交换时，使原来的b—g链和b—y链中的一些顶点由g和y均变成了r，这些顶点有可能在图中本来就是相邻的，这样就不可能同时移去两个r，空不出r给v着上（这一点在一般的文献中均提到了，在张忠辅教授的《数学的陷阱——四色猜想的各种“证明”》一文中又特别提出了这一点）。
这样一来，5—轮构形的中心顶点v似乎没有办法着上已用过的四种颜色之一。真的就没有办法了吗？不是的，而是有办法解决的。

我们可以想办法使其变成图1，a的形式，让图中不存在任何连通的对角链，然后再按图1，a的交换办法给v着上已用过的四种颜色之一。图1，f中的两条连通的对角链是相交叉的，两链共同的顶点除了顶点2外，还有另外一个，都着色是b，只要想办法改变这两个顶点之一的颜色，就可使图1，f变成图1，a的形式，使图中不存在任何连通的对角链。要改变这两个顶点的颜色，就必须从该顶点开始交换两条交叉链共有的颜色与共同没有的颜构成的色链b—r，这样图1，f就分别变成了图2，a和图2，b两图了，该两图都是图1，a的模式，图中不存在任何连通的对角链。这时再任进行一次坎泊的颜色交换，就可空出一种颜色给v着上。用这一方法我们可以给Heawood—图进行4—着色，即可以把Heawood—图中唯一未着色的那个顶点着上其已用过的四种颜色之一（Heawood—图的4—着色作者已于一九八九年完成，其着色过程于一九九二年在陕西省数学会年会上作过学术报告）。
另外，从以上的颜色交换过程中我们还注意到，顶点2是一个非常关键的顶点，它在5—轮构形中的两个相邻的轮沿顶点1和3着有同一颜色r，且只有r色用了两次，别的颜色都只用了一次。在图1的各种情况下，只要从顶点2开始进行b—r链的交换，都可使图1的各种情况变成图1，a的情况，即图中不存在有任何连通的对角链。这就是说，只要是5—轮构形，可以不管它是什么情况，先从顶点2开始对其所着颜色与其相邻的两个顶点所着颜色构成的色链进行交换后，再进行一次坎泊的颜色交换，该5—轮构形就可以4—着色，也就是说这个5—轮构形是“可约的”。
我们还注意到了。图1，f的情况，在最复杂时只可能有如图3中的三种情况，三图都有图1，f的特点，都是极大图，即所有面均是3—边形。
图3，a由于红—兰链是一条环链，从一个兰色顶点交换半—红链，图中又产生了两条相交叉的红—黄、红绿链，仍有两个交叉点，只是其颜色由兰以成了红，整个图的结构并没有变化，与原来是一样的，所以不能按图1，f的交换方法进行着色，而只能从两个红色顶点开始交换红—黄链和红—绿链，同时移去两个顶点的红色，空出红色给V着上，先从那个红色顶点交换是无所谓的；
图3，b是一个标准的图1，f的构形，且图中还有一条环形的黄—绿链，把兰—红链分成了环内与环外两个部分，这样我们无论是从环内还是从环外交换兰—红链，都只能改变两交叉链的一个交叉顶点的颜色，使图中不存在连通的对角链，用给图1，f着色的交换方法是完全可行的；

图3，c中既不存在红—兰环形链，也不存在黄—绿环形链，兰—红链与黄绿链均是只有一条的直链，从那一个兰色顶点开始交换兰—红链，得到的图都是与原图的结构是相同的，原图并没有发生变化，看来是不能按图1，f的交换方法进行着色了。但我们又注意到了，如果先从左边的红色顶点开始进行红—绿链的交换，后从右边的红色顶点进行红—黄链的交换时，也可以向图3，a那样，同时移去两个顶点上的红色，把红色给V着上；我们也发现，如果交的换次序错了，也没有关系。因为这时的图就变成了一个结构与图3，b结构相同的图了，用给图3，b和图1，f着色时的交换方法就可以给V着上已用过的四种颜色之一。张彧的九个构形及其介绍的霍罗伊德—米勒构形实际上采用图1，f着色时的交换方法，同样也可给其中的未着色顶点V着上已用过的四种颜色之一。
到此，5—轮构形的4—着色已完成，5—轮构形也是要可约的。坎泊证明中的漏洞得到了弥补。四色猜测应该是正确的。
5、四色猜测的证明
过去坎泊已证明了0—轮（K1图）、1—轮（K2图）、2—轮（K3图）、3—轮（K4图）和4—轮构形的可约性，现在我们又证明了5—轮构形的可约性。至此，地图或平面图不可避免构形集中的各种构形就都是可约的了，这样我们就可以对四色猜测进行证明了。
一个顶点数为n（n为自然数）的平面图（或地图的对偶图）中一定存在着度d≤5的顶点。把这些d≤5的顶点从图中去掉，图仍是一个平面图，图中又会产生新的度d≤5的顶点，再把新图中的度d≤5的顶点去掉，就这样一直取下去，最后图将成为一个顶点数n≤4的图，这种情况下，最复杂时只可能是一个K4图（即3—轮），着上四种颜色是绝对没有问题的。
现在再沿相反方向向回走，给上面的n≤4的图中增加最后一次取掉的那些度d≤5的顶点，图中就有n≤5个顶点，这时未着色顶点的度最大也只可能是4，即未着色顶点在一个4—轮的中心，坎泊早已证明了4—轮是可以4着色的；若再增加最后第二次取掉的那些度d≤5的顶点时，图中就有n≤6个顶点，这时未着色顶点的度最大也只可能是5，即未着色顶点在一个5—轮的中心。从上面的证明可以看出，5—轮构形4—着色是没有问题的，即增加的这些顶点着上已用过的四种颜色之一是可以办到的。继续增加顶点时，由于所增加的顶点都是原来从图中所去掉的顶点，其度d都是≤5的，这些顶点一定是可以着上四种颜色之一的；一直到把从图中所去掉的顶点全部都增加进去为至。因为所增的每一个顶点都是可以着上已用过的四种颜色之一的，所以整个图也就只用了四种颜色。这也就证明了四色猜测是正确的。
四色猜测正确！应上升为四色定理！


雷  明
二○一○年十一月九日于长安
注：图请打开DOS文件查看。