四色定理的证明及对几个研究课题的探讨

王卫东 王小丹

1.烟台新宇科技有限公司 山东 烟台 264000;2.长安大学渭水校区 陕西 西安 710014

一、四色定理的证明及意义

四色问题的起源及四色定理的证明过程问题的提出

1852年,伦敦大学毕业生格斯里(FrancisGuthrie)来到一家科研单位搞地图着色工作时,发现每幅地图都可以只用四种颜色着色。但这一现象能不能当作数学问题加以严格证明呢?他和正在大学读书的弟弟决心大胆试一试,但是稿纸已经用了一大叠,研究工作还是没有任何进展。弟弟还就此问题的证明请教了他的老师、著名数学家德·摩尔根,摩尔根也没有能找到解决的有效途径,于是写信向好友、著名数学家哈密顿爵士请教,但直到1865年哈密顿逝世为止问题仍未能够解决。

1872年,英国当时最著名的数学家凯利正式向伦敦数学会提出了这个问题,于是四色猜想成了世界数学界关注的问题,世界上许多一流的数学家都纷纷参加了四色猜想的大会战。

肯普的研究

1878～1880年两年间,著名的律师兼数学家肯普(Alfred Kempe)和泰勒(Peter Guthrie Tait)

两人分别提交了证明四色猜想的论文,宣布证明了四色定理(Four color theorem)。

大家都认为四色猜想就此解决,但其实肯普并没有证明四色问题。1890年,在牛津大学就读的年仅29岁的希伍德以自己的精确计算指出了肯普在证明上的漏洞。他指出肯普说没有极小五色地图能有一国具有五个邻国的理由有破绽。不久泰勒的证明也被人们否定了。人们发现他们实际上证明了一个较弱的命题——五色定理。就是说对地图着色,用五种颜色就够了。

不过让数学家感到欣慰的是,希伍德没有彻底否定肯普论文的价值,运用肯普发明的方法,希伍德证明了较弱的五色定理。一方面,五种颜色已足够,另一方面,确实有例子表明三种颜色不够。

肯普的贡献

肯普是用归谬法来证明的,大意是如果有一张正规的五色地图,就会存在一张国数最少的“极小正规五色地图”,如果极小正规五色地图中有一个国家的邻国数少于六个,就会存在一张国数较少的正规地图仍为五色的,这样一来就不会有极小五色地图的国数,也就不存在正规五色地图了。这样肯普就认为他已经证明了“四色问题”,但是后来人们发现他错了。

不过肯普的证明阐明了两个重要的概念,对以后问题的解决提供了途径。第一个概念是“构形”。他证明了在每一张正规地图中至少有一国具有两个、三个、四个或五个邻国,不存在每个国家都有六个或更多个邻国的正规地图,也就是说,由两个邻国,三个邻国、四个或五个邻国组成的一组“构形”是不可避免的,每张地图至少含有这四种构形中的一个;肯普提出的另一个概念是“可约”性。“可约”这个词的使用是来自肯普的论证。他证明了只要五色地图中有一国具有四个邻国,就会有国数减少的五色地图。自从引入“构形”,“可约”概念后,逐步发展了检查构形以决定是否可约的一些标准方法,能够寻求可约构形的不可避免组,是证明“四色问题”的重要依据。但要证明大的构形可约,需要检查大量的细节,这是相当复杂的。开始人们希望通过用可约构形简化地图来研究证明四色定理;计算机也依据这个思路进行证明,虽然做了百亿次判断,终究只是在庞大的数量优势上取得成功,这并不符合数学严密的逻辑体系。

由于四色定理的证明没有得到公认,所以包括中国在内的很多数学爱好者仍在前仆后继的不断努力,希望找到能得到大家公认的证明。笔者也是其中的一员,经过长期探索,我们终于通过对色链的研究,利用色链的性质对四色定理进行了证明,并且首次对四色定理进行了详细描述,能否得到大家对认可,我们拭目以待。具体的证明过程详见《中国科技投资》杂志2019年第17期。

四色定理:当给平面或球体表面地图上的国家着色时,只需四种颜色,即可使任何两个相邻的国家不具有相同颜色,只在孤立点上相邻的国家除外。同时,它们必然符合网状链式结构的特点,即:任意连接两种颜色,便会形成一条链;当地图中的国家相当多时,所形成的链或连续或断开,形如网状,它们的最小组成部分是单色或孤立点。

四色定理的内在本质就是网状链式结构,这个结构能够囊括‘给平面地图用四种颜色着色’的所有情况。

证明四色定理,必须用完全归纳法,而且需要有严密的逻辑证明过程。说起严密的逻辑过程,我们不得不说一下逻辑学里面的一些悖论。实际上,我们认为逻辑学是一个严密的思维科学,是不应该有悖论的,之所以有一些逻辑悖论,是因为有一些概念模糊造成的,比如比较著名的“理发师悖论”。

“理发师悖论”是“罗素悖论”的通俗说法。所谓悖论就是怎么说都不对。他说,假如有一个村子,村子里有一个理发师,这个理发师,他在自己的店门口立了一块牌子,说我给且仅给自己不刮胡子的人刮胡子。也就是说,如果你自己给自己刮胡子,那我就不给你刮了。如果你要是不给自己刮胡子,那你来我这,我就给你刮胡子,不要钱我也给你刮。那么罗素就问了,假如真的有这样一个理发师的话,他应不应该给自己刮胡子呢?他如果给自己刮胡子,他就是一个给自己刮胡子的人。那么他不应该给自己刮胡子,对不对?按他的说法。他如果不给自己刮胡子,他就是一个不给自己刮胡子的人。他就应该给自己刮胡子,他到底给不给自己刮胡子?

造成“理发师悖论”的原因就是:这里面的‘给自己刮胡子的人’这一个概念模糊造成的。把这个概念明确后,“理发师悖论”就迎刃而解了。我们可以把这个‘给自己刮胡子的人’进行三个定义:1、只要心里想了要给自己刮胡子那他就是‘给自己刮胡子的人’;2、只是心里想了要给自己刮胡子还不行,他需要至少给自己刮一根胡子,那他就是‘给自己刮胡子的人’;3、只是心里想了要给自己刮胡子不行,他需要给自己的胡子全部刮干净,并清洗干净,他才是‘给自己刮胡子的人’。只要这三个概念明确,不管你认可用哪个概念定义‘给自己刮胡子的人’这个悖论都会被破解。

证明四色定理的意义

对于一个具体的平面地图来说,用四种颜色着色不是一件很难的事,那么证明了四色定理有什么意义呢?笔者认为至少有以下两个意义,第一,是对于一个无限大的平面地图如何用数学归纳法进行证明的探索。第二,通过对四色定理对研究,发现了其中的网状链式结构,这个是平面上的一个普遍存在的结构。通过对网状链式结构的研究,我们可以发现其中的一些奥秘,四种颜色可以同时产生六条色链,可以通过对色链进行换色使地图的着色千变万化。

二、由四色定理引发的一些新想法及课题

可以根据四色定理的原理开发一套四色围棋(或四色围棋软件),它和目前的黑白两色围棋主要的区别就在于四色围棋用四种颜色棋子且不允许在直线相邻的两个点上着同一种颜色的棋子,可以2、3、4个人对弈,两种颜色为一组,这样给下棋增加了难度也增加了下棋的乐趣。

下面是我们所要说的几个研究课题,希望能和对此感兴趣的人士共同探讨:

研究课题之一:通过四色定理的证明,使我们历经160多年发现了里面的网状链式结构,既然这个网状链式结构那么不容易被发现,我们能否利用他编制一种加密程序哪?我们相信通过对这方面研究一定会有所收获。

在一个平面地图用四种颜色着色,可以同时产生六条色链,有一加一大于二的效果。根据这个原理,我们在一张地图上选择一个色链的某一段作为加密信息,就会很难被破解,从而实现加密的目的。这是一个最基本的想法,具体怎么实施,需要在实际运作时不断改进。

研究课题之二:根据网状链式结构的特点研究新材料、新工艺。比如:用几种材料混合为新的复合材料;这个在当今社会上是人们比较关注的一个学科,而且人们也在不断的进行研究,也出了很多的成果,比如现在建筑上大量应用的混凝土就是人为将石子、砂粒、水泥及水混合而成的,我们可以根据网状链式的原理结合以往人们的研究方法研究新的复合材料相信也会有所收获。

研究课题之三:自古以来人们对太空的探索一直没有停止过,我国在这方面也取得了很大的成就。这个虽然和四色定理无关,但是我们对它也非常感兴趣。碟状飞行器是这些年人们热议的话题之一,通过对网上相关视频及图片资料的研究,我们发现这种碟状飞行器,可以克服地球引力,飞行速度很快,飞行时几乎没有声音,可以在空中悬停,这使它不但节约能源,还不需要传统飞机跑道的限制,而且这种飞行器可以做的很大。虽然目前认为它是外星文明的产物,但是它既然能被我们发现,说明它是存在的,既然外星人能制造出来,我们也应该能制造出来。它才是我们未来飞向太空理想的工具。相信通过大家的不懈努力,我们在不远的将来也能生产出这样的飞行器。