数学中国

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

2—连通3—正则平面图的可3—边着色

[复制链接]
发表于 2017-4-4 10:00 | 显示全部楼层 |阅读模式
本帖最后由 雷明85639720 于 2017-4-8 08:26 编辑

2—连通3—正则平面图的可3—边着色
雷  明
(二○一七年四月三日)

    1、颜色叠加的原理:
证明2—连通3—正则平面图的可3—边着色,目的是为了证明泰特猜想是否正确。泰特猜想是:2—连通3—正则平面图的可3—边着色等价于其可4—面着色。要证明可3—边着色的2—连通3—正则平面图是可4—面着色的,必须要用到颜色叠加的原理。所以首先介绍颜色叠加的原理如下:


图1,a是一个由两个园部分相互重叠后所得的图,图2,a是由一个园和一个月牙形图相邻后所得的图,都把画图的面分成了若干部分。若把构成各图的两个图分开画,它们也把画图的面至少分成了两部分(如图1,b,图1,c,图2,b,图2,c),若给每一部分各染上一种颜色(如A,B,C,D四种),然后再把两个染了四种颜色的图重叠起来后,就可得到四种新的颜色,图中各面都有一种颜色(如图1,d和图2,d),但所占用颜色总数不超过新产生的四种颜色。
如果2—连通的3—正则平面图都可划分成若干个(包括一个)偶圈(或边2—色圈或回路),那么这些偶圈也就把画图的面至少分成了两部分。把同一个2—连通的3—正则平面图的两种边2—色圈(偶圈)的内、外相间的各染以不同的两种颜色,然后再把染了色的两种边2—色圈的色图重叠在一起,就产生了四种新的颜色。图也回到了原来的2—连通3—正则的平面图的原状,图中每个面均染了一种颜色,且两个相邻的面不会占用同一颜色。
这就是颜色叠加的原理。是由四种颜色叠加产生四种颜新的颜色的过程。
2、2—连通3—正则平面图可3—边着色的证明:
2、1  证明方法(一):
3—正则的平面图告诉我们,图中的每个顶点都连有3条边,那么该图的总边数就是e=3v/2=1.5v(e是边数,v是顶点数),即边数是顶点数的1.5倍。从这里可以看出,3—正则的平面图的顶点数必须是偶数,才能满满足图的边数是整数的要求。
又因为3—正则的平面图中有e=∑efi/2=(ef1+ef2+……+efn)/2的关系,从这里还可以看出,3—正则的平面图的面中,若有奇数边的面时,则奇数边面的总数必须是偶数,只有这样也才能满足图的边数是整数的要求。
颜色叠加的原理告诉我们,要进行颜色叠加至少把2—连通的3—正则平面图要划分成若干个(包括一个)偶圈。“3—正则平面图的顶点数都是偶数”和“3—正则平面图中奇数边面的总数是偶数”这两点,就保证了2—连通的3—正则平面图至少是可以划分为一个偶圈的;“2—连通”这一点也保证了从图的任一顶点出发,到达任一顶点后,再返回到原出发顶点时,不走重复路线。也就可以保证2—连通的3—正则平面图(地图)是一定可以划分成两条以上的若干偶圈的。
每个偶圈就是一条边2—色圈(回路),偶圈的边着色时,只用两种颜色就够了。图中所剩余的边的两端也都只与边2—色圈上的、已连接着着有两种颜色的边相邻,且这些边相互间均不相邻,所以全部着上第三种颜色是完全可以的。这就证明了2—连通的3—正则平面图一定是可以3—边着色的。
2、2  证明方法(二);
边着色就是对原图的线图的顶点着色。所谓线图就是把原图的边作为顶点,按原图中边与边的相邻关系作新的边,所得到的新图,就是原图的线图。
3—正则平面图中各顶点的度均是3,所以其线图中的最大团的顶点数最大也只能是3(即线图的密度是3),着色时至少也要3种颜色。
3—正则平面图中各面的边数都大于等于3的多边形的面,这些多边形面在其线图中都是以边数大于等于3的圈(面)出现的。圈着色时色数也一定是不大于3的,所以该线图的色数也一定不会大于3。
3—正则平面图中各边两端均共连有四条边,表现在其线图中就是各顶点的度均是4,该线图是一个4—正则图。线图的各顶点外围是四个边数大于等于3的面,所以图中不可能有大于等于5的奇轮,最多也只能有4—轮。4—轮的色数只能是3,没有5—轮以上的奇轮,所以该线图的色数也不可能大于3。
综合以上三点,就证明了3—正则平面图一定是可3—边着色的。当然2—连通的3—正则平面图也就一定是可3—边着色的。
    3、四色猜测的证明:
我们已经证明了泰特的猜想:“2—边通的3—正则平面图的可3—边着色等价于其可4—面着色”是正确的。现在又证明了每一个2—边通的3—正则平面图都是可3—边着色的。当然也就证明了任何2—边通的3—正则平面图(地图)都是可4—面着色的,即证明了地图四色猜测是正确的。地图四色猜测正确,则其对偶图——极大图平面图的顶点着色的色数也一定是小于等于4的,进而由极大图平面图经减边去点得到的任意平面图的色数也一定是不会大于4的,平面图的四色猜测也是正确的。

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

本帖子中包含更多资源

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

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

本版积分规则

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

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

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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