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

简单明了的“四色问题”证明

焦永溢 2009-6-27 18:29:08

    注:此为作者投稿。投稿时间:2009年6月27日 16:18

  关于地图“四色问题”,本人已写过三篇文章,其中于2007年5月21日发布在《少年百科》网站上的那篇《用减少法证明最大平面图“四色问题”》 已经用非常简便的方法能够完全证明最大平面地图(即球面平面地图)用四种颜色足够。对于这样简单的问题,文章下面的评论中,除了少数人表示看懂,多数人还是看不明白。在其它网站上登的不是没有图,就是没有看得懂的人。
  现在我再把原文章重新整理一下,增加了多幅说明的图,相信只要有初中(甚至小学)数学知识的人都能看懂。
  根据欧拉创立的“拓扑学”原理,平面地图上不管形状多么复杂、大小多么不等的每块区域都可看成一个点。而相互间有接壤的可用连线来表示(从图1到图6每幅图上方的区域图都可用下面的关系图来表示)。地图上着色时只要相互有接壤的区域用的颜色不同就能分清不同区域了,也就是关系图上每条线两端的点不重色就行了。
  从最大平面图上看,每一个区域(点)都是被其它若干个区域(点)所包围。下面我们就逐一就各种包围情况来分析需要几种颜色。
  一个区域完全包围另一个区域的情况:这种情况相信不用画图大家也能明了,比如梵蒂冈处在罗马的包围之中,地图上它只要用与罗马不同的任何颜色就能分别出来,而处在中间的梵蒂冈存在与否,根本不会影响罗马与周围区域的着色。

  二个区域包围一个区域的情况:如图1所示,中间的区域只要用不同于外面二区域的任何颜色就可以了,而它的存在与否,也根本不会影响外围二区域与其它区域的着色。就是说:在整个最大平面图中可把图1中左边的情况看成与右边的一样,下方的关系图就是去掉了中心O点,把二边形左右两条边AB合并为一条。
  三个区域包围一个区域的情况:如图2所示,中间的区域只要用不同于外面三区域的任何第四种颜色就可以了,而它的存在与否,也根本不会影响外围三区域与其它区域的着色。就是说:在整个最大平面图中可把图2中左边的情况看成与右边的一样,下方的关系图就是去掉中心O点,只剩下外面三边形ABC。
  四个区域包围一个区域的情况:如图3所示,由于上与下区域不接壤可用同一种颜色、左与右区域也不接壤也可用同一种颜色,所以中间区域只要用第三种颜色就行了。由于中间区域只与周围四个区域有接壤,不与外界其它区域有接壤,所以它的存在与否,只要外围四区域着色不变也不会影响其它区域的着色。就是说:在整个最大平面图中可把图3中左边的情况看成与右边的一样(图中是中间用了绿色使左右区域相连,也可以用红色使上下区域相连),下方的关系图就是去掉中心O点,把C点合并到B点,只剩下三个点二条线。
  五个区域包围一个区域的情况:如图4所示,周围五个区域中,A与C可用同一种颜色,B与E可用另一种颜色,D就必须用第三种颜色,而中心的O就需要用第四种颜色。由于中间区域与以上几种情况一样只与包围它的五个区域有接壤,它的存在与否,只要外围五区域着色不变也不会影响其它区域的着色。就是说:在整个最大平面图中可把图4中左边的情况看成与右边一样,下方的关系图就是去掉中心O点,把E点合并到B点,只剩下四个点四条线。
  当外围的点增多时能否与上叙一样处理呢?回答是肯定的。我们先来看一条公路状的平面图的着色(如图5、6所示),公路起点用一整块红色,左右车道向下对称的分别用绿、红、绿、红……一块块涂色。当起点终点及左右两边总块数加起来是偶数2n时,终点也是一整块并且n是偶数也用红色,n是奇数用绿色(图5)。当起点终点及左右两边总块数加起来是奇数2n-1时,终点左右分两块,其中一块沿用上面车道着色方法用红或绿,另一块就要多用一种颜色蓝(图6)。中间用黄色把左右车道分隔开来,这样图5就需要三种颜色,图6就需要四种颜色。因为中间的黄色是被包围在公路当中不与外界接触,它的存在与否不会影响公路与外面地域的着色情况,所以可以把黄色部分去掉,去掉中间部分后左右车道就合二为一(如图中右边所示),图5和图6中右边与外界的着色关系同左边时仍旧一样。下方的关系图就是去掉中心点,通过合并,2n边形只剩下n+1个点n条线(图5),2n-1边形只剩下n+1个点n+1条线(图6)。带下划线的这两个规律其实也适合上面所述的二边形、三边形、四边形、五边形……。它们只是多边形的几个特例。

  在最大平面图上可以把任何一个点当作中间点来去掉,但可能在包围这个点的多边形的各个顶点当中有的点之间有连线(比如第1个点与第3、5、7等点有连线,相当于在串联电路中把一些电阻短路),这些点就不能使用同一种颜色。图7中A与C的连线就把B点短路了,但一旦有短路现象就一定会产生比原来多边形边数少的多边形,如图7中就产生三边形AOC包围B点的情况,这样可以先去掉B点,原来的多边形也就少了一个B点。因为边数最少的多边形顶点间不可能再有短路,所以只要先找到整个最大平面图中顶点最少的多边形进行去掉中心点(也就是连接线最少的点),再把外围的点按图1到图6的规律进行合并。把减少合并后的线和点,在最大平面中代替原来多点包围一点的多边形(就象初等代数中解多元一次方程的代入消元法一样,用图1到图6的右面取代左面),再在新形成的整个平面图上找出顶点最少的多边形,再用以上同样的方法把连接线最少的中间点去掉,把外围的多边形合并成几条线和几个点。这样一步步的减去、合并、代替下去,任何复杂的最大平面图到最后只剩下一个三边形。
  在去掉中间点的过程中,很容易出现连成一串的四边形(如图8中的B和C都是四边形的中心点),可先去掉B点把C与A合并,也可先去掉C点把D与B合并。从A点到D点实际上是两个多边形的公共边,在去掉这些四边形中心点的过程中,因为有着依次去掉一个合并一个的规律,可一次性把这些点去掉,A到D的总点数是单数,合并后只剩下A点;A到D的总点数是双数,合并后只剩下A和D两点。
  实际的地图中往往有没有中心点的多边形存在,也可用以上方法看成有中心点去掉后再把周围合并。在以上减去、合并、代入等操作过程中一直不会使用超过四种颜色。这就完全能够证明任何复杂的最大平面图“四色足够”。

[jyy630907@163.com]

用减少法证明最大平面图“四色问题” [焦永溢 2007-5-21]

彻底解决“四色问题” [焦永溢 2005-10-22]

关于“四色问题”的证明 [焦永溢 2005-1-4]