|
|
[这个贴子最后由hanzhixin在 2006/02/19 04:52pm 第 2 次编辑]
析四色定理和七色定理
韩治新
（民权县公安局，河南 民权 476800）
摘 要:本文介绍了四色和七色定理的概念,分析了在平面上和在球面上为地图着色时具有相同的性质,分析平面地图染色性质时得出两条结论,一是最多只有四个图形可以两两相邻,二是假定一定数量的图形用四种颜色来染色,使得任何具有共同边界的两个图形的颜色都不同,那么其最外围的图形存在使用3种及其以下颜色染色的可能性. 前者是四色定理成立的前提,后者为四色定理成立的递推奠定了基础,利用数学归纳法可以构筑一个简捷明快的证明.一个环面可以由球面去图对接转换而成,所以能够用四色定理分析七色定理.
关键词: 两两相邻；四色定理；七色定理
中图分类号: O157.5 文献标识码：A
1 四色和七色定理的概念
1852年,伦敦大学学生Francis Guthrie提出:“看来,每幅地图只需要用四种颜色着色, 便可以使得所有有共同边界的国家着上不同的颜色”.这就是被誉为世界近代三大数学难题的四色定理.
1890年, 英国数学家Heawood证明了环面上的任意地图可以用七种颜色着色,并提出环面上七个图形两两相邻的特例. 如图1,粘合矩形的对边,把它上面的七个地区转换到环面上, 使得每两个地区都相邻,即所有七个地区应该着上不同的颜色.
图 1
2 四色和七色定理的证明
2.1 有关平面地图染色的条件、性质和定理
我们在通常表述四色问题时, 常常忽视四色定理成立约定俗成的两个先决条件. 一是两国相邻是指它们的公共边界上至少包含一段连续曲线, 因此两个只在一个或有限个点接壤的国家不算相邻. 否则我们可以构造出任意多个在一点彼此相邻的国家, 当然绝对不能用四种颜色对它们染色使得任何两个相邻的国家染上的颜色都不同. 二是国家是指由一条或若干条不自交的连续闭曲线围起来的连通闭曲域, 但是一个国家不能有两块或两块以上互不毗邻的领土.
一个平面上的地图可以通过这样的方式转换到球面上去.如图2,我们这样想象,保持所有的单个图形相邻性质不变,只是作一些形状和大小的改变,而把地图以外的广大区域想象为一个点, 通过扭曲闭合转化为球面,不难想象,此时球面上地图和平面上地图保持着相同的性质；反之亦然,在球面上的地图,我们先寻找若干个图形的一个公共点 (可视为公共点在若干个图形上,也可视为公共点不在若干个图形上,另外也可以是一条公共线段),沿这个公共点(公共线段)展开可得平面图.这就是说在平面上的四色定理,扩展到球面上照样适用.为了论证四色定理,引入以下定理.
图2 图3
定理1 在平面或球面上,最多只有四个图形可以两两相邻.在研究平面地图的单个区域图形两两相邻问题时,两个图形两两相邻,三个图形两两相邻情形较简单,在此不作详述. 如图3,在四个图形两两相邻时,中间的图形已经被外围三个图形完全包围.中间的那个图形不可能再和其他图形相邻了,所以最多只有四个图形可以两两相邻,不可能有五个或者更多的图形两两相邻,这是四色定理成立的前提. 事实上,在平面或球面上二、三、四个图形两两相邻情形是唯一的.
定理2 假定任意n个图形组成的地图四色定理正确,那么由n-1,n-2,……5个图形组成的地图四色定理正确,且由n-1，n-2,……5个图形组成的地图最外围图形存在使用3种及其以下颜色染色的可能性.利用反证法可以证明此命题的正确性,如果由n-1,n-2,……5个图形组成的地图最外围的图形必须使用4种颜色染色,那么当一个图形完全包围n-1，n-2,……5个图形时,n个图形的情形四色定理就不正确,从而产生了与已知假设的矛盾.此定理也可理解为多数复杂地图蕴涵少数简单地图染色问题.
定理3 假定任意由n个图形组成的地图四色问题正确,那么其最外围的图形存在使用3种及其以下颜色染色的可能性.
证法1:任意的由n个国家构成的平面地图，假定4种颜色染色满足要求,如图4,对于+号和*号之间的n-1个国家,根据定理2, 带*号的边沿的国家不能用4种颜色染色, 同样带+号的边沿的国家也不能用4种颜色染色(如果带+号的边沿的国家用4颜色染色,当外围有一个图形和带+号的边沿国家相邻时四色定理就不正确).
证法2:假定对于由n个国家构成的平面地图4种颜色染色满足要求, 如图4, 假定最外围的(带+号)必须用4种颜色染色,那么我们总可以找到其中自相矛盾的情形. 因为在最外围的国家中必有同种颜色的两个国家,当一个国家环抱所有带+号的国家时，就产生了矛盾,所以最外围的图形存在使用3种及其以下颜色染色的可能性.
2.2 浅析四色和七色定理
首先利用数学归纳法证明四色定理.
（一）显然，对于任意的由1、2、3、4个组成的图形,四色定理正确.对于任意的5个图形组成的图形，根据“最多只有四个图形可以两两相邻”的分析，可知任意的5个图形时四色定理正确.
（二）假设任意n个图形时四色定理正确,那么我们分析n+1个任意的地图图形.
因为假设任意的n个图形四色定理正确,根据前面的分析, 可知其最外围存在使用3种颜色或者3种以下颜色染色的可能性,所以任意n+1个图形时四色定理正确.
任意的一个环面可以这样由球面转换. 假想在拥有很多地图图形的球面上,从两端各去掉一个图形,从刚才的分析可知两端使用三种颜色或者三种以下的颜色就足够了,如果一端由A、B、C或者三个以下包围, 另一端由B、C、D(或者A、B、D或者A、C、D）及其以下包围, 只要把另一端的B、C(或者A、B或者A、C)换为E、F就行了,此时用六色就足够了.如果两端均由A、B、C三色包围, 这时需要把一端的A、B、C换为E、F、G三色，因为中间还有用颜色D的，此时需要七色.
3 说明
由于四色问题涉及到无穷尽图形的染色问题，只能作一些浅显的理论分析，当前还不能找到具体染色的法则，就是说,如果给我们一个较为复杂的地图,我们还不能简捷的人工染色.在分析这些问题时,使用动态的分析方法，即视为地图的单个图形在不改变总体着色性质的情况下,单个或部分图形是可以变化的.地图染色问题针对不同的条件会有不同的结论，在一条直线上，只需要两种颜色就可以把一条直线分成无数段，平面和球面上的地图需要四色，环面上则需要七种颜色，在三维空间上任意堆积严密的实物模型因两两相邻不受限制,所以没有最少数目的颜色将其区别. 正象我们饭碗里的面条, 每根面条显然是可以粘合的（两两相邻的）,所以我们不能用有限种颜色把他们分开,而且使相邻的颜色均不同.
参考文献
[1]Robertson N,Sanders D.P,Thomas R.The Four Color Theorem.The Four Color Theorem[EB/OJ].http://www.math.gatech.edu/~thomas/FC/fourcol-
or.html.
[2]Eric W. Weisstein. Heawood Graph From Math World-A Wolfram Web Resource[Z].http://mathworld.wolfram.com/HeawoodGraph.html
[3]中国数学会.四色问题[Z].http://159.226.47.206/cms/popularize/1a/1a
-2/1a2q028.htm.
[4]中国数学会.解决四色猜想的历程(一)[Z].http://159.226.47.206/cms/po
-pularize/1a/1a2/1a2q029.htm.
A simple analysis of the four color theory and
the seven color theorem
HAN Zhi-xin
(Public Security Bureau of Minquan County,MinQuan,Henan,476800,China)
Abstract: This thesis has analyzed that there is the same nature while coloring for the map on the level and on the sphere.And has drawn two conclusions while analyzing the nature of the plane map: First,there are only four figures all right two-two adjoin at most.Second,if to color certain amounts of figures with four kinds of colors, make the colors of any two figures with common borders both different. In this way, there is a possibility that can be colored the most peripheral figures with 3 colors or less than 3 colors. The first conclusion is the foundation that the Four Color Theory can be estalished, and the second conclusion has established the foundation for the recursion of this theory.So it can be provided easily by the mathematical induction. A torus map can be changed by a sphere map by the method of deleting figures and end-to-end joint. Therefore we can analyze the seven color theorem by the principle of the four color theorem.
Key words: two-two adjoining; four-color theory; seven-color theorem
作者：韩治新,男,汉族,1968年1月20日生,本科文化程度
时间：2004年12月31日完稿，2005年11月7日修改
单位：河南省民权县公安局
Email: han.zhixin@sohu.com
手机：13569321521
 |
|
IP卡
狗仔卡
发表于 2006-2-19 16:47
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
楼主