数学中国

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

四色猜测的最终证明——正确! ——证明四色猜测的关键问题是解决颜色冲突问题

[复制链接]
发表于 2021-3-5 18:46 | 显示全部楼层 |阅读模式

四色猜测的最终证明——正确!
——证明四色猜测的关键问题是解决颜色冲突问题
雷  明
(二○二一年元月三十日)
(图没有发上来,请到《数学中国》中去看)

摘要:先把地理学问题转化成数学问题。再把构形围栏顶点数从任意数转化为1—5的有限个轮构形。其中可以构成颜色冲突问题的只有4—轮和5—轮的两种构形。不含双不交叉链的构形坎泊早已证明是可约的了,4—轮构又是不可能形成双环交叉链的,所以目前的关键问题就是解决5—轮构形中的颜色冲突问题。含有双环交叉链的5—轮构形中有四个关链的顶点,只要有一个关键顶点的颜色有了变动,构形就可转化成无双环交叉链的可约构形了。5—轮构形中除了可以连续的移去两个同色的构形已是可约的外,其他的构形可以分为两类:一是可以断开双环交叉链的构形,用断链交换法解决:另一类是不可以断开双环交叉链的构形,用转型交换法解决,并且最大的转型次数一定能在7次转型之内解决。
关键词:四色问题  四色猜测  构形  双环交叉链  关键顶点  环形链  断键交换  转型交换  有限转型次数的上界值
   
所谓颜色冲突问题,有人也叫染色困局。就是当遇到了与要着色的待着色顶点相邻的顶点已占用完了四种颜色时的情况,这时,该待着色顶点应如何着色的问题。
1、把无穷问题转化成有穷问题:
四色问题因给地图着色而引起,证明时还得先从地图开始。地图是一个3—正则的平面图,每个顶点的度都是3(即三界点)。给地图的“面”上的染色就是对其对偶图——极大平面图——的“顶点”着色。这就把一个地理问题转化为一个数学问题了。
极大平面图的每个面都是3—边形面,每个顶点都是处在一个轮形图的中心顶点,所以在对极大平面图着色时,在着色的中途,特别是在着色的最后,都一定会遇到待着色顶点的所有轮沿顶点都已着色的情况。把这种只有一个顶点未着色,而其他顶点都已进行了4—着色的图,叫做“构形”,把与待着色顶点相邻的顶点叫“围栏”顶点。
极大平面图中的任何一个顶点都有可能作为待着色顶点,其度也是任意的。而在图论中已经证明了,任何平面图中一定存在着度是小于等于5的顶点。这样,待着色顶点的度是小于等于5的轮构形,就成了(极大)平面图中的“不可避免构形”。这就又把一个无穷问题又转化成了一个有穷的问题。研究四色问题时,只要研究度是小于等于5的待着色顶点的着色问题就可以了。因为在对极大平面图着色时,一定是可以把最后的待着色顶点放在度是小于等于5的顶点上。
如果极大平面图的四色猜测被证明是正确的,则用四种颜色着过色的极大平面图,经“去顶”和“减边”后所得到的任意平面图中,所用的颜色数只会减少,而不会不再则增大,所以也就引出了任意平面图的四色猜测。

2、什么是颜色冲突问题:
着色时,最后所剩下的待着色顶点的围栏顶点数是小于4或围栏顶点所占用的颜色数也小于4时,该待着色顶点一定是至少还有一种颜色可着的;而把围栏顶点数是4或5,围栏顶点所占用的颜色数等于4时的情况,就叫做发生了颜色冲突。坎泊(Kempe)早在1879年就已经解决了极大平面图中度是4和5的、但不含有双环交叉链的不可避免构形在发生了颜色冲突时的可约性的问题(即可4—着色的问题),而却把含有双环交叉链的这一情况遗漏了。

所谓的双环交叉链,即是在BAB型的5—轮构形中,A—C链和A—D链不但各分别是连通的,而且两链在中途又是相交叉的,且又都与待着色顶点V构成了一个“环”,所以叫双环交叉链(如图1)。
因此,目前研究四色问题,主要就是要解决度是5的、含有双环交叉链的不可避免构形,在发生了颜色冲突问题时的可约性的问题。
有双环交叉链的构形的存在,是在1890年赫渥特(Heawood)所构造的赫渥特图(H—图)中发现的,后来在1921年埃雷拉(Errera)所给出的埃雷拉图(E—图)中也含有双环交叉链,随后很多研究人员也都相继的发现了这一问题。
图1中的A—C链和A—D链有共同的起始顶点2A和交叉顶点8A,两链的末端顶点分别是5C和4D。这四个顶点就是这类含有双环交叉链的构形中的关键顶点。四个顶点中只要有一个顶点的颜色发生了改变,就不存在双环交叉链了,也就成了坎泊已证明过的是可约的构形了。但双环交叉链也可能有不能断开的情况,所以有双环交叉链的构形又可分为两类:一类是双环交叉链可以断开的构形,另一类是双环交叉链不可以断开的构形,决没有第三种情况的可能。这就是有双环交叉链的构形的两种不可避免的颜色冲突构形。
3、用断链交换法解决可以断开的双环交叉链的颜色冲突构形:
在什么条件下才能使双环交叉链断开呢?现分析如下。
如果构形中含有经过了关键顶点2A或8A的环形的A—B链,该链就一定把经过关键顶点4D和5C的C—D链与其他经过了双环交叉链A—C和A—D的C—D链分隔在了A—B链环的内、外两侧。交换经过4D和5C的C—D链,A—C链和A—D链两条链均没有了各自的末端顶点,当然双环交叉的A—C链和A—D链也就断开了。
如果构形中含有经过了关键顶点4D和5C的C—D环形链,该链也就把经过了关键顶点2A或8A的A—B链与其他经过了双环交叉链A—C和A—D的A—B链分隔在了C—D链环的内、外两侧。交换经过了2A或8A的A—B链,A—C链和A—D链两条链就没有了共同的起始顶点或相交叉顶点,A—C链和A—D链当然也就断开了。
构形中只要没有了双环交叉链,也就转化成了坎泊已证明过是可约的无双环交叉链的可约的构形了。这种交换的方法叫断链交换法。所依据的理论是一对相反色链是不可相互穿过的原理。这类构形的主要特征是含有经过了关键顶点的环形链,所以又叫做含有经过了关键顶点的环形链的构形。
1935年欧文•基特尔(Irving·Kittell)就是用的断链交换法解决了含有经过了双环交叉链的共同起始顶点的环形链的E—图构形的4—着色问题的(见欧文•基特尔的《对已部分4—染色地图的一组操作》一文,以及琼·哈钦森和斯坦·马车的《肯普再研究》一文。当时他们叫做“正切链法”,也就是在经过了双环交叉链的共同起始顶点的环形链外,从双环交叉链的两个末端顶点开始,交换了由双环交叉链的两个末端顶点的颜色构成的色链,E—图构形就转化成了不含有双环交叉链的可约构形了。欧文用的正切链法,实际上就是我们这里的断链交换法);1990年雷明也是用断链交换法解决了含有经过了双环交叉链的两个末端顶点的环形链的赫渥特图(H—图)构形的4—着色问题的(雷明曾于1992年3月8日在西安空军工程学院(今西安空军工程大学)召开的陕西省数学会第七次代表大会暨学术交流会上作了题为《赫渥特图的4—着色》的学术论文报告)。
当然,不含有经过了关键顶点的环形链,但有局部的环形链A—B或C—D,把经过了双环交叉链的相反链C—D或A—B分隔在环的两侧时,交换环形链内侧的一支短一些的相反链,也会使构形转化为无双环交叉链的可约构形了(如张彧典先生《四色问题探秘》一书中的“第八构形的放大图那样的构形)。
4、用转型交换法解决不可以断开的双环交叉链的颜色冲突构形:
这类构形的主要特征是不含有经过了关键顶点的环形链,A—B链和C—D链各都是一条直链,当然就不可能进行交换了,双环交叉链也就不可能再断开了。这类构形也可以叫做不含有经过了关键顶点的环形链的构形。所以这类构形也只能先用转型交换法使构进行形转型了,然后再看转型后的构形属于那一类的构形。所谓转型就是先从两个同色顶点中的一个顶点起,交换与其对角顶点的颜色构成的色链,构形就可以由原来的BAB型转化成DCD型(逆时针方向转型)或CDC型(顺时针方向转型)了。

现在要问,这类构形在转型交换时会不会象埃雷拉E—图构形(如图2,待着色顶点V是隐型画法)那样,产生无穷循环的现象而空不出颜色的情况呢?不会的。因为E—图中含有经过了关键顶点——双环交叉链的共同起始顶点A——的环形的A—B链(如图2中的加粗边),而我们研究的这类构形中根本就不存在这样的环形链,所以一定会在有限次的转型之内解决问题的,一定是不会出现无限循环转型的。那么现在还要问,这个“有限次”的“上界”是多少呢?因为不解决其上界的问题,仍然等于是无界的,无界也可能就是无穷的。
因为如果不证明这个转型次数是有界的,也就不能说明它不是无界的。只要存在一个转型次数是无界的构形,或者说转型次数是无穷的构形,就说明至少有一个构形是空不出颜色来给待着色顶点着上的,也就说明了四色猜测是不正确的。这当然也是一种证明四色猜测的方法,但这种构形却是一下子找不到的;而只要能证明了转型的次数是有界的,那么就能够说明任何构形都是可以在有限次的转型之内,空出颜色来给待着色顶点着上的,四色猜测也就得到证明是正确的了。
E—图构形在转型时,是以每4次转型为一个小周期的小循环和以每20次转型为一个大周期的大循环的无穷循环的构形。一个大循环周期内包含着5个小循环。而这里所研究的这类构形的转型次数既然是有限的,且又不会产生循环,那么就必须在E—图构形的第二个小循环周期形成之前,即最多转型7次就会结束转形。转化成一个仍然是含有双环交叉链的、但可以连续的移去两个同色的可约构形,或者是转化成一个含有经过了关键顶点的环形链的可约构形,可以改用断链交换法进行处理。而且转化成前者的情况一定是不会发生在转化成后者的后面的,最大是时发生。
这个结论是否正确呢?还必须要进一步进行证明。下面专门对其进行逻辑方面的证明。
5、不含有经过了关键顶点的环形链的构形转型次数不大于7的证明:
BAB型的5度顶点的颜色冲突情况,A—C和A—D链都是不能交换的,是空不出A,C,D三种颜色之一的。该构形可分为两种,一种是可以移去两个同色B的可的构形,二种是不可以移去两个同色B的构形。不可以移去两个同色B的构形也还可分为两种,一是有经过了关键顶点的环形链的构形,用断链交换法进行解决,二是无经过关键顶点的环形链的构形,用转型交换法进行解决。有环形链的构形又分为两种,一是有A—B环形链的构形,交换C—D链即可解决,二是有C—D环形链的构形,交换A—B链也即可解决。有环形链的构形用断链交换法已经解决,而无环形链的构形因无环形链,A—B链和C—D链也是不能交换的,又不能连续的移去两个B,那就只有先移去一个B,进行转型,再看转型后的构形是个什么构形了。也就是说现在就剩下证明无环形链的构形的转型次数是有限次的上界值了。这个问题解决了,四色问题也就解决了。
由于E族构形在转型交换时,是一个无穷循环转型的构形,永不可能空出颜色来给待着色顶点。但E族构形中却含有经过了关键顶点的环形链,所以E族构形却可以用断链交换法使图转化成可约的构形,使颜色冲突问题得到解决。
而非E族构形中的有经过了关键顶点的环形链的构形,也因与E族构形同样都有环形链,所以也可以用断链交换法解决问题。
非E族构形中的无经过关键顶点的环形链的构形,因无环形链而不能用断链交换法,而只能采用连续转型交换法解决。也由于其没有环形链,相对于有环链的E族构形来说,也是不能用断链交换法的,而只能用连续转型交换法。且转型的次数不会是E族构型那样——无穷的循还转型,而应是有限次的且非循环的有限次连续转型。E族构形的小循环周期是4次转形,那么只要不达到第二个循环周期——8次转型,就不会产生构形峰点类型的循环。所以连续转型的转型次数是不会大于7次的。
现在,有限次转型次数的上界值已经确定,然后再用逆否命题与原命同真同假和逆命题与原命是同真,逆命题是真是原命题成立的充要条件进行逻辑证明,就可以了。无经过关键顶点的环形链的颜色冲突构形转型次数的有限性可以这样证明。
设A是某类构形经有限次转型。B是可以转化成可约构形。这里,某类构形是指无环型链的构形;可约构形在这里是指可以连续的移去两个同色的构形,或含有经过了关键顶点的环形链的构形;有限次这里指的是7次转型。
则原命题从A到B是:无环形链的构形经有限次转型就可以转化成可约的构形。其逆否命题从—B到—A是:通过转型转化不成可约构形的构形一定是无穷转型的构形。这个逆否命题是真的。具体的说就是有E族构形是这样的例子。的确E族构形转型次数是无穷的,永远也不可能通过转型转化成可约构形。
根据原命题与逆否命题具有同真同假的性质,可以判定原命题无环形链的构形经有限次转型可以转化成可约构形的命题是真命题。
现在可以进行验证如下。
其逆命题从B到A是:可以通过转型转化成可约构形的构形的转型次数一定是有限的命题是真命题。无环形链的非E族构形都是这样的。原命题与逆命题同真,说明逆命题为真是原命题成立的充要条件。没有逆命题成立,原命题一定不成立,有了逆命题成立,则原命题也一定成立。这就用不同的方法都证明了有环形链的构形的转型次数一定是有限的结论是正确的。
无环形链的颜色冲突构形的最大转型次数的上界7次是这样确定的。由于其转型次数已证明是有限的,所以,只要是循环转型都是不可能存在的。那么这类构形的转型就只有在E族构形的第二个小循环周期形成之前结束。因为转型次数达到8次时,就会出现小循环现象。两个小循环周期共计是8次转型。在两个周期之前,结束转型,那么,最大转型次数的上界值就是7次了。着色的实践也己经证明了该类构形的确是在7次转型之内就可以解决问题的。
以上就是我对无环形链的构形转型次数的有限性的证明。先证明经有限次转型就可以转化成可约构形的结论是正确的,再证明最大转型次数的上界值是7次。
6、四色猜测是正确的:
到此,应该说四色猜测的证明已经结束了,四色猜测是正确的。因为我们在前面已经说过了,“目前研究四色问题,主要就是要解决度是5的、含有双环交叉链的不可避免构形,在发生了颜色冲突问题时的可约性的问题。”现在这种构形的两种不可避免的颜色冲突构形都已经证明是可约的了,那么就应该说四色猜测是正确的,四色问题就得到了解决。从证明开始到证明结束,除了示意什么是含有“双环交叉链”的构形和E—图构形中的“经过了关键顶点的环形链”画了两个图外,再也没有画一个图和给任何一个图进行过着色。实现了我于1992年在西安作学术论文报告最后所说的“不画图不着色证明四色猜测”的想法。

附录:用着色实践检验上术结论是否正确:
为了检验无经过关键顶点的环形链的构形转型的最大次数的正确性,我们再举几个实际着色的例子,看看其转型次数与上面正文中用逻辑推理所得出的结果是否一致。
1、用非极大图的构形进行验证
图3是一个无经过关键顶点的环形链的BAB型的含有双环交叉链的非极大图的构形。对该构形进行不同方向的连续转型,如果某次转型从一个同色顶点交换了与其对角顶点的颜色构成的色链后,不能新生成从另一个同色顶点到其对角顶点的连通链时,应该说问题就已经得到解决,可以连续的移去另一个同色,空出两个同色顶点用过的颜色,给待着色顶点着上。颜色冲突问题就可以得到解决。

但我们却有意的不去这样做,而是在平面图许可的范围内,增加顶点或边,人为的构造从另一个同色顶点到其对角顶点的连通链,使图仍是一个不可以连续的移去两个同色的构形,再继续的进行转型。如果在后续的某次转型后,不再可能人为的构造从另一个同色顶点到其对角顶点的连通链时,这时的转型次数再减去1,就是转化成可以连续的移去两个同色的最大的转型次数。结果两个方向转型的最大转型次数都是5次,也都是小于7次的。
2、用极大图的构形进行验证

图4是我仿敢峰先生构造E—图构形(敢峰先生称其为终极图)时的转型演绎法,由图1最简单的双环交叉链开始,构造的一个属于极大图的无经过关键顶点的BAB型的含有双环交叉链的极大图构形。该构形好象是含有经过了关键顶点——双环交叉的A—C链和A—D链的两个末端顶点C和D(图中的两个加大顶点C和D)——的C—D环形链,但该环形链却并没有把另一对关键顶点——双环交叉的A—C链和A—D链的共同起始顶点A和交叉顶点A(图中的两个加大顶点A)——分隔在环形链的两侧,所以不是含有经过了关键顶点的环形链的构形。
    这个构形两个方向转型的最大次数只是4次,也都是小于7次的。逆时针方向转型时,不用转型(即转型次数是0时)就是一个可以连续的移去两个同色B的BAB型的可约构形;顺时针方向转型时,1至4次转型的结果全部都是含有经过了关键顶点的环形链的构形,都可以改用断链交换法提前结束转型;而且第4次转型的结果既是一个可以连续的移去两个同色B的可约构形,也是一个含有经过了关键顶点的环形链的构形。
3、用具体图着色实例进行验证

①  1935年欧文给出的那个无经过关键顶点的环形链的构形(如图5,待着色顶点V是隐型画法),由于其中的A—B链和C—D链都是对于构形的峰点A与5—轮构形的两个底角顶点C和D(即两条双环交叉链的末端顶点)的中点的连线呈对称状态的,所以无论从那个方向转型时,转型次数都是4次,也不大于7。且都在第3次转型时就得到含有经过了关键顶点的环形链的构形,也都可以用断链交换法提前结束转型。
②  张彧典先生的Z—构形中,Z1到Z5和Z11到Z15的十种构形都是属于无经过关键顶点的环形链的构形,转型次数都是在小于7次时,就转化成了可以连续的移去两个同色的可约构形或是转化成了含有关键顶点的环形链的构形。
③  张先生的第八构形的放大图也是无经过关键顶点的环形链的构形,但该构形中却含有局部的环形链,也是可以用断链法使其中一条双环交叉链断链的,从而转化成只有一条连通链的可约构形。
④  前面的图3是标准的无经过关键顶点的环形链的构形,A—B链和C—D各都只有一条,且是非树状的单条道路。各条链中相同颜色的首、尾顶点间,只隔着一个与其呈相反色链的链中的顶点,改变该顶点的颜色为其相反色链中的颜色时,图就转化成含有经过了关键顶点的环形链的构形,可以直接使用断链交换法了。由此也可以看出,无经过关键顶点的环形链的构形,也是可以直接转化成含有经过了关键顶点的环形链的构形的。但这是个个别的现象还是普遍的规律,我们现在还不知道。可以作为一个猜想提出,如果真是这样,平面图的4—着色就更加方便了。
雷  明
二○二一年元月三十日于长安
注:此文已于二○二一年二月三日在《中国博士网》上发表过,网址是:

这次重新发表时,进行了修改,题目也改变了。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

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

GMT+8, 2024-3-29 22:57 , Processed in 0.851563 second(s), 15 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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