【一】
相信很多人都听过四色猜想,一个听起来干脆简单的命题:
“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色”。
四色猜想最先是由一位叫古德里(FrancisGuthrie)的英国大学生提出来的。他跟弟弟一起研究,弟弟又向自己的老师请教,老师又写信咨询自己的朋友
之后的时间里,四色猜想在数学界传来传去,但众人都未能找到合适证法。
1878~1880年两年间,著名的律师兼数学家肯普(AlfredKempe)和泰勒(PeterGuthrieTait)两人分别提交了证明四色猜想的论文,宣布证明了四色难题。这是四色猜想证明史上的一个小插曲。
11年后,在牛津大学就读的年仅29岁的赫伍德以自己的精确计算指出了肯普在证明上的漏洞。他指出肯普说没有极小五色地图能有一国具有五个邻国的理由有破绽。
1913年,美国著名数学家、哈佛大学的伯克霍夫利用肯普的想法,结合自己新的设想;证明了某些大的构形可约。后来美国数学家富兰克林于1939年证明了22国以下的地图都可以用四色着色。1950年,温恩从22国推进到35国。1960年,有人又证明了39国以下的地图可以只用四种颜色着色;随后又推进到了50国。这种推进不仅十分缓慢,而且是没有尽头的。
那么,“四色猜想”是什么时候变成“四色定理”的呢?
电子计算机问世以后,由于演算速度迅速提高,大大加快了对四色猜想证明的进程。1976年6月,在美国伊利诺斯大学的两台不同的电子计算机上,用了1200个小时,作了100亿个判断,结果没有一张地图是需要五色的,最终证明了四色猜想。
“四色定理”得名。
但是计算机证法是人类无法验证的,所以直至现在仍有数学家称“采用计算机是作弊”,也有数学家认为四色猜想仍然是个猜想,计算机证法是不应被接受的。
【二】
四色猜想最大的特点是:门槛低。
上至专业图论数学家,下至小学生,甚至是文盲,大家都能看得懂四色定理的内容。于是,我们从来不缺四色定理的“证明”。
但四色定理的证明过程是“螺旋深入”的
四色定理的证明过程具有很强的层次性,层层深入,并且不断地推动数学理论的建设。例如,四色定理在一定程度上推动了拓扑学的发展。
拓扑学
既然如此,那么我们先避其锋芒,讨论一个四色定理的必要条件,四色定理的次级命题。也就是说:若证伪这个命题,则四色定理不成立;但若证明这个命题,却不能说明四色定理成立。
这个命题是:“平面内不存在五个区域两两相邻”。
也即:“平面内,最多有4个区域两两相邻(有公共线)”。
证明开始:
【1】
观察上述图形:
我们可以轻易看出,所谓“相邻”,就是指“存在公共边界”。
既然有公共边界,则在这两个区域内任取两点(不含边界),则两点间一定存在一条线段(不管直线还是曲线)只经过这两个区域。(线段全程在两个区域内)。
视野再放宽到A,B,C,D四区域,在它们内部分别任意取点a,b,c,d,既然存在ab只经过A和B,cd只经过C和D,则一定存在ab和cd的组合不相交。
继续推广:
若五个区域可以做到两两相邻,在五区域内任取五点,五点之间两两连线,一定存在一种连线模式,使得异源线段不相交。
【给异源线段定义:端点完全不同。如:有A,B,C,D四点,那么AB和CD互为异源的;AC和BD也是异源的,但是AB和AC不是异源的。】
而又因为:不管怎么取点,同源线段一定可以做到不相交,所以:
若五个区域可以做到两两相邻,在五区域内任取五点,五点之间两两连线,一定存在一种连线模式,使得任意线段间不相交。
利用逆否命题,所以:
证明:“不存在五个点两两相连,且连线不相交”就证明了原命题。
我们把“不存在五个点两两相连,且连线不相交”称为一级命题。
到这里,就是证明最核心且最巧妙的部分:将区域的关系简化为点线之间的关系,且完美等价。
【2】
那这个点线命题又该怎么证明呢?
如果我们多画几幅图就会发现,好像每次轮到第五个点连线时,前四个点中就必定有一个被“围住”。那么第五个点想要与之相连,连线就必定与之前的线段相交,从而满足命题。
首先我们明确,四点两两相连,且任意连线间不相交的连法是存在的。
那么我们可否大胆假设:
四点两两相连,且连线不相交时,必会出现一个点被其他点线“包围”的情况
若证明这个命题,也就证明了一级命题。
我们把“四点两两相连,且连线不相交时,必会出现一个点被其他点线“包围”的情况”称为二级命题。
【3】
我们思考如何用规范的数学语言描述“包围”。
引入几个概念:
(N点)区域:(由N个点,N条连线做边界的)封闭区域。
空区域:内部没有任何其他点线的区域
非空区域:内部还有结构的区域
空区域
当四点连线,两两不相交时:
三点之间的连线结构(三点三线图)是确定的,一定是个三点区域。
此时,若希望这个区域是非空区域,则另一个点必在区域内,也就是之前讲的“包围”。
于是命题再次等价转化:
四点两两相连,且连线不相交时,必会出现三点非空区域。
我们把“四点两两相连,且连线不相交时,必会出现三点非空区域。”称为三级命题
而在本命题中,最多可能形成四个“三点区域”
(排列组合:4C3=4:123,124,134,234)
若不希望出现非空区域,则这四个区域都必须是空区域。
那么先画出四个点,以及除34外的五条连线:
123与124已经成为了三点区域。令它们为三点空区域。
【这里还需证明:1423不是四点空区域。若1423为空区域,12连线必须经过“外侧”,则123和124不可能同时为空区域。读者可画图自行否定。又因五点及以上,两点及以下,也均不可能形成空区域(点数限制,线数限制),所以这里有且仅有两个空区域。】
给出一条定理:多连一条线,最多多形成一个空区域。
原因是,线段充当区域的界。所谓:“一刀两断”,不可能一刀三断,更不可能一刀四断。空区域可以理解为“区域的最小单位”,那么一条线段划下去,可能多出来一个空区域,也可能一个都不多,但不可能多出来两个。
注意!是空区域。多练一条线段可能会多出很多区域,但只有一个是空区域。
这里还有一条连线(34),所以最终可能形成三个三点空区域,或是两个。
必定有三点区域是非空的。
三级命题得证
二级命题得证
一级命题得证
原命题得证
嘿嘿
【三】
这个命题解决后,我们还可以向上向下分别推广至一维和三维空间。另外两个命题是:
“直线内,最多有2条线段两两相邻(有公共点)”
“空间内,最多有6个区域两两相邻(有公共面)”
再结合刚才这条:
“平面内,最多有4个区域两两相邻(有公共线)”
2,4,6,
我们是否可以猜测,在想象的“四维空间”中,最多有8个区域两两相邻呢?