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

jyy630907

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

                  焦永溢 2009-6-27

　　关于地图“四色问题”，本人已写过三篇文章，其中于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

这里图片很难上传

jyy630907

谁能找出这文章中错误的地方，本人承诺奖励人民币一万元。

雷明85639720

焦永溢,你让中科院数学所的专家们去认真阅读你的着色方法吧！

jyy630907

这个世界奇怪了，这么简单绝妙的证明，是个数学过得去的初中生就能懂，可是竟然没有一个识货的？

jyy630907

本人的这篇文章中有一句“但一旦有短路现象就一定会产生比原来多边形边数少的多边形”，严格来讲不一定。图7中B点比O点确实度数(外围的点数小)，但还有可能三边形AOC中不止B一个而是有许多点，并且每点度数都大于等于四或五的情况。这时O点如果是四度或五度以下的话，就仍旧是全图度数最小的点，这个度数最小的O点还能当中心点去掉吗？
一边形、二边形、三边形因为操作时只要去中心点，外围点用不及合并，外边短不短路不影响着色。
如图3所示的四边形BC若有短路不能合并，但上帝关了一扇门，却开了另一扇窗，AD之间就决不可能再有连线，就可以着同色合并。
如图4所示的五边形若BE有连线不能合并，但可把顶点A换成别点。若AC有短路，C与A就不能同色，但D却可以与A同色。若AC和AD都有短路，C和D都不能与A同色了，但可把顶点A换成C合并BD，或把顶点A换成D合并CE。
因为已有定理：最大平面(球面)地图上度数最小的点，一定不大于五度。从以上的分析中得出结论：一到五度的点，都是肯定能够进行“去掉中心点，合并外围点的化简操作。

jyy630907

“但一旦有短路现象就一定会产生比原来多边形边数少的多边形”这句不完全正确的话，还是由我自己发现，并且找到方法，仍旧能使“去掉度数最小的中心点，合并外围点”这个绝妙方法可以一直正确可行，这一万元奖金还是自己来拿。

雷明85639720

jyy630907：
1、你把极大图（即你所说的最大图）与地图间的关系弄混了。
2、平面上或球面上的地图不是极大图，而是3—正则的平面图，其每个顶点的度都是3，即“三界点”，就是平时大伙所说的“三不管地区”或“山高皇帝远”的地方。地图中的面都是多边形，包括二边形面在内，如蒙古国就是一个二边形面。
3、极大图则是所有面都是三边形面的平面图，其顶点度都是大于等于2的。
4、地图（3—正则的平面图）的对偶图就是极大平面图。地图的对偶图中，代表蒙古图的那个顶点的度就是2度的。
5、地图与极大图平面图是一对相互对偶的平面图。地图的对偶图是极大图，极大图的对偶图则是3—正则的平面图，即地图。
6、你这个“最大平面(球面)地图”，“最大平面(球面)地图上度数最小的点，一定不大于五度。”的说法是错误的。“地图”只能说是“平面地图”或“球面地图”，没有说成是“最大平面(球面)地图”的；地图中各顶点的度都是3，没有最小与不最小之分，更不能说一定不大于5；只能说“任何平面图中一定含有至少一个顶点的度小于等于5 的”，这才是图论中已经证明过的定理。所以你所说的所谓的定理“最大平面(球面)地图上度数最小的点，一定不大于五度。”也是错误的。
7、因为我对你的方法还看不明白，所以请你用你的理论把二十面体（极大图）或十二面体（地图）用你的方法合并到最后只剩一个三角形。十二面体（地图）与二十面体（极大图）是一对互相对偶的平面图。十二面体（地图）中各顶点的“度”全是3，各面全是5边形的面；而二十面体（极大图）中各个面的“边数”也全是3，各顶点的度则全是5。作业要求：要画出图，并作文字说明，写出操作步骤。

jyy630907

有的人又要来胡说了

雷明85639720

说说，那里说错了？