春天自远方来分享 http://blog.sciencenet.cn/u/pingguo 相遇真,邂逅美,捕捉属于自己的思想。

博文

四色猜想的逻辑证明

已有 4552 次阅读 2019-11-15 14:07 |个人分类:数学|系统分类:论文交流|关键词:学者| 四色猜想, 五色定理


四色猜想的逻辑证明

 

 

证明思路

运用五色定理。设想有一张足够大的由M个国家构成的五色地图,该地图上有若干个五色区域,任意选定其中一个五色区域,我们可以沿着该五色区域的边界将它从地图上裁剪下来(无论该五色区域与外界构成怎样的相邻关系)。一种颜色代表一个国家,很显然,该五色区域由五个国家相邻构成,用S1S2S3S4S5表示这五个国家并代表它们各自不同的颜色。

第一步,我们不难证明:由五个国家构成的五色区域在平面上并不存在,只需要着四种颜色就足够了。证明这一点,我们只须将五个国家所能构成的全部相邻关系逐一列举出来即可。

第二步,从地图上任意取出的一个五色区域(实际只需四种颜色),我们发现,该五色区域必定有两个国家不相邻,而且其中一个国家必定被其他三个国家所包围而不可能再与其他任何国家相邻。假设这个被包围的国家是S5,包围它的国家是S1S2S3,与它不相邻的国家是S4。显然我们可以将国家S5的颜色改为S4,也就是,我们可以将原来从地图上取出的五色区域改为四色区域而不改变其原有的相邻关系。

(以上,我们只考虑其中仅两个国家不相邻的情形,也就是不考虑少于四种颜色着色的由五个国家构成的相邻关系。)

 

搜狗截图19年11月16日0834_1.jpg

第三步,从地图上取出的五色区域,将其改为四色之后,再放回到地图上原来的位置;很显然,原地图的国家之间相邻关系不变且着色不变。

同理,我们可以将整个地图上所有的五色区域改为四色,也就是说,我们可以按照同样的方法为地图重新着色,使之变为一张足够大的由M个国家构成的四色地图,即对于任何一张地图而言,只需四种颜色着色就足够了。

证明完毕。

 

 

更为一般情形的讨论

设想有一张足够大的由M个国家构成的N色地图(NM),在这张地图上,必定至少有一个由N个国家构成的N色区域。任意选定其中一个N色区域,用S1S2、……Si、……Sn表示这N个国家并代表它们各自不同的颜色。

在选定的这个由N个国家构成的N色区域上,去掉一个国家Si(沿着Si国的边界线将它剪下来),从而得到一个(N-1)色的区域(注意!这个过程是可逆的:我们可以将剪下来的Si重新放回去)。

N色区域与(N-1)色的区域进行比较:我们发现,由(N-1)个国家构成的(N-1)色区域,当它与Si相邻从而构成由N个国家构成的N色区域,只有当Si与这(N-1)个国家中的每一个国家构成两两相邻关系时才有可能。

M=2, M= 3, M=4时,即由2个国家相邻可构成2色地图、3个国家相邻可构成3色地图、4个国家相邻可构成4色地图。当M=5时,我们发现,由5个国家相邻并不能构成5色地图,最多只能构成4色地图。要说明这一点,我们只须将五个国家所能构成的全部相邻关系逐一列举出来即可。接下来,用反证法,假设存在一张足够大的由M个国家构成的五色地图,按照前面的第一步、第二步、第三步证明思路,进行证明。

 

本文中的证明方法可能为三维空间乃至多维空间中的相关问题提供了一个解决思路。

 

 

两种基本相邻关系——本证明的逻辑起点

平面或球面上,AB两个国家相邻有且只有两种方式:一种是,A国家的部分边界与B国家的部分边界相邻;另一种是,A国家的全部边界与B国家相邻,即A国家被B国家所包围(无需考虑A国家与B国家完全重合的情形,因为这在四色问题上没有意义)。
   
需要指出的是,图中的红色与绿色可以互换,即,当只有两个国家相邻时,下图中的国家A与国家B是等价的:哪一个为红色,哪一个为绿色,意义是一样的(在下文的表述中同样的情形不再说明)。

搜狗截图19年11月16日0835_2.jpg

 

设想有一张由m+1个国家构成的地图,它显然可以视为由m个国家与某一个国家A以任意可能的方式相邻构成的。当m=1时,即为最初两个国家构成的地图;m=k时,即为由k+1个国家构成的任意可能的地图。

1、  如果地图由两个国家相邻构成,需要两种颜色。

2、  如果地图由三个国家相邻构成,最少需要两种颜色,最多需要三种颜色;只有当这三个国家两两相邻的时候,才需要三种颜色。
搜狗截图19年11月16日0836_3.jpg

3、  如果地图由四个国家相邻构成,最少需要两种颜色,最多需要四种颜色;只有当这四个国家两两相邻的时候,才需要四种颜色。如下图:
搜狗截图19年11月16日0837_4.jpg

4、  如果地图由五个国家相邻构成,最少需要两种颜色,最多需要五种颜色;只有当这五个国家两两相邻的时候,才需要五种颜色。
实际上,平面或者球面上最多只能构造四个两两相邻的国家。

 

增色定理
n个国家构成的地图最多需要n种颜色,并且,只有当这n个国家两两相邻时才需要n种颜色。

这一点不难证明。设n个国家的名称与颜色分别为S1S2S3,……,Sn,假设该地图只有前n-1个国家两两相邻,第Sn个国家仅与其中的k个国家相邻(kn-1),那么,国家Sn颜色只要与这K个国家的颜色不同即可,它可以取与之不相邻的(n-k-1)个国家的任意一种颜色。同理,可以假设该地图只有前(n-2)、(n-3)、(n-4)、……、54个国家两两相邻,得到类似的结论。


推论
在由m个国家构成的n色地图上,以任意可能的方式增加一个国家A,若国家A与该n色地图上的k个国家相邻(kn),则由此构成的m+1个国家地图仍为n色地图;只有当国家A与该n色地图上的n个国家都相邻,才需要n+1种颜色

推论不难证明。n色地图意味着这个由m个国家构成的地图,它的某个局部必须用n种颜色着色,即该地图的某个局部有n个国家两两相邻。

 

 


 

附件一 四色猜想相关概念及五色定理内容的介绍

 

 

 

四色猜想的提出

四色猜想是弗伦西斯·格斯里(FrancisGuthrie1831-1899)提出的,1852年他在给弟弟的信中写到:“每幅地图都可以只用四种颜色着色,使得有公共边界的相邻国家着上不同的颜色。”四色猜想又称四色定理、四色问题。

格斯里的话中包含两个需要明确的概念:一个是相邻;另一个是国家,即平面或球面上的一个区域。为此给出两个定义。

 

 

两个需要明确的概念

1、单连通:一个区域内的任何两点,如果可以在其内部(即不穿过其边界)用一条曲线相邻,则称这个区域是单连通的。四色猜想中涉及到的区域均指的是单连通区域。

2、相邻:平面或球面上的两个区域,如果只有一条公共边界,就说这两个区域是相邻的。

 

 

五色定理的内容

将一个平面分成若干区域,给这些区域染色,且保证任意相邻区域没有相同颜色,那么所需颜色不超过五种。

 


 


附件二 平面或者球面上最多只能构造四个两两相邻的国家

 

 

证明这一点,只须例举出全部五个国家相邻的情形即可。我们不妨从两种基本相邻关系出发,来更清晰地说明这一点。

 

1-1前面我们已经知道,平面或球面上,AB两个国家相邻有且只有两种方式:如图一、图二。

搜狗截图19年11月16日0835_2.jpg
        图1                                            2

1、图2与第三个国家相邻,如2-12-2

 

2-1图一与第三个国家相邻,有如下三种方式

搜狗截图19年11月16日0840_5.jpg
        3                            4                         5

 

2-2 图二与第三个国家相邻,有如下两种方式
4

            6                               7

 

3、图4、图5、图6、图7与第四个国家相邻,如3-13-23-33-43-5

 


 

3-1 图三与第四个国家相邻,有如下四种方式

8

        8                                     9

9

    10                                  11

 

3-2 图四与第四个国家相邻,有如下四种方式

10

       12                             13

000

       14                                 15

 

3-3 5与第四个国家相邻,有如下两种方式 (以下略)

 

从以上可知,两个国家相邻有两种方式;三个国家相邻有五种方式……

由三个国家相邻的五种方式,与第四个国家相邻即构成全部四个国家相邻的方式,最多只需四种颜色即可。

 

 


 

 

注:这里发表的是改进后的版本,原文201622日发表于科学网博客。

 

 

                                                          王平

                                                   20191115

 

 

数学的美妙之处在于它是简单性与深刻性相统一的事物。诸多真与美的事物也是如此。

数学的困难之处在于,你感觉自己直接面对着上帝,却从不知道上帝在哪里。

如果把数学视为一个游戏,它也许是唯一一个上帝愿意陪你玩的游戏,可是你永远不知道上帝怎么玩。

 

 

正文中的一些插图未显示,请下载本文的PDF文档:

四色猜想的逻辑证明-20191115.pdf






我的更多数学论文,请点击进入:

关于哥猜的再猜想

微分中值与积分中值关系定

罗尔定理引用辅助函数的证明方法

利用不定方程的对称性巧证费马大定理

 

 




https://m.sciencenet.cn/blog-2376-1206285.html

上一篇:古老的自言自语
下一篇:有孤独的成分在

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-28 20:13

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部