数学中国

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

用颜色叠加法对地图着色时的一些技巧

[复制链接]
发表于 2017-4-7 13:10 | 显示全部楼层 |阅读模式

用颜色叠加法对地图着色时的一些技巧
雷  明
(二○一七年四月七日)
地图就是2—连通的3—正则平面图,在用颜色叠加法给其着色时,首先要对其进行3—边着色,要找边2—色圈。现根据自已的经验总结一些规律:
1、有些地图是4—色的,有些地图是3—色的,要使着色结果反映其色数的真值,颜色叠加时使用的两种边2—色回路必须都是非哈密顿的,以防把本来是3—色的地图着成4—色的。如底面是偶数条边的楞柱体,所有的面都是偶数条边的面,是3—色图,这些图一定是有两条以上的边2—色回路的。完全可以做到这一点。
2、除了所有面都是偶数的地图外,其他的地图一般都是4—色的,对这样的地图就可以大胆的去找其边2—色图了,这种地图,无论其是否是哈密顿的,都一定是4—色的。
3、一个地图,若其中有4—边形面(偶数条边界线),这本身就是一条边2—色圈,在其周围再做偶圈。最后一定有剩下的边,但也一定是偶数条。这些边能构成一个偶圈时,正好各偶圈都找到了;若不能构成圈时,就与最开始的那个4—边形面构成的偶圈共同合成一个偶圈即可。
4、平面图中的面可以是各面都是2—边形的(如一个海岛上只有两个国家的地图),3—边形的(如正四面体),4—边形的(如正六面体),以至5—边形的(如正十二面体),但一定不会有各面都是6—边形面的地图。这就是坎泊的地图的不可免集。这四种地图,我们已经知道其色数分别是:3(所有面都是2—边形的海岛和所有面都是4—边形的正四面体)和4(所有面都是3—边形的正四面体和所有面都是5—边形的正十二面体)。据此,我们可以推广到不含有寄数边面的地图一定是4—色的,而含有寄数边的面的地图则一定是4—色的。
5、如果一个地图中含有4—边形面,就可按以上3中所说的方法找边2—色圈。如果地图中有寄数边面,那么,两个寄数边面就是一个偶数边有边2—色圈。如果两个寄数边面不相邻时,那么两个寄数边面还是可以通过寄数个偶数边面,的传替,共同构成一个偶圈的。
6、非哈密顿的地图一定是4色的,而可哈密顿的地图,有些是4色的,有些是3色的,为了保证叠加后都能真实的反映其色数值,必须都用两种边2—色回路都是非哈密顿的相叠加,才能得到理想的叠加结果。所以,在作边2—色圈时,尽量不要作可哈密顿时的圈。也可以防止把3色图叠加成着成4色的。

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

注:此文已于二○一七年四月七日在《中国博士网》上发表过,网址是:
您需要登录后才可以回帖 登录 | 注册

本版积分规则

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

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

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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