数学中国

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

四色猜测是可以手工证明的

[复制链接]
发表于 2017-1-28 11:34 | 显示全部楼层 |阅读模式
本帖最后由 雷明85639720 于 2017-1-30 04:10 编辑

四色猜测是可以手工证明的
雷  明
(二○一七年元月二十六日)

【摘  要】从分析构形的结构入手,构造了完备的H—构形的不可免集,也证明了该集中的所有不可免的H—构形都可以转化成坎泊的K—构形,即都是可约的。加上坎泊一八七九年早已证明了的可约的不可免构形,平面图的所有不可免构形都是可约的了,这就证明了四色猜测是正确的。
【关键词】四色猜测  四色问题  平面图  构形  不可免构形  不可免构形集   链  交换  可约构形

目前研究四色问题,主要只应该研究H—构形是否可约就行了。研究H—构形的可约性问题,首先要知道H—构形有多少种,它的不可免集是什么,有多大。并且要明确什么是H—构形,才能构造出不同结构的H—构形来。
H—构形的定义:H—构形应该是既含有两条相交叉的连通链(两链有共同的起始顶点)的构形,又不能同时移去两个同色的构形。
1、 H—构形的不可免集
根据H—构形的定义及其特征,我构造出了如下五种不同结构类型的H—构形。在这里,我用了两种不同形式的方法画图:一是英国的米勒所使用的待着色顶点是隐形的画法(如图1);二是我国的张彧典先生所使用的待着色顶点是显形的画法(如图2)。这两个H—构形的不可免集实质上是同一个集合,只是图的画法不同而已。从该集合中看,好象是有五个元素(构形),实际上却只有三个不可免构形。

以上的H—构形的不可免集中,明明画了五个构形,为什么又说实际上只有三个呢。这是因为a图中有一条环形的A—B链;b图中有一条环形的C—D链;c图和d图中既没有环形的A—B 链,也没有环形的C—D链,而且两图的结构正好是左右相反的,实际上应该是同一个构形;e图则是A—B环形链和C—D环形链都有的构形,这就是敢峰—米勒图。e图既有a图的特征,又有b图的特征,既可归入a图中,也可归入b图中,因此,它不是一个单独的构形。这样,集合中的构形数目,就只有a图、b图、c图的三个构形了。这就是我构造的H—构形的不可免集,其中只有三个元素,即三个构形。

2、 该H—构形的不可免集完备性的证明
2、1  这三个构形从有没有环形链角度来分:a图、b图、e图皆有环形链;c图、d图皆没有环形链。从环形链的条数角度来分:c图、d图都是0条;a图、b图都是1条;e图只是大于一条的代表。从环形链的种类角度来分:a图只有A—B一种环形链;b图只有C—D一种环形链;c图、d图那一种环形链都没有;e图是两种环形链都有。除了这些外,再没有别的环形链分布模式了。
   2、2  这三个图中的A—C链和A—D链是连通链,都与待着色顶点一起构成了一个环或圈,其链的本身是不可能构成环形链的;由于A—C链和A—D链的连通性,则其相反的B—D链和B—C链就不可能再是连通的了。四种颜色所能构成的六种链中,上述这四种链已经固定,不能变动,那就只有变动另外的两种,即A—B和C—D链了。这就是我们在1中所分析的内容。

2、3  以上图1和图2中的构形,当顶点数减少到九点形图时,分别就变成了与图3和图4中所对应的各图。图1和图2中的e图也就变成了图3和图4中的a图2、4  在图1和图2的a图,b图,c图三个图中,除了5—轮的5条轮沿边和C—7D—6C—D三条边只能是单边外,其他的任何边都可以看成又是由其两个端顶点的颜色所构成的色链,即其中还可以含有别的顶点。如果在C—7D—6C—D这三条边中还有别的顶点时,图就变成了可以同时移去两个同色的K—构形,而不再是H—构形了。关于这一点,读者可以自已画图试一试,看是不是可以同时移去两个同色B。和b图。图3和图4中的这四个图除了b图仍是H—构形外,其他的三图都已变成了可以同时移去两个同色B的K—构形了。

2、5  到此,就证明了再也没有别的构形是H—构形了(四种颜色所能构成的六种色链中,四种已固定,不能再变动,可以变动的两种,各种情况已都考虑到了),所以说,我们上面的图1和图2的H—构形的不可免集是完备的。
    3、 不可免的H—构形可约性的证明
H—构形之所以与K—构形不同,主要是由于其中有A—C和A—D两条交叉的连通链而引起的,A—C和A—D链都是不能交换的。同时,也不能同时移去两个同色B,所以说B—C链和B—D链也是不能交换的。因此,在解决这一类图的着色问题时,我们首先想到的就是能不能把连通的A—C链和A—D链断开,使其变成坎泊的K—构形。只要图变成了K—构形,当然也就可约了。
3、1  对于a图的构形,由于有A—B链是环形的,所以它把C—D链分成了环内、环外互不连通的两部分。又由于环形的A—B链交换后不起任何作用,所以,现在就只有一种C—D链是可以交换的了。当交换了被环形链A—B所隔开的任一部分C—D链后,都可使连通的A—C链和A—D链断开,使图变成为坎泊的K—构形而可约(如图5,以后如何交换,使得待着色顶点周围的顶点所占用的颜色总数由四种减少到三种,就属于坎泊的证明范围了,也就不再画图了);

3、2  对于b图的构形,由于有C—D链是环形的,所以它也把A—B链分成了环内、环外互不连通的两部分。也是由于环形的C—D链不可交换的原因,所以,现在也只有一种A—B链是可以交换的了。当交换了被环形链C—D所隔开的任一部分A—B链后,也都可使连通的A—C链和A—D链断开,使图变成为坎泊的K—构形而可约(如图6,以后的交换同样也属于坎泊的证明范围了)。赫渥特图的4—着色就是用这种方法解决的。把具有这种特点的构形,我们叫它类赫渥特图型的H—构形;
3、3、 以上3、1和3、2中的交换办法,我叫他“断链交换”法,是坎泊所创造的颜色交换技术的又一种应用。而坎泊在证明中只用了他创造的颜色交换技术的一种应用,即“空出颜色”的交换的应用。

3、4  对于e图的构形,由于该图既有环形的A—B链,它把C—D链分成了环内、环外互不连通的两部分,交换其中任一部分C—D链,都可使连通的A—C链和A—D链断开,成为坎泊的K—构形而可约;该图又有环形的C—D链,它又把A—B链分成了环内、环外互不连通的两部分,交换其中任一部分A—B链,也都可使连通的A—C链和A—D链断开,成为坎泊的K—构形而可约。敢峰—米勒图的4—着色用这两种办法都是可以解决的;
3、5  对于c图和d图,由于其中没有环形链,而且A—B链和C—D链均是直链(即是一条道路),且只有一条,即就是交换了,也不起任何作用,图仍不会变成K—构形。而B—C链和B—D链又不能同时交换,不能同时移去两个同色B。没办法,我们就只好先交换一种链,先移去一个B,使图由123—BAB型转化成为451—DCD型或345—CDC型。然后,再视转型后的图的类型再进行研究。

3、6  对于c图和d图转型交换的结果,从不同的两种方向交换看,不同的交换方向,有不同的交换结果:一是转化成了可以同时移去两个同色的K—构形(如图7);另一是转化成了类似图2中b图的有一条环形链的类赫渥特图型的H—构形(如图8,该构形是可以通过断链交换转化成坎泊的K—构形的,如上3、2中所述)。转型交换后,所转化成的两种构形都是可约的。

3、7  这里所说的交换,具有转换构型类型的作用,所以我叫它“转型交换”法,这又是坎泊颜色交换技术的第三种应用。
4、 有环形链的H—构形一定可以通过“断链”交换转化成K—构形的证明
4、1  有A—B环形链的断链交换可转化成K—构形的证明:
因为在A—C链和A—D链中,至少有两对顶点6C与7D和4D与5C是直接相邻的两个顶点(如果没有这两对顶点的直接相邻,图就不可能再是H—构形了),所以,无论A—B环形链是从哪个地方穿过A—C链和A—D链的,也无论是只穿过一条还是两条都穿过,A—B环形链的某一侧至少是存在着这样的两对顶点之一对的。这就保证了无论从其中的哪一对顶点进行C—D链的交换时,都可以使A—C链和A—D链的一条或两条断开,使构形转化成K—构形。赫渥特图就是这样着色的,敢峰—米勒图也可以这样着色。
4、2  有C—D环形链的断链交换可转化成K—构形证明:
因为在A—C链和A—D链中,至少有顶点2A和顶点8A是两条链的公共顶点(如果没有这两个公共顶点,图也就不可能再是H—构形了),所以,无论C—D环形链是从哪个地方穿过A—C链和A—D链的,也无论是只穿过一条还是两条都穿过,C—D环形链的一侧至少是存在着这样的两个公共顶点之一的。这就保证了无论从其中的哪一个公共顶点进行A—B链的交换时,也都可以使A—C链和A—D链的一条或两条断开,使构形转化成K—构形。敢峰—米勒图就是这样着色的。
4、 3  用以上的两种断链方法对图1和图2的a图以及图1和图2的b图着色时,要注意的是两种构形断链时所用以交换的链是不同的。如在a图中有环形的A—B链时,交换的是C—D链,而在b图中有环形的C—D链时,交换的则是A—B链。赫渥特图中只有环形的C—D链,所以其只有一种断链的方法,只能任意交换环形的C—D链两侧的A—B链,使图变成K—构形;而敢峰—米勒图中既有环形的A—B链,又有环形的C—D链,所以其不但可以交换环形的A—B链两侧的C—D链,也可以交换环形的C—D链两侧的A—B 链,都可以使图变成K—构形而可约。
4、4  到此,就证明了有环形链的H—构形一定是能够转化成为坎泊的K—构形的。
5、 无环形链的H—构形一定可以通过“转型”交换转化成K—构形的证明
5、 1  无环型链的H—构形构形可以转化成可以同时移去两个同色的K—构形的证明:
5、1、1  从图4中可以看出,只所以图4,a、图4,c和图4,d可以同时移去两个同色B,是因为两个同色顶点1B和3B中至少有一个B色顶点到A—C链和A—D链两链的交叉顶点8A有一条连通的B—A边。以致从1B交换了B—D后,生成了从顶点8到顶点1的A—D边,使得从3B到5C不可能再有连通的B—C 链;而从3B交换了B—C后,则生成了从顶点8到顶点3的A—C边,也使得从1B到4D不可能再有连通的B—D链;从而可以同时移去两个同色B。
5、1、2、 现在看看图1和图2中的无环形链的H—构形在施行了一次转型交换后,是不是与图4,a有同样的结果呢。对图2,c的构形从1B施行了一次逆时针转型交换后得到图9,a,是一个451—DCD型的5—轮构形。图9,a中C—A链和C—B链的交叉顶点是6C,5—轮轮沿顶点中用了两次的颜色是D,从6C到4D有一条C—D链;当从顶点4交换了D—A后,生成了从6C到4A的C—A链(如图9,b),使得从顶点1D到3B不可能再有连通的D—B链,从而可以移去两个同色D。这就证明了无环形链的H—构形是一定可以转化成为可以同时移去两个同色的K—构形的。对图2,d的构形从3B施行了一次顺时针转型交换后,得到的345—CDC型的5—轮构形,也有同样的结果。


5、2  无环形链的H—构形可以转化成类赫渥特图型的H—构形,再转化成坎泊的K—构形的证明:
在图1和图2的c图(或d图)的构形中,有通过顶点2A—1B—8A—6C—2A(或2A—3B—8A—7D—2A)的缺口是6C(或7D)的A—B圈(如图10,a),当对c图从顶点3交换B—C(或对d图从顶点交1换B—D)时,顶点6C变成了6B(顶点7D则变成了7B),就形成了一条完整的环形链A—B(如图10,b),把C—D链分成了环内、环外互不连通的两部分,构形具有了图1和图2的b图的特点了。是一个类赫渥特图型的H—构形,一定是可以转化为K—构形的。
5、3  到此,就证明了无环形链的H—构形一定是能转化成为坎泊的K—构形的。
6、四色猜测是正确的
以上的H—构形的不可免集已证明是完备的,其中的各个不可免构形也证明都是可约的;那么再加上以前坎泊在一八七九年所证明了的结果,说明了平面图的不可免构形都是可约的。这就证明了平面图的四色猜测是正确的。由于给地图的面的着色就是给极大的平面图的顶点着色,所以也就证明了地图的四色猜测是正确的。所以说四色猜测是正确的。

雷  明
二○一七年元月二十六日于长安
   
作者:雷明,金堆城钼业公司退休职工,高级工程师,退休前任钼业公司教育处处长
注:此文已于二○一七年元月二十五日以《从构形结构角度研究H—构形的不可免集及其不可免构形的可约性》的题目曾在《中国博士网》上发表过,网址是:
,这次修改后题目改成了《四色猜测是可以手工证明的》。修改后的论文也于二○一七年元月二十八日(春节)在《中国博士网》上发表过,网址是:

   

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

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

本版积分规则

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

GMT+8, 2025-7-31 01:49 , Processed in 0.097793 second(s), 16 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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