数学中国

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

断链法证明四色猜测的原理

[复制链接]
发表于 2018-12-11 08:43 | 显示全部楼层 |阅读模式
本帖最后由 雷明85639720 于 2018-12-18 14:17 编辑

断链法证明四色猜测的原理
雷  明
(二○一八年十二月八日)
(这里我发不上图,请到《中国博士网》中去看)

1、H—构形只所以不能空出颜色来,主要是因为图中有连通的A—C链和连通的A—D链,两链不但有共同的起始顶点2A,而且在中途又在顶点8A处相交叉(如图1)。但仅有这一条件还不够,还必须有从1B到7D的B—D链和从3B到6C的B—C链也是连通的(如图1),并且6C和7D间只是一条单边而不是链(如图1),才能保证从一个B色顶点进行关于B的链的交换后,产生从另一个B色顶点到其对角顶点的连通链,以致不可连续的移去两个同色。但也的确存在着这样的构形,虽有连通且相交叉的A—C链和A—D链,却的确是可以连续的移去两个同色B的,如“九点形”构形就是这样的可以连续的移去两个同色B的K—构形(这里就不再画图了)。

2、从图1中可以看出,顶点1A,8A,4D,5C,6C和7D六个顶点,均处在一个特殊的地位,即处在连通且交叉的A—C链和A—D链的一条或两条之上。这6个顶点只要有一个顶点的颜色加以改变,就会使连通且相交叉的A—C链和A—D链的一条或两条同时断开,成为不连通的,使图成为K—构形而可约。而只有交换了经过这些顶点的A—B链,C—D链,B—C链或B—D链时,才能达到这样的目的。同时从图1中还可以看出,由A,B,C,D四种颜色可能构成的六种色链中,A—C和A—D链因为是连通的,不可能再进行交换,也空不出A,C,D三种颜色之一;B—C链和B—D链也只能交换其一,也空出不出两个B色来;现在就只有A—B链和C—D链可以交换了。因为A—B链和C—D链是一对相反色链,所以两链又是不可能相交的。根据图中A—B链和C—D链可能的分布情况,可以把H—构形分为三类不可免的构形:即第一类,有经过1B,2A和3B三个顶点的A—B环形链的H—构形(如图2),第二类,有经过4D和5C两个顶点的C—D环形链的H—构形(如图3),第三类,任何环形链都没有的H—构形(如图4)。

3、断链法对各H—构形进行着色:
第一类,图中有环形的A—B链,交换经过4D和5C(或6C和7D)的C—D链,都可以使A—C链和A—D链同时断开,变成不连通链,使图变成K—构形而可约(见图2)。这类构形的代表就是敢峰—米勒图图。
第二类,图中有环形的C—D链,交换经过1B,2A和3B(或经过8A)的A—B链,也都可以使A—C链和A—D链同时断开,变成不连通链,使图变成K—构形而可约(见图3)。这类构形的代表是赫渥特图。
第三类,图中没有任何的环形链,可交换经过1B和7D(或3B和6C)的B—D(或B—C)链,使A—C链和A—D链中的一条断开,成为不连通链,使图由BAB型的构形变成DCD(或CDC)型的、可以连续的移去两个同色的K—构形,或者变成DCD(或CDC)型的、第二类H—构形。这两种构形都是可约的。我们把这样的交换又叫做转型交换,因为交换一次,图的结构类型就变化一次。这类构形的代表则是张域典先生的第八构形。
对图4若从顶点1交换B—D链时,顶点7D改变颜色为7B(如图5),使连通的A—D链断开,使图变成一个DCD型的可以连续的移去两个同色D的K—构形。再从顶点4交换D—A链,使得连通的由5C到2A的这一条C—A链从8D(顶点8原着色为A)处断开(如图6中打×的顶点),移去了一个D;再从顶点1交换D—B链时,就可以移去第二个D,连续的移去了两个同色D。把D空了出来。
对图4若从顶点3交换B—C链时,顶点6C改变颜色为6B(如图7),使连通的A—C链断开,使图变成一个CDC型的有经过1D和2A两个顶点的A—B环形链的第二类H—构形(如图7)。按解决第二类H—构形的办法解决即可。当在环形的A—B链内交换了C—D链后,使得图7中连通且交叉的D—A链和D—B链的交叉顶点7D的颜色改变成7C(如图8中打×的顶点),D—A链和D—B链两链同时断开,构形成为K—构形而可约。

图4的第三类构形,还有一种与图4是左右完全相反的构形,两种构形是同一类,解决的办法也是相同的。只是交了B—C链和B—D链后所得结果正好相反罢了。
4、第三类构形还有一种情况,即构形有一个A—B链的对称轴(如图9),这就是1935年那个美中人构造的图。该图进行同方向的连续三次转形交换后,得到一个两种环形链都有的CDC型的构形(如图12),既是属于第一类构形,又是属于第二类构形,用解决第一、第二类构形的办法中任一种都可以解决。由于构形的轴对称性,所以该构形从那个方向进行转型交换的结果都是一样的。总共进行了五次交换,比上述非对称的第三类构形多了两次交换。

这种轴对称的第三类构形为什么会比非轴对称的构形多了两次交换呢,我们也进行了研究。发现前两次转型交换是把对称的构形变成不对称的构形(如图11)。我们把第二次转型交换后的图11进行整理,得到图13,这是一个非对称的第三类构形。把图13再进行同方向转型交换一次,同样也得到一个两种环形链都有的、既属于第一类构形,又属于第二类构形的构形。结果与第三次转型交换后的图12是一致的。

对图9的轴对称型第三类构形进行了三次转型交换后的图12,分别按第一类和第二类构形的解决办法,在C—D环形链内、外进行A—B链的交换和在A—B环形链内、外进行C—D链的交换,所得的结果分别如图15,图16,图17和图18。他们都是只有一条连通链的K—构形。

5、还有一种情况,虽然不是一个单独的类别,但也有必要说明一下。如图19的构形,即含有环形的A—B链,又含有环形的C—D链。既是属于第一类构形,又是属于第二类构形。可以分别用解决两类构形的办法解决。

把图19当作第一类构形看待(如图20)时,可以交换环形的A—B链内、外的任一条C—D链,都可使连通且交叉的A—C链和A—D链同时断开,图变成K—构形而可约(如从A—B环内交换了C—D链的图21和从A—B环外交换了C—D链的图22)。

若把图19当作第二类构形看待(如图23)时,也可以交换环形的C—D链内、外的任一条A—B链,都可使连通且交叉的A—C链和A—D链同时断开,图变成K—构形而可约(如从C—D环内交换了A—B链的图24,从C—D环外交换了A—D链的图读者自已作)。

以上对各类H—构形的解决中,都是用了使两条连通且相交叉的链变成不连通链的方法,所以我们叫他断链法。坎泊在证明K—构形都是可约时,用以交换的链都是不连通的;而我们在解决H—构形也是可约时,用的则是断链法:即先要把两条连通链中至少一条变成不连通的链,再交换图中的不连通链,使构形成为可约的。现在就可以清楚的看出解决K—构形和H—构形的不同之处在什么地方了。


雷  明
二○一八年十二月八日于金堆城

注:此文已于二○一八年十二月十一日在《中国博士网》上发表过,网址是:

发表于 2018-12-18 19:59 | 显示全部楼层
雷明,了不起,可喜可贺,虽然我没有看明白,但是,我相信你的证明是正确的,期待您更更多的作品。
 楼主| 发表于 2018-12-18 20:28 | 显示全部楼层
本帖最后由 雷明85639720 于 2018-12-18 12:44 编辑

成飞朋友,有那些不明白的地方,提出来,我立即会给你答复的。不光是答复了你,我再修改后,一定会使更多的人能看明白的。

成飞朋友,以后一定要看明白后再发表赞扬的意见。看不明白,可以提出问题,我会解释得直到你能看明白为止。

成飞朋友,请你到《中国博士网》中去看图,看了图后,会对理解有很大的帮助的。

您需要登录后才可以回帖 登录 | 注册

本版积分规则

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

GMT+8, 2024-3-29 16:00 , Processed in 0.083984 second(s), 15 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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