论文部分内容阅读
摘要：1852年，毕业于 伦敦大学的格斯里（Francis Guthrie）来到一家科研单位搞地图着色工作时，发现每幅地图都可以只用四种颜色着色。这个现象能不能从数学上加以严格证明呢？他和他正在读大学的弟弟决心试一试，但是稿纸已经堆了一大叠，研究工作却是没有任何进展。1852年10月23日，他的弟弟就这个问题的证明请教了他的老师、著名数学家德·摩尔根，摩尔根也没有能找到解决这个问题的途径，于是写信向自己的好友，著名数学家 哈密顿爵士请教，但直到1865年哈密顿逝世为止，问题也没有能够解决。1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。
关键词：四色猜想；五色定理；
铺瓦定理：如果任意简单的二维图形被分割为充分小的区域，则不论这些区域的形状如何，必然有这样一些点使三个或更多个区域在那里相遇，另外，一定存在图形的这样一种剖分，使得每个点至多同时属于这剖分的三个区域。
我们关心的平面地图着色问题，而不是关心一个国家疆界是正方形还是圆形，因此我们可以利用平面图形的拓扑关系，总可以把一副简单（几何关系简单不是外形简单）图形拓扑的等效于铺瓦定理图形。铺瓦定理图形，是一个国家最多和另外两个国家彼此比邻。比铺瓦定理图形稍微复杂一点几何图形关系，是一个国家被三个国家围绕，而且其中一个国家和另外三个国家保持彼此都相邻，这样，显然需要着四种颜色，要不然就要撞色。如图：
这种几何关系，也可以把铺瓦定理中实心点改成空心点来等效。此种几何结构是平面几何结构中最复杂的，如果再多一个国家就不能彼此保持这种其中一个与另外四个都彼此间相邻的几何关系。因此，经过上述分析，我们知道一张地图中，不管多复杂，界点总可以分成如下三类，如图：
可见，一副地图着四色是平面图形几何结构关系决定。一副地图着四种颜色够吗？这个完全取决于地图中国家与国家疆界之间的几何关系，而且是综合几何关系，而不是简单的国家的数量。假设用1、2、3、4和5，5个数字代替5种颜色。我们知道一副地图国与国之间存在着界线，这两个国家和至少其他一个国家相界，那么必存在一个界点。因此，一副地图，到处充满着界点，而且界点是至少3个国家的界线的交点，有些是4个国家，有些是5个国家，有些甚至更多。我们规定，1个国家被超过3个，如果达8个国家围绕，那么多出来6个国家，是偶数个，按照1-2-1-2-1-2排列；如果多出来的国家是奇数个呢？我们按照1-2-1-2-1排列，这样排列是基于为了满足最少着色要求。
现在我们讨论第③类界点数字标注情况，我们用图形来分析这些界点的几何关系：
考虑最复杂的那种几何关系；假如有两个区域已经标注了3和4；那么，另外还有两种情况与之共点，1、奇数个国家与之共点，根据上文最小着色要求的规定，那么只需要标注4个数字即可；2、偶数个国家与之共点，那么也只需要标注4个数字即可。具体如下图，
根据上图形分析，在复杂的第③类界点几何关系下，我们标注了4个数字，如果遇到更复杂的几何关系，我们把黑色界点标注5即可；而且，3和4如果不相邻，那么他们之间我们可以插入标注1和2，不影响格局。地图上出现了5，那么还会出现更复杂的几何关系吗？不会，我们可以用5代替3，结果仍然只需要标注4个数字，然而遇到更复杂的几何关系（第③类界点是最复杂的几何关系），我们用被代替3标注黑色界点即可。
另一种方法标注，我们知道地图的界点有三类，我们从最复杂第③类界点开始标注，让中心圆圈标注4，最复杂情况下，用1、2和3标注其他区域；接着同样让第②类界点中心圆圈标注4，其他显然标注1、2和3；那么剩下地图上都是第①类界点，而且地图上除了圆圈内的4之外，全是1、2和3；排得好1、2和3正好排上第①类界点的三个区域；排的的不好，比如其中两个区域已经排了1和2，剩下一个区域仍然必须排1或2，此时我们选择4代替1或2即可；最坏的情况，就是第①类界点的三个区域必须排同样的数字比如三个2，那么我们可以在地图版面上交换第③类界点中的1和2的位置或者2和3的位置，或者兩者同时交换，看看还会不会出现同样的数字同排的现象，如果仍然出现，我们用4和5代替两个2即可，此时需着五色。
经过分析，不管地图上国与国之间的关系多么的复杂，理论上只需着五色，即可区分国与国之间的疆界而不撞色。在实际地图着色中，我们可以选择第③类界点中国家数量最多那个为中心进行着色，向周围扩散，用没有边界的这个条件换取第5色；更何况，我们遇不到国与国之间的复杂的几何综合关系，再加上选择性着色，因此，着四色即可。
（作者：浙江省宁波市人，邮编315600）
关键词：四色猜想；五色定理；
铺瓦定理：如果任意简单的二维图形被分割为充分小的区域，则不论这些区域的形状如何，必然有这样一些点使三个或更多个区域在那里相遇，另外，一定存在图形的这样一种剖分，使得每个点至多同时属于这剖分的三个区域。
我们关心的平面地图着色问题，而不是关心一个国家疆界是正方形还是圆形，因此我们可以利用平面图形的拓扑关系，总可以把一副简单（几何关系简单不是外形简单）图形拓扑的等效于铺瓦定理图形。铺瓦定理图形，是一个国家最多和另外两个国家彼此比邻。比铺瓦定理图形稍微复杂一点几何图形关系，是一个国家被三个国家围绕，而且其中一个国家和另外三个国家保持彼此都相邻，这样，显然需要着四种颜色，要不然就要撞色。如图：
这种几何关系，也可以把铺瓦定理中实心点改成空心点来等效。此种几何结构是平面几何结构中最复杂的，如果再多一个国家就不能彼此保持这种其中一个与另外四个都彼此间相邻的几何关系。因此，经过上述分析，我们知道一张地图中，不管多复杂，界点总可以分成如下三类，如图：
可见，一副地图着四色是平面图形几何结构关系决定。一副地图着四种颜色够吗？这个完全取决于地图中国家与国家疆界之间的几何关系，而且是综合几何关系，而不是简单的国家的数量。假设用1、2、3、4和5，5个数字代替5种颜色。我们知道一副地图国与国之间存在着界线，这两个国家和至少其他一个国家相界，那么必存在一个界点。因此，一副地图，到处充满着界点，而且界点是至少3个国家的界线的交点，有些是4个国家，有些是5个国家，有些甚至更多。我们规定，1个国家被超过3个，如果达8个国家围绕，那么多出来6个国家，是偶数个，按照1-2-1-2-1-2排列；如果多出来的国家是奇数个呢？我们按照1-2-1-2-1排列，这样排列是基于为了满足最少着色要求。
现在我们讨论第③类界点数字标注情况，我们用图形来分析这些界点的几何关系：
考虑最复杂的那种几何关系；假如有两个区域已经标注了3和4；那么，另外还有两种情况与之共点，1、奇数个国家与之共点，根据上文最小着色要求的规定，那么只需要标注4个数字即可；2、偶数个国家与之共点，那么也只需要标注4个数字即可。具体如下图，
根据上图形分析，在复杂的第③类界点几何关系下，我们标注了4个数字，如果遇到更复杂的几何关系，我们把黑色界点标注5即可；而且，3和4如果不相邻，那么他们之间我们可以插入标注1和2，不影响格局。地图上出现了5，那么还会出现更复杂的几何关系吗？不会，我们可以用5代替3，结果仍然只需要标注4个数字，然而遇到更复杂的几何关系（第③类界点是最复杂的几何关系），我们用被代替3标注黑色界点即可。
另一种方法标注，我们知道地图的界点有三类，我们从最复杂第③类界点开始标注，让中心圆圈标注4，最复杂情况下，用1、2和3标注其他区域；接着同样让第②类界点中心圆圈标注4，其他显然标注1、2和3；那么剩下地图上都是第①类界点，而且地图上除了圆圈内的4之外，全是1、2和3；排得好1、2和3正好排上第①类界点的三个区域；排的的不好，比如其中两个区域已经排了1和2，剩下一个区域仍然必须排1或2，此时我们选择4代替1或2即可；最坏的情况，就是第①类界点的三个区域必须排同样的数字比如三个2，那么我们可以在地图版面上交换第③类界点中的1和2的位置或者2和3的位置，或者兩者同时交换，看看还会不会出现同样的数字同排的现象，如果仍然出现，我们用4和5代替两个2即可，此时需着五色。
经过分析，不管地图上国与国之间的关系多么的复杂，理论上只需着五色，即可区分国与国之间的疆界而不撞色。在实际地图着色中，我们可以选择第③类界点中国家数量最多那个为中心进行着色，向周围扩散，用没有边界的这个条件换取第5色；更何况，我们遇不到国与国之间的复杂的几何综合关系，再加上选择性着色，因此，着四色即可。
（作者：浙江省宁波市人，邮编315600）