[原创]我研究四色问题的方法

雷明85639720

[watermark]

我研究四色问题的方法
——为木易每文同志所写
雷  明
（二○一一年元月二十三日）
木易每文同志，你说你对我的钻研精神很佩服，但说我所研究的东西太深了，你象看天书一样，其实是你对四色问题和图论还不了解，如果你了解了他们，你也会象我一样，几十年如一日的去进行研究的。现在我就用更通俗一点的语言给你谈谈有关四色猜测证明的问题，
1、什么是四色问题
1852年英国的绘图员法郎西斯在给英国区划地图染色时，发现了任何地图染色时最多四种颜色就够用了，不需要再多的颜色。这就是地图四色猜测。法郎西斯把这个问题告诉了他在伦敦大学读书的弟弟古特里，希望能解释其中的道理。古特里经过认真的研究后，既不能肯定也不能否定，于是在经得他哥哥法郎西斯的同意后，就把这个问题连同法郎西斯自已也认为很不满意的证明于1852年10月23日转交给了他的老师——伦敦大学的教授、著名的数学家莫根，并向老师请教。莫根也无法解决这个问题，但认为这是一个崭新的东西，于是就在当天很高兴的给他在三一学院的好友——著名的数学家和物理学家哈密顿写了信，告诉哈密顿四色猜测问题，希望他能够给以解答。但哈密顿并没有重视这个问题，致使地图四色猜测，一开始就得不到人们应有的重视，过了二十八年后，英国的数学家凯莱在1878年6月13日英国皇家数学会上和在1879年该会所创办的会刊上连续两次提出了这个问题，数学界才对这一问题引起了应有的重视。1879年7月13日律师出身的数学家坎泊在《自然》杂志上宣称他证明了四色猜测是正确的，后来在凯莱的建议下，坎泊把他的成果发表在了《美国数学杂志》第二卷上。这时人们都认为四色问题就此就得到了解决，但在1890年，一个叫赫渥特的学生构造了一张地图，指出了坎泊的证明中有漏洞，但这时坎泊又无法解决赫渥特提出的问题，只得在英国皇家数学会上承认自已弄错了。从此四色猜测至今已有一个半多世纪也没有得到理论上的证明。到了1976年，美国的阿贝尔等三人宣布他们用电子计算机证明了四色猜测是正确的，但至今数学界也没有正式认可他们的“证明”是正确的，因为他们的所谓“证明”只能叫做验证，也不可能用人工的方法进行验证他们的方法是否正确。我认为计算机只能按人的意志去进行工作，但人还不能解决的问题它也绝对不能解决，只是人叫它帮人做事时的速度比人要快得多而已。阿贝尔三人虽宣布他们用计算机证明了猜测，但他们仍没有解决赫渥特找出的坎泊的漏洞，而是把这一个重要的问题用别的问题给代替了，即用双5—轮构形和别的构形代替了5—轮构形（关于构形请见下面的《3、坎泊证明的主要想思》一节），人为的绕过了5—轮构形着色的这个难点，实际上猜测仍然是没有得到证明的。
2、地图四色猜测与数学的关系
你注意看一下行政区划地图，图中有好的区划，也有多条边界线，还有好多的由三条边界线相交而成的点（我叫它三界点）。给一个区划着上一种颜色，使相邻的区划不着同一种颜色，一幅地图最多用四种颜色就够了，这就是地图四色猜测。现在我们丢掉地图的具体内容，只说由这些三界点和边界线构成的几何图形，看一下将是一个什么样的图。如果尽量的把边界线拉成直线，适当的把有些三界点的位置移动一下，以致不至于使拉直后的边界线相交起来，象这样由点和边界线构成的几何图形在数学上就叫做“图”，三界点叫顶点，边界线叫边或线，区划叫面。专门研究“图”的学科就是“图论”。地图中没有边界线相交叉的情况，所以由地图变来的“图”中也是不会有交叉边的，这样的图在图论中就叫平面图，因为它可以边不相交的可以画在一个平面上。相反，如果把图画在平面上时，出现了交叉边，则这样的图在图论中就叫非平面图。四色问题就是只局现在平面图范围内的问题。
如果用顶点来表示某些事物，用边表未事物与事物之间的相互关系或联系，把代表有相互关系或联系的事物的顶点用边连起来所得到的网络就是一个图。如供电、供水、通信的网络，公路、铁路、民航交通的示意图等等都是图，用图可以解决许多的生产、生活和社会现象的实际问题，四色也就是一个实际问题。
在图论中，把平面图的面作新的顶点，把代表两个有边相邻的面的两个新顶点用边连接起来，并穿过两个面的边界线，所得到的新的图就叫做原来平面图的对偶图。地图染色是给地图中区划（在图中叫面）的染色，实际上就是对其对偶图的顶点染色，这样就把一个给地图中面的染色的地理问题变成了一个给平面图的顶点着色的数学问题了。对图的面的染色也不是不可，只是没有对图的顶点染色时研究起来方便而已。数学中研究着色问题，已经是专从对图的顶点着色出发的，而抛开了地图的概念了。图的着色问题解决了，平面图和地图的四色问题也就相应的解决了。这就是数学问题一般都是来源于实际问题，而在数学研究中却又不真对某个具体问题的道理。
还有一个问题就是，在地图中每个顶点（三界点）都连有三条边，象这样的各顶点都连有相同条数的边的图在图论中叫做正则图，把每个顶点所连的边的条数叫做度，则地图就是一个3—度正则的平面图；各顶点的度不尽相同的图则是非正则图。而在地图的对偶图中却是所有的面都是由三条边构成的，都是边数最少的多边形（3—边形），象这样的各面都是由最少边数的多边形——3—边形所构成的图在图论中叫极大图，则地图的对偶图就是一个极大的平面图；各个面的边数不相同的图则是非极大图。
3、坎泊证明的主要想思
坎泊的依据是任何地图中总存在着至少一个区划的相邻区划数小于等于5，这相当于平面图中总存在着至少一个顶点的度小于等于5。这些都是图论中可以证明是正确的结论。一个区划与小于等于5个区划相邻的区划结构，以及度小于等于5的顶点与其外围顶点所构成的轮形结构，在四色问题的证明中分别叫做地图的不可避免构形和平面图的不可避免构形，因为他们在任何地图或平面图中总是不可避免的至少要存在着一个或几个。由这几种构形所构成的集合分别就是地图或平面图的不可避免构形集。因为不可避免构形集是一个有穷的集合，只要能证明这有穷个构形均是可以4—着色的，就可以避免无穷无尽的画图着色（因为其他的所有构形都是可以避免的），就可使猜测得到证明，这就是坎泊的主导思想。这一思想也一直成为后人证明猜测时的重要思想。1976年阿贝尔的证明也是基于这一思想的。
另外还有一个依据，就是任何地图中都不会存在大于等于5个的区划间两两均是相邻的，这与任何平面图中都不存在顶点数大于等于5的团（在这个团中任两个顶点均是相邻的，在图论中把这些顶点与他们之间的边所构成的集合就叫做团）是一个道理，否则这张地图或平面图就都不再是平面图了，也就不属于四色问题所研究的范围了。
坎泊认为，在地图中只要能证明五种相邻区划数不大于5的构形，在其外围所有的区划都已着上了四种颜色之一、且相邻区划间没有着同一颜色的情况下，该区划若能上已用过的四种颜色之一时，就可使猜测得到证明是正确的。因为在给任何地图着色时，总可以把相邻区划数小于等于5的区划放在最后，再看该区划是否可以着上已用过的四种颜色之一。这是一个半世纪之前坎泊证明的思路，完全是从地图的观点出发的，是在给图的面上的着色。如果用现在的图论的观点来描述时，则是只要能证明6种度不大于5的顶点（度为0时也算一种），在其外围顶点均已着上了四种颜色之一、且相邻顶点间没有着同一颜色的情况下，该顶点若能着上图中已用过的四种颜色之一时，也就可使猜测得到证明是正确的。同样是因为我们在着色时也总可以把度小于等于5的顶点放到最后，看该顶点是否可着上已用过的四种颜色之一。
坎泊的思想可以对无限多的地图或平面图，只要证明其五种或六种情况就可以使猜测得到证明，把一个无穷的问题变成了一个有穷的问题了。可惜他没有证明彻底，叫赫渥特把他给否定了。
阿贝尔等人的证明与坎泊的思想是一致的，是坎泊证明的继续，可惜他们是用的穷举法，无穷尽的着色（几乎着了2000个图），不惜浪费计算机资源（用了1200多个机器小时），却没有解决赫渥特所提出的问题。
以上坎泊与阿贝尔的证明都是从给图着色的观点出发，所以我们把它统一叫做着色证明法。这种证明方法所依据的理论根据是没有问题的，可以把一具无穷问题变成一个有穷的问题，但总是给人一个印象这是在用实践的方法（着色）对猜测进行验证，不象是理论上的证明。
4、坎泊对四色猜测的证明
坎泊首先创造了对一条道路（图中由顶点—边—顶点所构成的连续序列就叫道路）中的顶点用两种颜色交替着色的方法，这样交替着有两种颜色的道路叫做色链；也创造了交换某色链中各顶点的颜色用以改变链中各顶点颜色的颜色交换技术。这一着色方法和颜色交换技术也一直成为后人在对猜测的证明中所常用的方法和技术。坎泊就是用他的着色方法和颜色交换技术对地图的不可避免集中的各种构形进行着色的，并以此对猜测进行证明的。
但坎泊的证明只证明了任何平面图中4—轮以下的构形（相当于地图中的一个区划的相邻区划数是4以下的构形），当其外围顶点全着上了四种颜色之一、且没有相邻的顶点使用同一颜色时，轮的中心顶点是可以着上已用过的四种颜色之一的。但当他在证明5—轮（相当于地图中的一个区划的相邻区划数是5的构形）时，他只考虑了一种情况，而没有考虑到还有另一种情况的存在。这一情况就是后来赫渥特发现的他的漏洞所在。5—轮构形能否4—着色，是坎泊证明中成败的关键，可他却没有把全部可能情况都考虑完全，就根据前面对4—轮构形及以下的轮构形可以4—着色，就断定5—轮形也一定能够4—着色，这也铸成了他的证明必然是失败的，这也是他的证明失败的原因。
6、我为什么对四色问题产生了兴趣
1984，1985年我两次学习计算机，均讲到四色问题人一辈子也让明不了，可在计算机问世之后，四色猜测却被计算机证明了。我对这样的说法非常的不服气，所以才有了我漫长的二十五年的证明四色猜测的过程。起初我也是画图，着色，虽都是只用了四种颜色，但总不能说明任何平面图着色时四种颜色就够用了，因为图是无穷多的，你总是不可能把所有图都能着色一遍。后来我就走上了用图论方法让明四色猜测的道路。不用对任何图进行着色，从图论和欧拉公式出发，分别可以证明任何地图或任何平面图着色时，最多四种颜色就够用了，证明了四色猜测是正确的。在此之前我已把赫特渥图中未着色的顶点无意中着上了该图中已用过的四种颜色之一，这就更加坚定了我对猜测进行证明的信心。我继续研究后发现，赫渥特提出的5—轮构形的另一种情况，有其特别的着色方法，它也是能够4—着色的，弥补了赫渥特指出的坎泊证明中的漏洞。用我找到的方法也能指导对赫渥特图进行4—着色，赫渥特构造的那个图中的未着色顶点也能着上该图用已用过的四种颜色之一了。这一方法我已于一九九二年三月八日在陕西省数学会年会上作过学术论文报告，地点是在西安，中国人民解放军空军工程学院。
7、我证明四色猜测的主要思想
既然图的形式是无穷多的，永远也着色不完，那么不用着色的方法能不能对猜测进行证明呢，当然是可以的。任何一个图，把不相邻的顶点放在一起构成一个集合，图论中就叫顶独立集，一个顶独立集内的顶点由于在原图中都是不相邻的，所以着同一颜色是决没有问题的。一个图所能分划出的顶独立集的个数，叫顶独立集数，任何一个图总存在着一个最小的顶独立集数。一个顶独立集内的顶点着一种颜色，那么一个图的最小顶独立集数是几，这个图着色时最少就得用几种颜色。这就是我研究四色问题的出发点。如何求一个图的最小顶独立集数，又得与图的同化联系起来。
图的同化就是把图中不相邻的顶点凝结在一起，最后得到一个完全图。所谓完全图就是其中的各个顶点都是相邻的，不可能再相互同化了，完全图也就是一个团。如果一个图同化后得到的完全图的顶点数是最少的，则这个完全图就叫做原图的最小完全同态，其顶点数就是原图的最小顶独立集数，也是原图的色数。就是在这一思想的指导下，才使我不去对任何图进行着色，就可以对四色猜测进行证明了。
8、图论方法证明四色猜测
我通过对图的结构的分析，研究任意图的同化的最终结果，得到了任意图的最小完全同态的顶点数与图的密度之间的关系。这里先说一下什么是图的密度。图的密度即图中最大团的顶点数。任何图同化后的最小完全同态的顶点数一定不会小于图的密度，而同化后的最小完全同态的顶点数也不会大于图的密度的一点五倍。由此也就得到任意图的色数与其密度的关系，即任意图的色数都不小于其密度值，也不会大于其密度值的一点五倍。任何一个图都有自已的最大团，也就是说何等何图都有一个密度值，在图论中我们已经知道任何平面图的密度是不大于4的，把密度不大于4的各个值都代入到任意图的色数与其密度的关系式中，其结果是图的色数都不大于4，这就证明了四色猜测是正确的。尽管，密度是4的图有可能同化的最小完全同态的顶点数可能是5或6，但是在这种情况下的图已不再是平面图了，而是一个非平面图，这种图却不在四色问题的研究范围之内。这一证明方法我也于一九九四年九月二十七日在陕西省数学会年会上作过学术论文报告，地点是在延安大学。
9、从欧拉公式直接推导出四色猜测的正确
前面提到的赫渥特一生研究四色问题六十年，虽然没有最终解决四色问题，但却得到了一个多阶曲面上的地图着色公式，该公式中只要把曲面的亏格数代入其中后，就可以得到可嵌入该亏格曲面上的图的色数最大不会超过的一个界限值。为了说明问题，这里首先把多阶曲面及其亏格数介绍一下。拓朴学球面也就是平面，平面也就是球面，平面和球面的面的亏格都是0，象轮胎一样的曲面的亏格是1，象眼镜匡一样的曲面的亏格是2，象油炸的麻花一样的曲面是亏格更高的曲面。现在看，球面（平面）上没有孔洞，亏格是0，轮胎面上中间有一个孔洞，亏格是1，眼镜面中有两个孔洞，亏格是2，那么多孔的麻花的亏格就应在3以上了。可以说，球面上有几个孔，该曲面的亏格就是几。这就是拓朴学中的多阶曲面和曲面的亏格。赫渥特的这个公式中当把平面（球面）的亏格0代入后，就得到色数是小于等于4的结果，这就是四色猜测的结论。可是由于赫渥特对他构造的用以否定坎泊证明的赫渥特图他自已不能对其进行4—着色，所以他只好就在他的公式后面增加了一个附加条件：曲面的亏格不等于0。
对于赫渥特的多阶曲面上的地图着色公式，我从去年开始已经通过多阶曲面上的欧拉公式推导出来了，证明了该公式是正确的，同样也就证明了四色猜测也是正确的。这一证明方法我已写进我的《四色猜测与欧拉公式》一书了。
10、我送给你的一个新年礼物
我是一介书生，是一个书呆子，别的什么不会，只会踏实工作和钻研业务。我几十年如一日的研究四色问题也就说明了这一点。这篇论文如果你能看明白，就说明我这么多年的苦没有白下，也说明写这篇论文的一番用心还是有必要的，还可以说明我的理论是一定能够让更多的人看懂和接受的。如果你还想再继续深入一点的了解，就请看一下我前段时间所写的《用不同的方法证明四色猜测》一文。我一直认为一个问题的解决不只有一种方法，而是一定有多种方法的，也很可能目前已经有人用别的方法证明了猜测，只是没有得到数学界的认可而已。只所以得不到认可，是因为目前数学界的大师们从骨子里头根本就看不起我们这些业余的数学爱好者，殊不知历史上有多少伟大的数学家本来就不是学数学专业的，而是为了解决某种难题才成为数学家的。另外，他们业内人士的眼光总是在自已的那个小圈子里打转，思想上受一定的束拂，看不到外界的大千世界，外面的好多好的东西都在他们的不哼不哈中熄灭了，哎，这样的状况下不知要埋没多少人才呀。
雷  明
二○一一年元月三十一日于长安