搜索
写经验 领红包
 > 职场

四色问题的证明思路(如何证明四色问题)

导语:数学的理解 一般性原理 26 四色问题的证明:对偶原理

数学的理解 一般性原理 26四色问题的证明:对偶原理

从一个趣闻轶事说起。

德国天才数学家闵可夫斯基,曾是爱因斯坦的老师。他把相对论中的时间和空间统一成“四维时空”。这是近代物理发展史上的关键一步。

一天闵可夫斯基走进教室,一名学生递给他一张纸条:“如果把地图上有共同边界的国家涂成不同颜色,那么只需要四种颜色就足够了。您能解释其中的道理吗?”

闵可夫斯基微微一笑,说到“这个问题叫四色问题,是一个著名的数学难题。其实它之所以一直没有得到解决,仅仅是由于没有第一流的数学家来解决它。” 为证明只是一道小菜,闵可夫斯基当堂掌勺,打算把问题“炒成”定理……

下课铃响了,可“菜”还是生的。一连好几天他都挂了黑板。后来有一天闵可夫斯基走进教室时,忽然雷声大作。他借此自嘲道“哎!上帝在责备我狂妄自大呢!我解决不了这个问题。”

我们就来聊一聊四色问题。不考虑有“飞地”的情况。

给地图着色时,要求邻国(有共同边界)为不同颜色,以便区分。这和国家的大小形状以及边境线的曲直长短无关。这类问题是拓扑研究的对象。

为了略去繁琐且没意思的文字,把下面的内容设为“公理”。参考下面的图。

【公理1】国家和首都是 一对一 对应的。如图1。

【公理2】两个邻国至少有一段共同边界。不存在三个或以上的国家共有的边界。只有孤立点接触的两国不属邻国。

邻国的首都间以穿越某段共同边界的一条铁路线连接。这样,任何国与国的共同边界至多被一条铁路线穿越。参考图2,不难理解:

【公理3】“铁路网线”仅在首都交汇。首都也称为节点。

擦除图2中所有的边境线,得到图3。图1和图2互为对偶图。两个首都节点间若有铁路线连接,为互邻节点。

这样,根据对偶原理,给图1的地图着色问题,就转换为给图3的互邻节点染不同颜色的问题。

那么,一个节点最多会有多少互邻节点呢?

考虑三个互邻节点,记为A,B,C。互连这三个节点的铁路线或曲直长短,但仍称△ABC。参见图4。

引理1. 三角形任一内点和任一外点不相邻。

因为连接三角形外点和内点的连线必与三角形某边相交,故不为邻。

引理2. 三角形内至多有一个节点与三角形的三个顶点互邻。

参见图5。任取△ABC内一点D,并与△ABC三个顶点相连。显然,A、B、C、D为互临节点。△ABC被分为三个小三角形。

参见图6。再在△ABC内任取一点E,则E必在某个小三角形内,不妨设是△ABD内点。则C为△ABD外点。由引理1,E与C不相邻。

引理3. 三角形外至多有一个节点与三角形的三个顶点互邻。

参见图7。任取△ABC外一点F(不妨如图),分别连接F和△ABC三个顶点。得△FBC(FC边如虚线所示)。再任取节点G。

G或在△FBC内,由引理2,G不能与ABCF四点互邻;或在△FBC外(另记为G’),由引理1,G’不能与A相邻。引理得证。

综合引理1~3,得:

定理:平面上至多有四个节点互邻。区分互临节点顶多需要四种颜色。

推论:由对偶原理,区分地图上不同的国家,至多只需四种颜色。

本文内容由小玥整理编辑!