组合数学四色证明.doc

《组合数学四色证明.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、四色问题的证明如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻的国家的颜色不同。这样的着色效果能使每一个国家都能清楚地显示出来。但要证明这个结论确是一个著名的世界难题，最终借助计算机才得以解决，最近人们才发现了一个更简单的证明。根据欧拉创立的“拓扑学”原理，平面地图上不管形状多么复杂、大小多么不等的每块区域都可看成一个点。而相互间有接壤的可用连线来表示<从图1到图6每幅图上方的区域图都可用下面的关系图来表示）。地图上着色时只要相互有接壤的区域用的颜色不同就能分清不同区域了，也就是关系图上每条线两端的点不同色就行了。下面的是湖南地

2、图！可以用四种颜色！！6/6四色问题的证明如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻的国家的颜色不同。这样的着色效果能使每一个国家都能清楚地显示出来。但要证明这个结论确是一个著名的世界难题，最终借助计算机才得以解决，最近人们才发现了一个更简单的证明。根据欧拉创立的“拓扑学”原理，平面地图上不管形状多么复杂、大小多么不等的每块区域都可看成一个点。而相互间有接壤的可用连线来表示<从图1到图6每幅图上方的区域图都可用下面的关系图来表示）。地图上着色时只要相互有接壤的区域用的颜色不同就能分清不同区域了，也就是关系图上每条线两端的点

3、不同色就行了。下面的是湖南地图！可以用四种颜色！！6/6　　从最大平面图上看，每一个区域<点）都是被其它若干个区域<点）所包围。下面我们就逐一就各种包围情况来分析需要几种颜色。1。一个区域完全包围另一个区域的情况：这种情况相信不用画图大家也能明了，比如梵蒂冈处在罗马的包围之中，地图上它只要用与罗马不同的任何颜色就能分别出来，而处在中间的梵蒂冈存在与否，根本不会影响罗马与周围区域的着色。6/62..二个区域包围一个区域的情况：如图1所示，中间的区域只要用不同于外面二区域的任何颜色就可以了，而它的存在与否，也根本不会影响外围二区域与其它区域的着色。就是说：在整个最大平面图中可把图1中左

4、边的情况看成与右边的一样，下方的关系图就是去掉了中心O点，把二边形左右两条边AB合并为一条。3..三个区域包围一个区域的情况：如图2所示，中间的区域只要用不同于外面三区域的任何第四种颜色就可以了，而它的存在与否，也根本不会影响外围三区域与其它区域的着色。就是说：在整个最大平面图中可把图2中左边的情况看成与右边的一样，下方的关系图就是去掉中心O点，只剩下外面三边形ABC。4.四个区域包围一个区域的情况：如图3所示，由于上与下区域不接壤可用同一种颜色、左与右区域也不接壤也可用同一种颜色，所以中间区域只要用第三种颜色就行了。由于中间区域只与周围四个区域有接壤，不与外界其它区域有接壤，所以

5、它的存在与否，只要外围四区域着色不变也不会影响其它区域的着色。就是说：在整个最大平面图中可把图3中左边的情况看成与右边的一样<图中是中间用了绿色使左右区域相连，也可以用红色使上下区域相连），下方的关系图就是去掉中心O点，把C点合并到B点，只剩下三个点二条线。5.五个区域包围一个区域的情况：如图4所示，周围五个区域中，A与C可用同一种颜色，B与E可用另一种颜色，D就必须用第三种颜色，而中心的O就需要用第四种颜色。由于中间区域与以上几种情况一样只与包围它的五个区域有接壤，它的存在与否，只要外围五区域着色不变也不会影响其它区域的着色。就是说：在整个最大平面图中可把图4中左边的情况看成与右

6、边一样，下方的关系图就是去掉中心O点，把E点合并到B点，只剩下四个点四条线。6/66/6当外围的点增多时能否与上叙一样处理呢？回答是肯定的。我们先来看一条公路状的平面图的着色<如图5、6所示），公路起点用一整块红色，左右车道向下对称的分别用绿、红、绿、红……一块块涂色。当起点终点及左右两边总块数加起来是偶数2n时，终点也是一整块并且n是偶数也用红色，n是奇数用绿色<图5）。当起点终点及左右两边总块数加起来是奇数2n-1时，终点左右分两块，其中一块沿用上面车道着色方法用红或绿，另一块就要多用一种颜色蓝<图6）。中间用黄色把左右车道分隔开来，这样图5就需要三种颜色，图6就需要四种颜色。

7、因为中间的黄色是被包围在公路当中不与外界接触，它的存在与否不会影响公路与外面地域的着色情况，所以可以把黄色部分去掉，去掉中间部分后左右车道就合二为一<如图中右边所示），图5和图6中右边与外界的着色关系同左边时仍旧一样。下方的关系图就是去掉中心点，通过合并，2n边形只剩下n+1个点n条线<图5），2n-1边形只剩下n+1个点n+1条线<图6）。带下划线的这两个规律其实也适合上面所述的二边形、三边形、四边形、五边形……。它们只是多边形的几个特例。在最大平面图上可以把任何一