新浪博客

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

2017-03-24 09:59阅读：

http://blog.sina.cn/dpool/blog/u/1638843823


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

无割边的3—正则平面图就是地图的原型，其每个顶点的度都是3，就是所谓的“三界点”，人称“三不管地区”。 3—正则平面图都有偶数个顶点，边数都是顶点数的1.5倍，都是可3—边着色的（可见《中国博士网》上发表的博文《直接用地图来证明四色猜》一文，网址是：http://www.chinaphd.com/cgi-bin/topic.cgi?forum=5&topic=3273&show=0；也可到“雷明的博客”中去看，“雷明的博客”的网址是：http://blog.sina.com.cn/leiming1946）并且三种颜色所用的频率（使用次数）是相同的；无割边的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）。
无割边的3—正则平面连通图的可否哈密顿与其可４—面着色的关系

1、3 然而不可哈密顿的无割边的3—正则平面连通图肯定不可能是一条边2—色圈的，但却一定是有两条以上边2—色圈的，如最小非哈密顿平面三次图（如图2）就有3条边2—色圈。
无割边的3—正则平面连通图的可否哈密顿与其可４—面着色的关系

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—正则平面连通图的可否哈密顿与其可４—面着色的关系

从图3和图4中，我们还发现，同样是一个无割边的3—正则的平面连通图，在图3的非正常着色中，三种边2—色圈，有两条都是哈密顿的，只有一条是非哈密顿的；而在图4的正常着色中，三种边2—色圈，三条都是非哈密顿的。同时也发现，可哈密顿的边2—色圈在图中只可能有一条，只能把画图的面分隔成两部分；而非哈密顿的边2—色圈至少是有两条的，能把画图的平面分隔成三个以上的部分。这就是我们以后在使用颜色叠加法对无割边的3—正则的平面连通图（地图）着色中应该注意的问题：如何才能作到正常着色。
无割边的3—正则平面连通图的可否哈密顿与其可４—面着色的关系
无割边的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—１边2—色回路是哈密顿的（如图6，b），所以颜色叠加的着色结果仍是一个4—面着色的图，如图6c。这一现象也说明了一个问题：只有一条哈密顿圈的可哈密顿的无割边的3—正则平面连通图（地图）一定是一个4—面着色的图，其面色数一定是4。
无割边的3—正则平面连通图的可否哈密顿与其可４—面着色的关系

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—色圈是把画图的面分隔成了四部分的。
无割边的3—正则平面连通图的可否哈密顿与其可４—面着色的关系
无割边的3—正则平面连通图的可否哈密顿与其可４—面着色的关系
无割边的3—正则平面连通图的可否哈密顿与其可４—面着色的关系



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

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

注：此文已于二○一七年三月二十四日在《中国博士网》上发表过，网址是：
http://www.chinaphd.com/cgi-bin/topic.cgi?forum=5&topic=3281&start=0#1

我的更多文章

下载客户端阅读体验更佳

APP专享