[原创]四色问题的提出与证明大事记

雷明85639720

[watermark]                四色问题的提出与证明大事记
                           雷  明
                   （二○一○年二月二十二日）
   1852年10月前，英国的绘图员法朗西斯•古特里（Francis  Guthrie）在给英国地图染色时首先发现了任何地图染色时最多四种颜色就够用了的地图四色猜测；
   1852年10月，法朗西斯把这一发现告诉了他在伦敦大学读书的弟弟弗内德里•古特里（Frederick Guthrie），可弗内德里无法证明是对还是错；
   1852年10月23日，弗内德里写信把这一发现告诉了他的老师——伦敦大学的教授、著名的数学家古斯特•德•莫根（Augustus de Morgan），并经他哥哥法朗西斯的同意把他哥哥的证明也带给了莫根老师，向他进行请教；
   1852年10月23日（弗内德里向他的老师请教的当天），莫根也因为自已无法解决，当天就写信把这一问题告诉了他在三一学院的好友，著名数学家和物理学家威廉•哈密顿；
   1852年10月26日（10月23日后的第3天），哈密顿给莫根回了信，答道“我可能不会很快就考虑你的颜色‘4元组’问题。”以后也没有再引起他对四色问题的兴趣；
   1860年4月14日（1852年后的8年），莫根写的一篇书评中，继续对四色问题进行着传播；
   1878年6月13日（1852年后的26年），在伦敦的数学会上，对四色问题的兴趣又复燃起来；
   1878年6月17日，当时的著名的英国数学家凯莱（Cayley•A）正式询问了地图四色问题是否得到解决；
   1879年（1852年后的26年），在英国皇家地理学会所创办的第一卷会刊上，凯莱再次提出这个问题。此后四色猜测才引起了人们的关注，许多学数学专业的和非学数学专业的人都在试图证明猜测是否正确；
   1879年7月13日，律师出身的数学家坎泊在（Kempe）《自然》杂志上宣布他已经解决了四色猜测问题，即每个地图都能够用4种或者更少的颜色来染色。在凯莱的建议下，当年坎泊就把他的成果发表在《美国数学杂志》的第二卷上；
   坎泊依据任何平面图（地图的对偶图也是平面图）中至少存在着一个顶点的度（即与其相邻的顶点数）小于等于5，采用自已创造的在一条道路上的顶点的“交替着色法”和“颜色交换”技术，交换某条已用两种颜色交替着色的道路上各顶点的颜色，可以空出已用过的四种颜色之一，给有五个相邻顶点并已占用了四种颜色的待着色顶点着上。可惜他并没有对5—轮进行实际着色，就非常自信地按照他对有四个相邻顶点的4—轮的着色方法，非常自信的认为5—轮同样也可以4—着色。留下了一个“漏洞”。
   1880年（1852年后的28年），法朗西斯的弟弟、当时已成为物理学家的弗内德里，在爱丁堡皇家学会的刊物上发表了一篇短文，文中说大约在三十年以前，他当时还是莫根班里的一个学生的时候，他的哥哥法朗西斯首先告诉他地图四色问题，因为他无法解决，才去向莫根请教的。自猜测提出28年后，总把首先提出人搞清楚了；
   1880年，泰特（Tait）根据另外一个错误的猜想“每一个平面三次图都有哈密顿圈”给出四色猜测的另一个证明。从此，猜测的证明开始由对地图的面上的着色开始转为对平面图的顶点的着色。后来还有Erederick Temple发表的一个错误证明；
   1890年（1879年后的11年），当时才二十来岁的、在英国牛津大学读书的学生赫渥特（Heawood）对坎泊的证明进行了否定，却“证明”了什么“五色定理”；
   赫渥特构造了一个图——Heawood—图，其中的未着色顶点（该顶点正好就处在一个5—轮的中心顶点）就与5个其他顶点相邻，图中除该顶点未着色外，其他顶点都已着上了四种颜色之一，该未着色顶点的5个相邻顶点也已占用了四种颜色。因为赫渥特不能对该待着色顶点着上四种颜色之一，就说坎泊的证明有“漏洞”。确实，坎泊的证明恰好也就是在这里出了“漏洞”，正好他对这个5—轮根本就没有进行着色。事情也就正好凑巧，不但赫渥特不能对该图4—着色，坎泊也不能进行4—着色。没有办法，坎泊就只好认输，称自已“弄错了”，并且自已也“无法弥补”这个错误。
   1890年，坎泊只得认同了赫渥特指出的“漏洞”，并在伦敦数学会上亲自报告了赫渥特的工作，并称“自已改正不了这个错误”。从此Heawood—图就成为挡在四色证明道路上的一块巨大的“拌脚石”，也就开始了四色问题长达一个多世纪的漫长的证明历史；
   1890年，由于赫渥特对他的Heawood—图不能4—着色，套用了坎泊创造的“颜色交换”技术，错误的“证明”了一个所谓的“五色定理”，美其名曰是“较弱一点的定理”，实际上是一个“倒退”；
   1980年，赫渥特又提出了一个多阶曲面的地图着色公式，该公式断言能嵌入亏格为n的曲面上的所有图的色数是小于等于＜(7+√(1+48n))/2＞（n≥0）的，但赫渥特只验证了极个别的图该公式是正确的，由于他对他的Heawood—图不能进行4—着色，所以他就在该公式后面加了一个成立的条件（n≥0），尽管当把n＝0（平面图的亏格）代入他的地图着色公式时，公式计算的结果是其色数小于等于0的；
   1890年—1939年，共49年时间，四色猜测的证明处于低潮，脚步几乎停止；
   1939年—1976年，共37年时间，这一阶段是对“假想地图”进行着色，“地图”中的“国家”数由少而多逐步增加，由22个增加到52个，虽然都是只用了四种颜色，但仍不能说明地图四色猜测对任何地图都是正确的，因为所有的地图中的区划（国家）数都是有限的；
   1946年，塔特（Tutte）构造出了一个没有哈密顿圈的平面三次图，对1880年泰特的证明进行了否定。从此，对猜测的证明彻底的由对地图面上的着色转到对平面图的顶点的着色了；
   现在，可以通过已证明是绝对正确的曲面上的欧拉公式v＋f＝e＋2－2n（式中v、f、e、n分别是图的顶点数、面数、边数和曲面的亏格，曲面的亏格也就是图的亏格），推导出当顶点数v≥3时，任意图的亏格是n≥［e/6－v/2＋1］（v≥3）或n≥［1+(e－3v)/6］（v≥3）；
   1968年，Ringel和Youngs证明了顶点数v≥3的完全图的亏格是n＝［(v－3)(v－4)/12］（v≥3），虽没有看到过该公式是如何得来的，但笔者雷明可以把完全图的边数e＝v(v－1)/2代入上面的顶点数v≥3任意图的亏格n≥［e/6－v/2＋1］（v≥3）或n≥［1+(e－3v)/6］（v≥3）而推导出［(v－3)(v－4)/12］（v≥3）来；
   1972年，赛特（Saaiy）也用了一个与Heawood—图同样的图，因为对其不能4—着色而对1879年坎泊的证明进行了否定。其实这一否定是错误的；
   1976年，美国的阿贝尔等人宣布他们用电子计算机“证明”了猜测，当时在全世界引起一时的轰动，但其对猜测的证明并无好处，而只是对计算机商家起到了一定的宣传作用；
   阿贝尔他们的所谓“证明”实质上只是对四色猜测的验证，他们用了近两千个特殊的图，即他们谓说的“可约有不可避免构形”，一个个的用计算机进行验证，都是用了四种颜。但他们的“证明”是白下若，是对资源的浪费，主要是因为在他们的两千多个构形中，偏偏就没有坎泊所没有证明的，赫渥特与坎泊也都不能进行4—着色的那个5—轮构形，这能说是证明了四色猜测吗；
   1992年3月8日，非数学专业的高级工程师、笔者雷明在陕西省数学会第七次代表大会暨学术年会（西安空军工程学院）上作了学术论文报告，报告了作者在1989年对Heawood—图进行的4—着色，证明了5—轮构形是能够4—着色的，对赫渥特对坎泊的否定进行了否定，同时也对坎证明中的“漏洞”进行了弥补。着色时不但是在赫渥特着色的基础上而且仍是用的坎泊的颜色交换技术。
   1994年9月27日，笔者雷明在陕西省数学会一九九四年的学术年会（延安大学）上做了用图论法证明四色猜测的学术报告，不对任何图着色就能证明猜测是正确的；
   该方法是基于任意图的色数与其最小顶独立集数和最小完全同态的顶点数是相等的。首先推导出任意图同化时的最终结果——最小完全同态的的顶点数与图的密度的关系，也即是图的色数与其密度的关系，即任意图着色色数的界：即任意图的色数大于等于其密度值，而小于等于其密度值的一倍半。然后再把平面图的密度不大于4的这个特殊条件代入到上述任意图的色数的界中去，就得到任何平面图着色时的色数总是小于等于4的。这就使自提出到目前已有一百六十多年的地图四色猜测得到了彻底的证明是正确的。
   1998年，董德周先生也对Heawood—图进行了4—着色；
   2007年5 月，张彧典先生对5—轮构形也进行了4—着色，也对坎泊的“漏洞”进行了弥补；
   2008年，许寿椿教授在其《图说四色问题》一书中有一个用计算机给Heawood—图进行的4—着色的结果；
   以上接二连三的对Heawood—图进行的4—着色，说明了猜测证明道路上的这块拌脚石彻底的被搬走了。现在，Heawood—图已经能够进行4—着色，5—轮构形也能进行4—着色，赫渥特的多阶曲面上的地图着色公式当图的亏格n＝0时，其色数γn≤4，进一步证明了四色猜测是正确的。那么，现在就可以把该公式成立的条件改成n≥0了，四色猜测也可以叫做“四色定理”了。
   2009年，笔者雷明进一步通过把顶点数v≥3任意图的亏格n＝［(v－3)(v－4)/12］（v≥3）在向上取整之前变形为一个关于图的顶点数v的一元二次方程，解之得到其根v≤＜(7+√(1+48n))/2＞，由于完全图的色数是与其相同顶点数的图中的最大者，所以又有所有可以嵌入亏格为n的曲面上的图的色数为γn≤＜(7+√(1+48n))/2＞，这就是赫渥特的多阶曲面上的地图着色公式，证明了该色式是正确的。公式中当n＝0时，γn≤4，即任何平面图（亏格为n＝0）着色时的色数都小于等于4的四色猜测是正确的。由此看来，四色猜测也就更应上升为“四色定理”了。
                               雷  明
                   二○一○年二月二十二日于长安

[补充该文...]
  


[/watermark]