数学中国

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

四色猜测的理论与实践两种证明方法

[复制链接]
发表于 2020-3-14 18:04 | 显示全部楼层 |阅读模式
本帖最后由 雷明85639720 于 2020-3-16 09:47 编辑

四色猜测的理论与实践两种证明方法
雷  明
(二○二○年三月十四日)
(这里发不上图,请到《中国博士网》上去看)

1、理论证明的方法:
1、1  把地理问题转化成数学问题:
地图是一个无割边的3—正则的平面图,其对偶图是一个极大的平面图。给地图的面上的着色就相当于对其对偶图的顶点着色。只要证明了极大平面图的四色猜测是正确的,则地图四色猜测就是正确的了。同时,由极大平面图通过“去顶”和“减边”所得的任意平面图的色数,则只会减少而不会再增大。所以证明了极大平面图的四色猜测是正确的,则任意平面图的四色猜测也就是正确的了。这就把一个地理问题转化成了数学问题。
1、2  极大平面图的生成:
地图是3—正则的平面图,其对偶图就是所有面均是三边形面的极大平面图。面数最少的地图,如海地岛的地图,其上只有两个国家即海地和多米尼加,四周被海洋“国家”包围着。该地图中只有三个面,其对偶图就是一个K3图极大图,用“增加顶点和边”的办法从K3图开始可得到有任意顶点数的、各顶点的度也是任意大的极大平面图。这些极大平面图一定都是可4—着色的。证明如下:
1、3  极大平面图四色猜测的理论证明:
极大平平面图的生成过程是从顶点数是3的极大平面图K3开始的,K3图只用三种颜色。再在K3图的一个面内增加一个顶点和三条边,可得到一个K4图的极大平面图,该增加的顶点只能用第四种颜色(但不能在K3的边上增加顶点,因为这样增加了顶点后,是不能生成极大图的);从K4图开始,以后再在新生成的极大平面图的任何一个面内增加一个顶点和三条边,所得到的图仍是极大平面图,则该顶点只能用与该面三个顶点不同的第四种颜色;若增加的顶点不在面内,而是在一条边上,则仍要使图保持是极大平面图时,还得要再增加两条新边,共计也是增加了三条边(因为增加的顶点是在边上,把该边已分成了两条)。增加的这个顶点一定是位于一个4—轮的中心顶点上的。根据坎泊的证明,这样的4—轮“构形”一定是可约的,即增加的这个顶点一定是可以着上图中已用过的四种颜色之一的。就这样一直不停的增加下去,就可得到顶点数是任意多的、各顶点的度是任意大的极大平面图,其所用的颜色数总是不会超过4的。这就证明了任何极大的平面图都一定是可4—着色的。
1、4  四色猜测是正确的:
极大平面图的四色猜测是正确的。那么地图的四色猜测和任意平面图的四色猜测也就是正确的了。
证毕。
2、实践证明的方法:
2、1  构形:
实践的方法就是着色的方法。对任何一个极大平面图着色,最后总是要遇到一个将要着色的顶点,其周围顶点都已着上了四种颜色之一的情况。把具有这种只剩下一个顶点未着色的图就叫做“构形”,未着色的顶点叫待着色顶点,把与待着色顶点直接相邻的顶点叫围栏顶点。若与待着色顶点相邻的顶点所占用的颜色数小于等于3时,该顶点至少还是有一种颜色可着的;若与待着顶点相邻的顶点所占用的颜色数已经达到了4时,能否给这个顶点着上图中已过的四种颜色之一,这是解决四色问题的关键。
2、1  把无穷问题变成有穷问题:
图中的任何一个顶点都是可以做为待着色顶点的,由于各顶点的度都是不相同的,所以这看起来好象是一个无穷的问题。但图论中却已证明了任何平面图中一定存在着度是小于等于5的顶点。这就可以把一个看似无穷的问题,转化成一个有穷的问题了。使我们在着色时总可以把最后一个要着色的待着色顶点放在度是小于等于5的顶点上。只要研究度小于等于5的几种待着色顶点,是否可以着上图中已用过的4种颜色之一就可以了。如果这些情况下的待着色顶点,都可以着上图中已用过的4种颜色之一,则四色猜测就是正确的。
2、3  四色问题的实质是减少围栏顶点所占用的颜色数:
解决这一情况的关键问题,是要把与待着色顶点相邻的围栏顶点所占用的颜色数,由4种减少到3种。坎泊1879年已经证明了待着色顶点的度小于等于4的构形和待着色顶点的度等于5的、但可连续的移去两个同色的构形,是可以把围栏顶点所占用的颜色数由4种减少到3种的,待着色顶点一定是可以着上图中已用过的4种颜色之一的。但他却遗漏了一种在待着色顶点是5度的情况下,具有“双环交叉链”的、好象是把围栏顶点所占用的四种颜色不能减少下来的一种情况的构形。这就是1890年赫渥特构造的图。把具有这种图结构特点的图,就叫做赫渥特构形,即H—构形。今天研究四色问题时,主要就是研究对具有双环交叉链的构形的可4—着色的问题。
2、4  H—构形的不可免集:
以下的图1到图6的六个图,不但都含有双环交叉的A—C链与A—D链,同时也都可从任一个同色的顶点B交换了与其对角顶点的颜色构成的对角链后,就可新生成从另一个同色的顶点B到其对角顶点的连通链,不可能连续的移去两个同色B,是六个地地道道的H—构形。

图1是含有经过了三个围栏顶点的A—B环形链的构形;图2是含有经过了两个围栏顶点的C—D环形链的构形;图3是不含有任何经过围栏顶点的环形链的、但A—B链和C—D链都只是一条的构形。但图3改变了其中某个顶点(图中的加大顶点)和颜色后,就可以变成图1或图2的含有经过了围栏顶点的环形链的构形(如图7和图8)。图4到图6同样也是三个不含环形链的构形,但其中的A—B链和C—D链却至少有一个至少是不连通的两段。也可以把这三图与图1或图2同样看待,给待着色顶点进行着色。

H—构形,按A—B链和C—D链的相互依存关系看,就只有以上图1到图6的六种情况,不会再有别的什么情况出现了。说明以上的6个图分别就是H—构形的6个不可避免的构形,由它们共同构成了H—构形的不可免集。这个不可免集是完备的。
2、5  H—构形可约性的解决办法:
看来,解决四色猜测的证明问题,主要就是要解决图1和图2的有环形链的构形中的待着色顶点V的可4—着色问题了。既然是因为有了双环交叉链,才构成了H—构形的,那就要想办法去断开它,使之从连通的链变成不连通的。使图转化成可约的K—构形就可以了。可以看出,只要改变了两链的共同起始顶点2A,两链的交叉顶点8A和两链各自的终了顶点4D和5C的颜色,就可达到断开双环交叉链的目的。

2、5、1  图1中的有环形链A—B的构形,交换A—B环内的经过4D和5C的C—D链(如图9),或者交换A—B环外的经过6C和7D的C—D链(如图10),都可以使双环交叉链断开,使图转化成可约的K—构形而可约。虽然所得到的图9和图10中仍含有两条连通链(如图中加粗的边所示),但却没有真正意义上的“十字”交叉,仍是可以连续的移去两个同色B的。所以该两图仍是可以空出四种颜色中任何一种的可约的K—构形。
2、5、2  图2中的有环形链C—D的构形,交换C—D环内的经过2A的A—B链(如图11),或者交换C—D环外的经过8A的A—B链(如图12),也都可以使双环交叉链断开,使图都转化成可约的K—构形而可约。由于所得到的图11和图12中都含有两条关于两个同色的、连通的、且是交叉的链(如图中加粗的边所示),是不可能通过交换而空出两个同色的,所以该图只能是可以空出除两个同色外的三种颜色之一的可约的K—构形。
以上解决两种有环形链的构形所用的方法就叫“断链交换法”,因为它的交换能使双环交叉链断开。交换的过程是在环形链的内、外交换与其呈相反色链的任一条链即可。或都说是交换经过2A(或8A)的A—B链或者是交换经过4D(或5C)的C—D链。

2、5、3  对于图4到图6的三个图,前面已说了可与图1或图2进行同样看待。均可以视A—B链或C—D链中有一条是环形链,而对其是相反链的任何一条进行交换,都可使双环交叉链断开,使图转化成可约的K—构形而可约。可以看出,实际上H—构形只分成了有环形链的构形和无环形链的构形两大类不可免构形。前者用断链交换法进行解决,后者是在将其转化成前者后,再用断链交换法进行解决,或者可直接用断链交换法进行解决。
2、5、4  再补充一个有环形链的构形:
图1—2是一个A—B环形链和C—D环形链都有的构形。用解决任何一种有环形链的方法解决都可达到断开双环交叉链的目的(如图1—2—1,图1—2—2,图1—2—3,图1—2—4)。虽然图1—2—3和图1—2—4中仍含有两条连通链,但却没有真正意义上的“十字”交叉,所以已不是H—构形而是K—构形了。

2、6  “九点形”构形:
当以上的各图的顶点数均减少到仍含有双环交叉链A—C和A—D的“九点形”构形时(如图13,图14,图15),除只有图2(或图8)的构形所对应的图14仍是H—构形外,而其他的构形所对应的图13和图15均成了可以连续的移去两个同色B的可约的K—构形。可见,含有双环交叉链只是构成H—构形的必要条件,而不是充分条件。少了双环交叉,就构不成H—构形,但有了双环交叉,却不一定都是H—构形。

3、结论:
通过以上对四色猜测从理论和实践两个方面的证明,都证明了极大平面图的四色猜测是正确的,这也就证明了地图的四色猜测和任意平面图的四色猜测也都是正确的。至此,四色猜测就得到了证明是正确的。

雷  明
二○二○年三月十四日于长安

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

发表于 2020-3-15 23:24 | 显示全部楼层
我弱弱地问一句,从单个构型来说4色没有问题,那么你怎么证明几个构型组成的地图,4色够吗?
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-3-16 17:53 | 显示全部楼层
本帖最后由 雷明85639720 于 2020-3-16 10:41 编辑

1、不明白你说的是什么情况下的地图,请你画出图来。
2、地图就只有那几种不可免的情况了,每种情况都是一种地图。
3、这几种情况的地图解决了,任何情况的地图也就都可以解决了。
4、这就是如何把一个无穷问题转化成有穷问题来处理的过程。
5、看来你还是不了解坎泊的不可免构形的真正意义。
回复 支持 反对

使用道具 举报

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

本版积分规则

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

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

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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