四色问题公式(四色问题解法)

导语：数学的理解 一般性原理 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，得：

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

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

本文内容由小馨整理编辑！