规则图形下四色定理的证明

雨天饼干

摘要：四色定理自提出以来，经历了很多代证明。但是人们并没有找到成熟的纯数学证明方法。同样本文也对该定理进行了探索。首先，本文将四色定理拆分成两个小定理，先证明，在不考虑空间是否可以实现的情况下，不管有多少国家，在这些国家中最多有k个国家两两相邻时，则用k种不同颜色刚好可以将所有国家区分开；之后，用等价代换的方法简化国家间的相邻关系，证明最多有4个国家两两相邻；最终得以证明四色定理。这也是数学问题的常见证明思路。为了方便说明，本文将以地图添色为代表展开讨论。规则图形，即是不考虑“飞地”的情况[详细见注释3]。
关键词：四色定理、等价转换、图论、平面图

名词解释
[1]平面图：若一个图G能画与平面上，而边无任何交叉，则称图G为平面图，否则称图G为非平面图。
[2]图：简单的说，图是指某些事物以及这些事物之间的联系，一般我们将这种事物表示成点，而直接的联系用连线来表示，形如图1中的关系图。完全图：就是图中所有结点两两相连
[3]图的同构：
设G和G'是两个分别具有节点集V和V'的图，若存在一个双射h：V->V'，使得当且仅当{Vi，Vj}是G中的边时，{h(Vi),h(Vj)}是G'中的边，则称G同构与G'。两个图同构，即表明一个图可以在不删减、增添新节点或者边的情况下，变换成另一个图。
在研究的N个点两两相邻的图时，各点的关系都是对称的，所以当点数N一定时，所有图都是同构的。


四色定理又称四色猜想、四色问题，是世界三大数学猜想之一。四色定理是一个著名的数学定理，通俗的说法是：每个平面地图都可以只用四种颜色来染色，而且没有两个邻接的区域颜色相同。这个定理最早在19世纪由一位英国地图地图工作中提出，摩尔根、哈密顿等数学家均尝试对该问题进行数学证明，但是都没有得到满意的结果。后来郝伍德等人证明了五色定理，自此对四色定理的数学证明再无实质性进展。人们仅使用计算机证明出了该定理。
对于该定理的证明，本文大致分为两部：1证明：不管有多少国家，在这些国家中最多有k个国家两两相邻时，则用k种不同颜色刚好可以将所有国家区分开。2证明：最多有4个国家两两相邻。以下是详细证明。
1将问题化简（降低难度）
在不考虑空间上是否可以实现的情况下，先研究国家的异色区分问题。规则很简单相邻国家间颜色不相同。由于不考虑空间中是否可以实现，所以只需要明白文字上的关系即可，有些图形是画不出来的。
先讨论所有国家两两相邻的情况。当只有两个国家（甲乙）时，显然需要用两种颜色；以此为基础，加入第三国（丙），所有国家两两相邻时，即丙国与甲乙都相邻，所以丙国只能使用第三种颜色；那么我们讨论加入第四国（丁）的情况，因为丁国与甲乙丙都相邻，所以丁国只能使用第四种颜色；以此类推，五个国家时，就是五种颜色了.......这里我们可知，N个国家两两相邻时，需要N种颜色。
那么当N个国家随机相邻时，设此时在这N个国家中最多能找到k个国家两两相邻。那么首先需要k种颜色，来辨别两两相邻的这k个国家，为便于描述，这里将这些国家和颜色编为同样的号（即i国为i色）。下面考虑第k+1个国：由于，假设条件是最多能找到k个国家两两相邻，所以第k+1国（最多）只能与前面k国中的k-1个国家相邻（为了便与描述就假设刚好是前k-1个国家），这时，k+1国只要涂上k国的颜色就不会发生颜色上的冲突。（因为第k+1个国家和第k个国家不相邻，只和前k-1个国家相邻，所以可以同色）依此类推，可以容易的证得，这种情况下我们只需要k种颜色即可用异色区分所有国家。而少于这些颜色就无法区分所有国家，多余k种颜色可以区分但是会造成浪费，既是说k是一个临界值。
总结一下以上证明可以得出如下结论：不管有多少国家，在这些国家中最多有k个国家两两相邻，则用k种不同颜色刚好可以将所有国家区分开。k是一个临界值，少于这些颜色就无法区分所有国家，多余k种颜色可以区分但是会造成浪费。
2回归原题
上面已经证明了，不管有多少国家，在这些国家中最多有k个国家两两相邻，则需要k种不同颜色即可将所有国家区分开。下面我们只要找到在考虑空间能否实现的情况下，最多有多少国家两两相邻。即可解决问题。
下面仍然要化繁为简
在讨论问题之前需要明确一个定义：相邻。本文的目的是用不同颜色来区分相邻国家。由于，两国之间只有存在长度大于零的边境才需要用不同颜色区分，两国之间只有‘点边境’时不需要用不同颜色区分。所以，只有当两国之间存在长度大于零的边境时，才被认为是相邻。
国土的形状非常复杂，如果将他化简成比较简单的几何关系。那么问题或许会变得简单一些。我们知道当两个国家相邻时，则存在一条路，使我们可以从一个国家的首都到另一个国家的首都，且不经过第三国，把种路记为直接（到达）路。直连路一定落在这两个国家的国土上，且必经过这两个国家相邻的那段的边境。换而言之，两个国家间存在直连路，则两个国家相邻（关系一）。由于，一段边境上只有两个国家；不同国家（地区）国土不重合。所以，不同国家间直连路不相交（关系二）。这里我做一下简单的解释，上文列出的两个原因分别对应两种情况：
情况一：当两条直连路有一个公共顶点（国家）时，即A国分别与B、C国相邻、存在直连路。首先，在A国外，AB，AC路在B、C国里面的一段不会相交；在A国边境上，由于一段边境上只有两个国家，所以一段边境上只会存在一条直连路；在A国国内，将A国想象成用一块圆形橡皮泥，首都在圆心，我们先将A国到每一段边境上的直连路画好（A国内部的直连路是可以自定义的），这样可以很轻松画出不相交的直连路，最后将橡皮泥拉成A国的形状就好了。
情况二：当两条路没有公共国家时，即两条路分别是AB国、CD国之间的直连路。之前定义直连路时我们知道，直连路一定落在这两个国家的国土上，即AB路上只有A或B国领土，没有CD国领土，也就是说CD路不在AB路上，即AB路与CD路不能相交。
理清这种关系之后，我们就可以用点代表国家（首都），用线代表直连路。两个点相连接（且接线之间互不相交）；即两个国家间存在直连路；即两个国家相邻。那么我们就将复杂的关系转换成了简单的几何问题。在离散数学中，前人已经对此类问题做过充足的研究。即，完全平面图中最多能有多少个结点。
直接引用可能一些人看不懂，这里就先简单的论证一下。要讨论，在考虑空间能否实现的情况下，最多有多少国家两两相邻。即是，讨论在平面上，最多有多少个点可以用不相交的线两两相连。因为，要求各点两两相连，所以节点数（国家）相同时图像是同构的。我们就不需要考虑列举的图形是否有代表性。[注释2]
首先，采用相对简单的枚举法，从小到大一个个试，如果发现N个点时就无法找到不相交的线，使各点无法两两相连。那么N+个点时就更找不到满足要求的连接方法了。首先是两个点的情况，图像是一条线段；三个点时，是三角形的三边和三个顶点；四个点时，以三点时为基础，在三角形内加一个点；五个点时，就找不到满足要求的图像了。[参考注释1]
进而用离散数学的平面图必要条件证明：m（边数、直连路）<=3n（顶点数、国家）-6[详见参考文献图论部分]。5个结点两两相连需要10条边，而公式中要求5个结点最多9条边，所以5个点不满足。
所以我们可以得出这样的结论。在平面上，最多有4个点可以用不相交的线两两相连。即在考虑空间能否实现的情况下，最多有4国家两两相邻。
综上所述：结论一：不管有多少国家，在这些国家中最多有k个国家两两相邻，则用k种不同颜色刚好可以将所有国家区分开。结论二：地图上最多有4国家两两相邻。所以，每个平面地图都可以只用四种颜色来染色，而且没有两个邻接的区域颜色相同。即地图添色时最少需要4种颜色才能满足所有情况。4是一个临界值，少于这些颜色就无法满足所有情况，多余4种颜色可以区分，但是会造成浪费。
注释：
[1]图1

由于要求N个点两两相邻，所以当N一定时图像是同构[注释2]的，我们不需要考虑列举的图形是否有代表性。
[2]规则的国土形状：
所谓规则形状，即是排除“飞地”的情况。在现实中出现国土分割两地的情况很正常，而当国土分割两地时就可能出现五个国家两两相邻的情况（如下图2）。根据上面的论证，可知当五个国家两两相邻时，至少需要5种颜色才能区别所有国家。如下图。

参考文献：
[1]洪帆.离散数学基础[M].武汉：华中科技大学出版社，2009年10月.

雨天饼干

尴尬  首行缩进忘记调了  自己的小想法希望各位指点

雨天饼干

希望各位看完后给一些意见