数学中国

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

无割边的3—正则平面连通图的可否哈密顿与其可4—面着色的关系

[复制链接]
发表于 2017-3-24 09:58 | 显示全部楼层 |阅读模式

无割边的3—正则平面连通图的可否哈密顿与其可4—面着色的关系
雷 明
(二○一七年三月二十三日)

无割边的3—正则平面图就是地图的原型,其每个顶点的度都是3,就是所谓的“三界点”,人称“三不管地区”。 3—正则平面图都有偶数个顶点,边数都是顶点数的1.5倍,都是可3—边着色的(可见《中国博士网》上发表的博文《直接用地图来证明四色猜》一文,网址是:(发不出);也可到“雷明的博客”中去看,“雷明的博客”的网址是:(也发不出))并且三种颜色所用的频率(使用次数)是相同的;无割边的3—正则平面连通图不但可3—边着色,并且可4—面着色(同样也可见上文)。
在地图中有“国中之国”,即该国只有一条边界线,且边界线上没有“三界点”,只是一个园环,其外围也只有一个国家,这个“国中之国”只要着上与其外围国不同的颜色就可以了,其至少有三种着色方式。所以在研究四色问题中就有所谓的“正规地图”的出现,即去掉了“国中之国”的地图。
1、任何无割边的3—正则平面连通图都有一条以上的边2—色圈
1、1  无割边的3—正则平面连通图有两种类型,一是可哈密顿的,另一是不可哈密顿的。任何无割边的3—正则平面连通图因其顶点数是偶数,而都可以把所有顶点划分成一个或若干个顶点数大于等于4的集团,这些集团都是一条边2—色圈。
1、2  可哈密顿的无割边的3—正则平面连通图的肯定可以只是一个边2—色偶圈的,如正十二面体就只有一条哈密顿圈边2—色圈(如图1,a);但也有一些同样是可哈密顿的无割边3—正则平面连通图,却可以是有两条以上的边2—色圈的,如正—6面体就有多条边2—色圈(如图1,b和图1,c)。

1、3  然而不可哈密顿的无割边的3—正则平面连通图肯定不可能是一条边2—色圈的,但却一定是有两条以上边2—色圈的,如最小非哈密顿平面三次图(如图2)就有3条边2—色圈。

    1、4  以上所述说明了:① 不可哈密顿的无割边的3—正则平面连通图一定是有多条边2—色圈的,② 而可哈密顿的无割边的3—正则平面连通图有些是只有一条哈密顿的边2—色圈,③ 而有些则是有多条边2—色圈的。
2、可哈密顿的无割边的3—正则平面连通图的两种可4—面着色的面色数
2、1  可哈密顿的边2—色圈在用颜色叠加法对无割边的3—正则平面连通图进行面着色时,不能反映所着色的图的面色数的真值。如正—6面体的面色数是3,但若用了可哈密顿的边2—色圈时,就得到一个4—面着色的非正常着色图,如图3;但若不用可哈密顿的边2—色圈时,就可得到正—6面体的一个3—面着色的正常着色图,如图4。这一现象说明了一个问题:有两条以上边2—色圈的可哈密顿的无割边的3—正则平面连通图(地图)一定是一个可3—面着色的图,其面色数一定是3。

从图3和图4中,我们还发现,同样是一个无割边的3—正则的平面连通图,在图3的非正常着色中,三种边2—色圈,有两条都是哈密顿的,只有一条是非哈密顿的;而在图4的正常着色中,三种边2—色圈,三条都是非哈密顿的。同时也发现,可哈密顿的边2—色圈在图中只可能有一条,只能把画图的面分隔成两部分;而非哈密顿的边2—色圈至少是有两条的,能把画图的平面分隔成三个以上的部分。这就是我们以后在使用颜色叠加法对无割边的3—正则的平面连通图(地图)着色中应该注意的问题:如何才能作到正常着色。


2、2  但本来就应是4—面着色的图,在不用可哈密顿的边2—色圈时,得到的图仍是4—面着色的,如图5和图6的5个国家包围一个国家的地图或5—楞柱两图的4—面着色。图5,a的1—2—1边2—色回路是哈密顿圈,颜色叠加的着色结果得到的是一个4—面着色的图,如图5,c;图6,a的1—2—1边2—色回路尽管不是哈密顿圈,但因其3—边着色中仍有1—3—1边2—色回路是哈密顿的(如图6,b),所以颜色叠加的着色结果仍是一个4—面着色的图,如图6c。这一现象也说明了一个问题:只有一条哈密顿圈的可哈密顿的无割边的3—正则平面连通图(地图)一定是一个4—面着色的图,其面色数一定是4。

3、不可哈密顿的无割边的3—正则平面连通图一定是4—面着色的图,其色数也一定是4
不可不可哈密顿的无割边的3—正则平面连通图一定有多条边2—色圈,所以其可4—面着色的色数一定是4。如图7的最小非哈密顿三次平面图的4—着色。图7,a是1—2—1边2—色圈的内、外相间二着色,图7,b是1—3—1边2—色圈的内、外相间二着色,图7,c是最后的4—着色。可以看出,图中的边2—色圈是把画图的面分隔成了四部分的。



    4、总结
4、1  非哈密顿的无割边的3—正则平面图一定有多个边2—色圈,也一定是4—面着色的;
4、2  若可哈密顿的无割边的3—正则平面图只有一条哈密顿边2—色圈,也是4—面着色的;
4、3  若可哈密顿的无割边的3—正则平面图有多条边2—色圈,一定是3—面着色的。
4、4  为了使在使用颜色叠加法对无割边的3—正则平面图(地图)的面着色时,能得到正常着色的结果,所以在对其进行3—边着色时,要尽可能的保证三种边2—色圈都不是哈密顿的。若实在不能保证,则说明该图就是只有一条哈密顿时圈的图,唯利是图放弃找非哈密顿圈。只有这样,才能保证颜色叠加的着色结果是正常着色。

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

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

本帖子中包含更多资源

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

x
 楼主| 发表于 2017-3-27 07:25 | 显示全部楼层
说得不明不白的,什么意思呢。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

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

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

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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