当前位置:首页 -少年百科 - 数学 - 正文*

地图“四色问题”中的特例——三色足够

浙江奉化 焦永溢 2016-8-27 19:02:25
浙江奉化  焦永溢  2016.5.6    关于地图四色问题,本人已写过多篇文章,于2007年5月21日发布在《少年百科》网站上的那篇《用减少法证明最大平面图“四色问题”》已经用非常简便的方法能够完全证明最大平面地图(即球面平面地图)用四种颜色足够。后来于2009年6月27日在《少年百科》网站上重新发了一篇《简单明了的“四色问题”证明》,就是把前一篇文章加以整理,并增加了若干的插图,目的是为了使大家能够更加看得清楚明了。这些图中,图5展示了中心一个点、被周围共偶数个点包围的情况下,怎样去掉中心点,合并外围的点,然后用右边合并后的图在整个图中代替左边的图;而图6展示了中心一个点、被周围共奇数个点包围的情况下,怎样去掉中心点,合并外围的点,然后用右边合并后的图在整个图中代替左边的图。现在我再把这两个图拿来分析一下合并前后各个点度数(就是与该点相连的线条数)的变化。这里的图1和图2,分别用的是原来图5和图6下面的示意图,为了分析方便,把各个点作了编号。下面就去掉偶度数中心点和奇度数中心点这两种情况作如下分析;     一、去掉偶度数的中心点(见图1)    合并前,中心点是偶度数的,周围各点若不计对外相连的线数,图中从1-12各点都是三度(与左、右、中心各有一条连线)。合并后,中心点去掉了,外围的12并给了2,11并给了3,10并给了4,9并给了5,8并给了6。1和7点从合并前的三度(不计向外的连线,下同)减少到一度;而其它点都是两个合并后只剩二度。可见没与其它点合并的1和7点,在这合并处理后分别减少了二度;其它的二个点合并后的度数由原来的三度加三度减少到二度,减少了四度。    二、去掉奇度数的中心点(见图2)
    合并前,中心点是奇度数的,周围各点若不计对外相连的线数,图中从1-11各点都是三度。合并后,中心点去掉了,外围的11并给了2,10并给了3,9并给了4,8并给了5,6和7相邻不能合并。与前一种情况相似,1点从合并前的三度减少到一度,其它两个点合并后只剩下二度,而合并后的5和8点却剩下三度,6和7点分别还剩下二度。可见1点在合并处理后减少了二度;5与8点合并后的度数由原来的三加三减少到三度,减少了三度;6和7点分别只减少了一度。
    大家知道,在整个最大平面图中,只要有三度及三度以上的奇度数点存在,就一定需要四种颜色(因为外围一圈就需要三种颜色了)。而偶度数的点,由于外围一圈只要二种颜色,包括中心点只要用三种颜色就够了;所以,只要保证图上所有的点在上述合并过程中一直都是偶度数的,不会有奇度数的点出现,就能保证三种颜色就够了。    为了使全图上所有点一直都是偶度数的,首先合并前就一定都要是偶度数;那么在合并的过程中这些点能不能一直保证都是偶度数呢?上面第一种情况的分析中,1和7点都是减少了二度,所以减少后的度数(包括与外连线的度数)还是偶数(偶数减二当然还是偶数);其它两个点合并后的度数,是两个点原来总度数(包括对外连线的度数)之和减少了四度,所以合并减少后的度数还是偶数(偶数加偶数减四当然还是偶数)。    综上所述,我们在拿到任何复杂的地图时,只要看一下图中有否三度及三度以上的奇度数点存在,有就可断定这图可用四色着色;若全是偶度数点,没有奇度数点,就可断定这图用三色足够了。这一判断的方法,就如欧拉在“七桥问题”上得出的“看图上奇度数点的个数就能断定能否一笔画出”的结论一样的简单。 注:此为作者投稿,本站未作审验。作者自2005年起就向本站投了关于四色问题的稿件,编辑对作者这十多年的执着研究致以敬意。作者相关文章:简单明了的“四色问题”证明 [焦永溢 2009-6-27]用减少法证明最大平面图“四色问题” [焦永溢 2007-5-21]彻底解决“四色问题” [焦永溢 2005-10-22]关于“四色问题”的证明 [焦永溢 2005-1-4]