数学中国

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

排列组合是证明四色猜测最基本的理论

[复制链接]
发表于 2017-4-20 13:10 | 显示全部楼层 |阅读模式
本帖最后由 雷明85639720 于 2017-4-29 05:48 编辑


排列组合是证明四色猜测
最基本的理论
雷  明
(二○一七年四月二十日)

在证明无割边的3—正则平面图的可3—边着色与其可4—面着色等价的泰特猜想时,就要用到排列组合方面的知识。
1、从可3—边着色到可4—面着色
设一个3—正则平面图是可3—边着色的,即C边=3。该图的每一个顶点都连接着三条边,这三条边一定是三种不同的颜色。
3—正则平面图的每一个面都是由这三种不同颜色的边所围成的,可能是二色边的面,也可能是三色边的面。这是一个组合方面的问题。
把由各种颜色的边组合成的面着上不同的颜色时,就是对该图的面着色。该图面着色的色数C面是:由三个元素中取出两个元素的组合数C2=C =3!/[2!×(3-2)!]=6/2=3,与取出三个元素的组合数C3=C =3!/[3!×(3-3)!]=6/6=1的和,即C面=C2+C3=3+1=4。当一个图中只有二色边的面而没有三色边的面时,这个图面着色的色数就是C面=C2=C =3!/[2!×(3-2)!]=6/2=3。所以就有可3—边着色的无割边的3—正则平面图一定是可4—面着色的结论。
整个图中最多用了多少种颜色呢,也是一个三个元素的各种组合问题。一条边虽不能构成面,但它却也占用了一种颜色,边占用的颜色数是C1=C =3!/[1!×(3-1)!]=6/2=3,所以整个图中最多所用的颜色总数是:C总=C1+C2+C3=C +C +C =3!/[1!×(3-1)!]+3!/[2!×(3-2)!]+3!/[3!×(3-3)!]=3+3+1=7种。的确,3—正则平面图中的边色数与面色数的和就是7。
2、从可4—面着色到可3—边着色
    设一个3—正则平面图是可4—面着色的,即C面=4。所用的颜色分别是A、B、C、D四种。
图中的每一条边都是两种颜色的面的共同边界线,这样的边界线的种类数就是由四个元素中取出两个元素的组合数,即C边界=C =4!/[2!×(4-2)!]=24/4=6,即A—B、A—C、A—D、B—C、B—D、C—D六种。另外这个6(种边界线)还可以这样计算出来:每一种颜色的面既都可以与其他三种颜色的面构成一条边界线,而其他的三颜色的面也都可以与自已构成一条边界线,除去重复计算外,所以就有(4×3)/2=12/2=6(种)。
是不是六种边界线就得要用六种颜色呢,不是的。因为在3—正则的平面图中,由A色面和B色面所构成的边界线A—B,与由C色面和D色面所构成的边界线C—D,不但不可能是同一条边界线,而且也不可能相邻。象A—B和C—D这样的两条边界线就叫一对互斥的边界线。而互斥的边界线着同一颜色是可以的。
互斥的两条边界线的两侧的国家是完全不相同的,如中、蒙边界线和朝、俄边界线就是互斥的边界线,两条边界线也是不相邻的;而两条边界线的两侧的国家有一个是相同的国家时,这样的两条边界线则是相邻的边界线,如中、蒙边界线与中、俄边界线就是相邻的边界线,这两条边界线的确也是相邻的;还有另外一种边界线,两条边界线两侧的国家完全是相同的两个国家,这样的两条边界线虽不是同一条,但却是同样的两个国家在若干个不同地段处的边界线,如中、俄就在两个地段处有两条边界线,中、印在三个地段处有三条边界线。
象A—B和C—D这样的一对两条互斥的边界线,在由A、B、C、D四种颜色的面所构成的边界线中,应该还有A—C和B—D,A—D和B—C两对,每对都可用同一种颜色。在可4—面着色的3—正则的平面图中,每个“三界点”顶点都与三种颜色的面(A、B、C)相邻,该顶点所连的三条边界线分别是A—B,A—C和B—C;这三条边界线正好都是两两相邻的边界,所以它们可以共同相交于一个“三界点”顶点;这三条边界线中,正好没有各条边界线所对应的互斥边界线C—D、B—D和A—D,也进一步说明了互斥的边界线是互不相邻的;若把A—B,A—C和B—C三条边界线分别用1、2、3表示,则把其互斥的边界线C—D,B—D和A—D也可以分别用1,2,3表示。
由四种颜色的面所构成的六种边界线中,有三对是互斥的边界线,互斥的边界线可用同一种颜色。由于这个3—正则的平面图是可4—面着色的,各面的颜色已经确定,那么各“三界点”顶点所连的边界线的颜色,实际上也就已经确定了。全图只有三对互斥的边界线,每对用一种颜色,全图也实际上就只有三种颜色的边。3—正则的平面图每个顶点都只连有三条边,这三条边正好也就是不同的颜色。也由于每对互斥的边界线,是由两条在边界线两侧用了完全不同颜色着色的两个区域的边界线构成的,所以图中互斥的边界线的总对数是应该是C互斥对数=C边界/2=6/2=3,这也就是该图边着色时的色数,即C边=3。所以也就有可4—面着色的无割边的3—正则平面图一定是可3—边着色的结论。
现在用反证法证明可4—面着色的3—正则平面图一定是可3—边着色的:假如这个图不是可3—边着色的,那么图中至少要有一条边是第四种颜色。则这条边的两侧至少要有一个面不是用A、B、C、D四种颜色之一着色的面,但这是不可能的,因为该图是可4—面着色的,图中只用了四种颜色。假设与已知条件产生了矛盾,应否定假设。这就使可4—面着色的无割边的3—正则平面图一定是可3—边着色的结论得到了证明。
由于该图的面色数是4,现在又证明了其边色数是3,所以图中所用的颜色总数仍是C总=C面+C边=4+3=7,与上面1中的结论是相同的。
3、这就证明了泰特的猜想是正确的。但还要进一步证明每一个无割边的3—正则平面图都是可3—边着色的才能使四色猜测得到证明是正确的(见另文)。

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

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


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

本版积分规则

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

GMT+8, 2025-7-31 01:46 , Processed in 0.084281 second(s), 15 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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