数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 782|回复: 2

解决四色问题的关键是化无穷为有穷

[复制链接]
发表于 2019-1-19 07:51 | 显示全部楼层 |阅读模式

解决四色问题的关键是化无穷为有穷
雷  明
(二○一九年元月十六日)
(在这里我不会发图,请到《中国博士网》中去看)

1、把一个地理学中的问题转化成一个数学问题
在地图中,把相邻的国家都染成不同的颜色,一张地图最多四种颜色就够用了。这就是1852年英图的绘图员法朗西斯在给英国地图染色时,提出的地图四色猜测。从图论上讲,地图不仅是一个平面图,而且是一个3—正则的平面图。其每一个顶点都连着3条边界线(即边),也就是所谓的“三不管地区”。对地图中面(区划)的染色,就是对地图的对偶图——极大平面图的顶点着色。这就把一个地理学上给地图中面的染色问题转化成了一个数学中给平面图的顶点着色的问题了。只要把极大平面图的四色猜测证明是正确的了,则地图四色猜测也就是正确的了。又因为极大平面图经去顶(点)或减边过算而得到的任意平面图着色时,所用的颜色数只会比极大平面图所用的颜色数减少,而不会再增加,所以,极大平面图的四色猜测证明是正确的了,则任意平面图的四色猜测也就是正确的了。
2、把无穷多的平面图转化成有穷多的构形
平面图有无穷多个,不可能一个一个的去进行着色,而且也是不可能着色完的。那么就必须把无穷多的平面图转化成有穷多的“构形”。所谓构形就是在一个平面图中,除了一个顶点未着色外,其他顶点均已用四种颜色着色,并且符合着色要求——相邻顶点不用同一颜色——的色图。把未着色的顶点叫做“待着色顶点”,把与待着色顶点相邻的顶点叫做构形的“围栏顶点”。待着色顶点与多少个围栏顶点相邻,也即连结着多少条边,在图论中就叫做待着色顶点的“度”是多少。不同的构形,围栏顶点数也都是不同的。所以,也可以说构形的围栏顶点数也是任意的,无穷多的。这该如何办呢?
坎泊早已证明了在任何地图中,总存在着一个国家与两个国家相邻,一个国家与三个国家相邻,一个国家与四个国家相邻和一个国家与五个国家相邻这四种情况中的一种或几种情况,任何国家都是与六个及六个以上的国家相邻的地图是没有的;而在图论中也可以证明任何平面图中总存在着一个或几个顶点的度是小于等于5的顶点,全部顶点的度都是6以上的平面图是不存在的。这样就可以做到在着色时,一定可以把待着色顶点安排在度是小于等于5的顶点上。使得构形的围栏顶点数由无穷转化为有穷。把无穷多的平面图转化为有穷多的、围栏顶点数是小于等于5的六种构形了。
3、1879年坎泊对四色猜测进行的有“漏洞”的证明
把由围栏顶点中的任意两个对角顶点的颜色交替着色的“顶点—边—顶点”所构成的序列叫做“色链”,简称“链”。该链若在两个对角顶点间是从一个顶点一直连结到其对角顶点时,则称为“连通链”,否则该链就是不连通的。把交换某链中各顶点的颜色的过程叫做“颜色交换”,简称“交换”。把从构形的某一个围栏顶点开始的对角链的交换,叫做“对角链交换”。只有不连通的对角链交换后,才可以从围栏顶点中空出一种颜色给待着色顶点。而连通的对角链交换后是不能空出颜色的。
1879年坎泊只运用了对角链的交换,证明了0—轮(即K1图)构形,1—轮(即K2图)构形,2—轮(即2—重的K3图)构形,3—轮(即K4图)构形,4—轮构形以及5—轮构形中无连通链的构形,有一条连通链的构形,有两条连通链,但两链只有一个共同的起始顶点,或者在中途两链只有交叉顶点的构形是可约的(即可4—着色的),是可以从构形的围栏顶点中空出一种颜色给待着色顶点着上的。所以对角链交换法也可叫做空出颜色的交换。而坎泊在证明中却遗漏了对两条连通链既有共同的起始顶点,且中途两链又有交叉顶点的构形的是否可约进行证明。这一遗漏在1890年被赫渥特用其构造的赫渥特图揭示了出来。但当时坎泊和赫渥特两个人都没有能对这个图进行4—着色。而在整整的过去了一个世纪之后,一直到了1990年,才有我们中国的雷明和懂德周,英国的米勒等,对赫渥特图在赫渥特原着色的基础上进行了4—着色。后来又有我国的张域典,刘福,颜宪邦,许寿椿等人,也都对赫渥特图进行了4—着色。
赫渥特图只是一个个别的图(也可以说是一个构形,因为其中还有一个顶点未着色),只对这一个图或构形进行了4—着色,还不能从根本上说明四色猜测就是正确的。而是要对具有赫渥特图结构特点的一类图都证明了其是否是可4—着色的时候,才能得出四色猜测是否是正确的结论。所以说,目前解决四色问题的关键,就是要解决好具有赫渥特图结构特点的一类图(即H—构形)的可约性的问题。
4、把无穷多的H—构形转化成有穷的不可免构形
现在仍以BAB型的5—轮构形为例来进行说明。H—构形中都有连通的、且既有同一个起始顶点,中途又有交叉顶点的A—C链和A—D链,所以该两链也都是不能进行交换的,也是空不出颜色A、B、C三色之一来给待着色顶点着上的。因为H—构形又是不可能连续的移去两个同色B的构形,所以暂时B—C链和B—D链也还是不能进行交换的。而可以交换的链现在就只有A—B链和C—D链了。因为A—B链和C—D链又是一对“相反色链”(即两链中的四种颜色都是完全不相同的颜色),所以A—B和C—D两链也一定是不可相交叉的。

根据构形的结构特点,可将H—构形分成三类:第一类是含有构形的三个围栏顶点的A—B环形链的构形(如图1);第二类是含有构形的两个围栏顶点的C—D环形链的构形(如图2);第三类是不含任何环形链的构形(如图3和图4)。当然也还有既含有A—B环形链,又含有C—D环形链的一类构形,但它们却可以分别属于以上的第一类和第二类构形,所以这里就不再单独列为另一类别了。以上图1到图4中的构形,待着色顶点采用了隐形画法(不画出待着色顶点的画法)。图中除了6C和7D是单边外,其余各边均可看成是由该边的两个端点顶点的颜色所构成的色链。图中只画出了主要的链的关系,其他的顶点和边均未画出,所以可以认为以上的图是极大的平面图,也可以认为是任意的平面图。但未画出的顶点都是只用了A,B,C,D四种颜色之一着色的顶点,且符合着色的要求——即相邻的顶点不用同一种颜色。
这三类构形就是H—构形的“不可避免的构形”,简称“不可免构形”。由以上三类构形就构成了H—构形的“不可避免的构形的集合”,简称“不可免集”。该集中的各个不可免构形,均含有两条既有共同起始顶点2的,在中途又含有相交叉顶点8的连通的A—C链和A—D链,所不同的只是A—B链和C—D链的分布结构不同。除了这三种情况以外,A—B链和C—D链就再也没有别的分布组合了,所以这个不可免集也是完备的。
5、各类不可避免的H—构形的可约性
图1的第一类H—构形的解决办法是交换经过该构形两个相邻的围栏顶点4和5的C—D链,使图中原有的A—C链和A—D链均可变成不连通的,图成为K—构形而可约(如图5);而图2的第二类H—构形的解决办法则是交换经过该构形三个连续相邻的围栏顶点1、2和3的A—B链,使图中原有的A—C链和A—D链也就均可变成不连通的,图也成为K—构形而可约(如图6)。
由于解决这两类构形的方法,都是首先使连通且既有共同起始顶点的,中途又有交叉顶点的两条链A—C和A—D断开了,破坏了形成H—构形的必要条件,因此,该方法也可以叫做“断链法”。由于断链法交换的是由构形的围栏顶点的邻角顶点颜色构成的链,所以也可以叫断链法为“邻角链法”,以区别于坎泊证明四色猜测时所交换的都是对角链的“对角链法”。由于断链法交换是不能直接空出颜色的,所以最后还是得要用可空出颜色的对角链法交换解决问题。

但图3的第三类H—构形的解决,就不能象图1和图2这样的交换了,因为其中的A—B链和C—D链都不是环形链而是直链,现在就只能交换B—C链和B—D链之一,使构形转型,并使图直接变成K—构形或者先变成上面的第一类、第二类H—构形,再进行解决。否则,若不能变成这三种构形时,就只能再继续进行同方向的转型交换了,直到能够转化成以上三种构形,能够空出颜色为止。图3与图4是实际上是同一类构形,只是左右不同罢了,所以只研究图3一个就可以了。
对图3从顶点1交换B—D链时(一次转型交换),产生了从顶点3到顶点5的连通链B—C(如图7),虽不能连续的移去两个B,但图5却是一个可以连续的移去两个同色D的K—构形。当对图5从顶点4交换D—A链时(二次转型交换),不能生成从顶点1到顶点3的连通链D—B(如图8),这就可以再从顶点1交换D—B链,连续的移去两个同色D,或者从顶点2交换B—D链,空出B来(图请读者画)。

图8虽然没有从顶点1到顶点3的连通链D—B,但在平面图范围内,却有生成该链的可能(如图9),这样就成了不可能连续的移去两个同色D的构形了,只有再继续进行转型。对图9从顶点2交换A—C链时(三次转型交换),同样的也有从顶点4到顶点1生成连通的A—D链的可能(如图10)。对图10从顶点5交换C—B链时(四次转型交换),也还有可能有再从顶点2到顶点4生成连通的C—A链。但到第五次转型交换时,就永远不可能再产生从另一个同色顶点到其对角顶点的连通链了。说明再进行一次交换就可以空出颜色来。总共是六次交换。请读者自已试试,完成作图。

若对图3从顶点3交换B—C链时(一次转型交换),产生了从顶点1到顶点4的连通链B—D(如图11),虽不能连续的移去两个B,但图11却是一个第二类的H—构形了,图中有了含有构形两个围栏顶点的A—B环形链,已是可约的了(如图6那样)。当对图11再从顶点5交换C—A链时(二次转型交换),也有可能生成从顶点3到顶点1的连通的C—B链(如图12)。继续转型下去,同样的也是在五次转型交换时,就永远不可能再产生从另一个同色顶点到其对角顶点的连通链了。第六次交换后就空出了颜色。也请读者自已完成作图。
第三类构形在连续转型交换的中途可直接转化为K—构形,或者可以转化成第一类和第二类构形。若改用断链法时,仍可以在六次交换内空出颜色。但对于轴对称的第三类构形(如图13)来说,在第三次转型交换后就可得到一个既是第一类,又是第二类的构形(如图14),改用断链法后,虽然也可以在六次交换内空出颜色。但在连续转型交换时,两个方向的转型交换,却都必须要进行六次交换才能空出颜色。

6、H—构形的最大交换次数是9的证明
通过以上的研究可以看出,第一类和第二类的H—构形,无论是用属于该类构形单独的解决办法,还是用连续转型交换的方法,最大的交换次数均是不会大于5的;对于第三类的H—构形,用连续转型交换的方法,交换的次数最大都是6。这是否可以说,任何H—构形解决时,交换的次数都是不会大于6的呢。不,还不能这么简单的下结论。
因为我们对第三类构形所进行的交换都是从两个方向进行的连续转型交换,两个方向均在第四次交换后,图才变得不再是H—构形了;第四次交换后的图是可以连续的移去两个同色的K—构形,第五次交换后的图则是一个更普通的K—构形,第六次交换后的图就已经是空出了颜色给待着色顶点着上的图了,着色结束。而第三次、第二次、第一次交换后的图以及第三类构形的标准原图——图3,则都是第三类H—构形的图,共七种。可见,这七种第三类H—构形中的任何一种,无论是从那个方向进行转型交换,最大的交换次数一定都是不会大于9的。其中最后三次交换对于任何一种第三类H—构形来说,都是必须的。而其中倒数第三次交换是把H—构形变成可以连续的移去两个同色的K—构形的转型交换,而倒数第二次、倒数第一次交换都是属于空出颜色的坎泊交换,并且都是在K—构形间进行的;而前面的一次到六次的交换则都是在第三类H—构形间进行的,而且是在构形的峰点位置不同的构形间进行的转型交换。但构形仍属于第三类H—构形,这一到六次的交换,对于每一种第三类H—构形来说,所占用的次数却是不相同的。现在,再用下面的图来解释一下(如图15):

在图15中,字母表示构形的类型,数字是交换的次数,箭头是转型交换时行的方向。H0是第三类H—构形的标准图——图3或图4的原图,H1、H2、H3分别是H0向两个方向转型交换1、2、3次后,所得到的第三类H—构形, K4是可以连续的移去两个同色的K—构形,K5是只有一条连通链的普通的K—构形,K6是已着色完成的图。图中共有七种第三类的H—构形,即一个H0,两个H1,两个H2和两个H3。向右是逆时针方向的转型交换,向左是顺时针方向的转型交换。从图15还可以看出,解决H—构形的着色时,交换的最小次数是3,而最大次数则是9。其实最大交换次数是几是关系不大的,关键的问题是这个最大交换次数只要是“有限”的就可以了,就能说明H—构形一定是可约的,也一定是可4—着色的。
我已经把那个轴对称的第三类构形(如图13),在顺时针转型交换的第三次交换所得的图(构形)的基础上,进行了逆时针方向的转型交换,的确是需要9次交换才能空出颜色来。
7、四色猜测是正确的,可以上升为四色定理了
以上就证明了任何不可免的H—构形都是可约的,加上坎泊已证明了的不可免的K—构形也都是可约的,则所有平面图的各种不可免构形就都是可约的了。这就证明了极大平面图的四色猜测是正确的,当然地图四色猜测和任意平面图的四色猜测也就都是正确的了。四色猜测是正确的,是可以上升为四色定理了。证毕。

雷  明
二○一九年元月十六日于长安

注:此文已于二○一九年元月十四日在《中国博士网》上发表过,网址是:
您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2024-3-29 17:58 , Processed in 0.076172 second(s), 15 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表