请选择 进入手机版 | 继续访问电脑版

QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 4447|回复: 5

四色问题的几何逻辑证明

[复制链接]
字体大小: 正常 放大

2

主题

3

听众

44

积分

升级  41.05%

该用户从未签到

发表于 2010-12-18 14:58 |显示全部楼层
|招呼Ta 关注Ta
逻辑四色问题的几何逻辑证法
徐积峰.男。生于1973.11.现工作于山东泰安粥店物探测量队,大专学历。邮编:271021。电话:13854865098。邮箱:xiaoxing_n@sina.com
前言:四色问题是拓扑学当中一个重要的命题,在当代数学中也占有相当的分量。对四色问题的研究已经由单一的图论拓扑研究延伸拓展到哲学,社会学领域。虽然在1976年,美国伊利诺大学的哈肯和阿佩尔利用计算机运行1200小时,做了100亿个判断,完成了四色问题的证明。但借助于计算机的机器证明始终无法让一些数学爱好者释怀。从拓扑几何逻辑上,经过严密的推演,完成四色的证明,成了很多数学发烧友热衷的题目。本文试图通过对相邻区域的公共边的结构类型进行分析,归纳。论证其等效命题:平面上四个两两相邻的区域中必有内包含区域。(此文的基本思想形成于947月份,当时委托我的同学——93年青岛大学的状元刘羽军找有关专业人士审证一下,不想一直未至可否。也就撂下了。这个月月初网上看到黎鸣先生与**就四色问题的相关报道,偶有来兴,整理之。)
摘要:本文的主要思路就是运用区域必闭合的定义,绕开具体的图形形状,大小的拘限,而考虑其相邻边的数量特征,公共交点分布与构成内含区域的可能性。假设存在五个互相邻的区域,那么五个便可分解为四相邻与另一个区域再相邻的问题。或者两个相邻区域与三个互相邻区域的再相邻问题。四个可分解为三相邻与一个的相邻问题考虑。但入手却是从小及大,以两个区域入手;推出两个相邻且无内包含区域的区域的特征其相邻边的数量只能为一。再分析满足三相邻无内含区域的情况,(每两个区域相邻边为一,其公共边必须交于一点)经过层层枚举,排除所有情况,得出四相邻的特征(内包含)。由于内含区域的存在,五个就不可能。实际上,分析公共边的个数,公共边的交点,每一步都是在排除内含区域的存在,排除了所有可能之方式,推出四个区域若两两相邻,必有内含区域存在,那么假设的五相邻也就不可能存在了,问题成立。所以本文大部分一直在探讨.构筑无内含区域存在的区域相邻特征。当区域数为四时,内含必然区域出现。四色问题即成立。
关键词:区域. 闭合. 公共边. 边线. 相邻. 内含区域。
引理 1:区域:即能够形成有效面积(面积大于0)的闭合的连通的曲线结构。任何区域必然是由连通的,不间断曲线(包括直线)所围成的有效面积结构。该区域上任何确定的两点A.B,都存在唯一边线AB,BA,构成该区域的所有边线。如图1.A.B点一旦确定,AB ,BA有且唯一。即一个区域内的任何两点均有连续不间断的有效边线相连。
" m% q! ?" M% a; S/ v6 U- c

" Y& b' E9 Q5 e& @8 f4 m" o; G% f1 U. f
引理2:相邻:相邻即存在共同的公共边(公共边个数≥1)。两个区域相交于一点的不构成相邻关系。
引理3:两个相邻区域相邻公共边确定,就不可能存在第三个区域以这些公共边(或其部分)为界与这两个区域相邻。两个区域的公共边不能成为第三个区域的边线。或者也可以说两个区域的公共边上任何两点之间的边线不再构成其它区域的边线(排它性)。
' b2 y; n3 S; ~) k3 O* J+ ~6 u! x

' W7 _* U) G: v3 I9 J% c5 W
8 E8 x8 q# e* F% }. X# g; p
引理4:被包含区域同构成包含区域外的其它区域不相邻
分析具有相邻关系的两个区域的公共边组成结构,及区域的相互位置(包含与否)关系。从两个区域入手,推演至三个。因为被包含区域同构成包含区域外的其他区域不相邻,在排除了所有具有内包含区域的三个互相邻区域类型后,推出一个不存在内含区域的三个互相邻区域类型,再分析第四个相邻区域与这三个相邻区域的公共边组成分布,包含与否的关系。得出:若满足平面上四个区域两两相邻,则其中必有内包含区域。本文每一步都旨在构筑一种图形结构的类型,肯定一种类型,或否定一种类型。用类型来概括规范同属于这一类(具有此类性质)的所有图形。例如在两区域相邻的讨论中,用三种关系来归纳所有两相邻区域的构成性质((1)包含,(2)不包含,相邻边数为一,(3)不包含,相邻边数≥2)。每一张图都是为了代表一种类型,勾画它的结构类型性质。图例是为了更好的表达逻辑陈述的一种外在借助手段,每一步的推导不是对一个图形具体的观察,而是在对已知条件和相关引理的反复推断中证明一个存在(边线或闭合区域)的逻辑必然性。
  一.为证明不存在两两相邻的五个区域, 首先讨论任意两个相邻区域1,2的相邻结构情况:(1)包含。如图2.
2)不包含相邻,有且只有一条公共边。如图3.
3)不包含相邻,有两条以上公共边。如图4
1)区域1被包含于区域2中,则区域1与区域2之外的任何其它区域不构成相邻关系。不满足五个区域两两相邻。此类型排除。
2)不包含相邻,有且只有一条公共边。
/ l7 v7 {9 U( t2 f* {7 B

9 O( T# X% q8 y( ?  q/ n5 G
3)不包含相邻,有两条以上公共边。为便利起见,讨论两条公共边的情况:区域1与区域2相邻于AB,CD,根据引理1(一个区域内的任何两点均有连续不间断的有效边线相连),区域1内必存在边线B⌒C1连系B与C,(根据引理一,实际上也存在其反向边C1⌒B连系B与C。B⌒C1与C1⌒B共同构成区域1,根据已知条件:区域1与区域2相邻于A⌒B,C⌒D,及引理一:闭合区域中任何确定的两点A.B,都存在唯一边线A⌒B,B⌒A,构成该区域的所有边线.用反证法可易证:A⌒B,C⌒D非存于B⌒C1即存于C1⌒B。为方便叙述,在此以反向的C1⌒B代表含有相邻边的边线,由于含有相邻边的反向边对本文的推导构不成帮助,同时反向边线与正向边线两者的存在,逻辑上为共生互容关系,所以下文的讨论均直接就不含已知区域相邻边的边线展开。)且B⌒C1不是区域2的边线。(已知区域1与区域2相邻于AB,CD,)同理,区域2也存在边线B⌒C2连系B与C.由于 B⌒C1为区域1的边线 , B⌒C2为区域2的边线,且二者不构成重合或部分重合(根据已知的,确定的相邻边)。 B⌒C1与B⌒C2相交于B,C两点,则B⌒C1与B⌒C2构成有效闭合区域,该区域计为3。区域3与区域1相邻于B⌒C1,与区域2相邻于B⌒C2。根据引理3(两个相邻区域相邻公共边确定,就不可能存在第三个区域以这些公共边(或其部分)为界与这两个区域相邻。)区域3被区域1,区域2所包含。同理将公共边拓展到n个,可证有n-1个内包含区域存于区域1.2之中,根据被包含区域同构成包含区域外的其它区域不相邻,所以,两个相邻区域中若无内含区域,则其两个区域之间的公共边只能为一个。
假设存在五个互相邻区域,那么其中的任意两个区域之间,只有两种可能:1无内含区域(有,且只一条公共边)。2有内含区域,且只为三个,因为假如为两个或一个,这两个或一个为内包含区域,根据引理4被包含区域同构成包含区域外的其他区域不相邻,就构不成五个相邻区域;并且这三个被包含的区域内再无被包含的子区域。3.这两个区域之间无完整的闭合区域,但能够与五相邻区域中其它一个或两个相邻区域共同包含另外两个或一个区域。就此本文分为两个部分探讨。12合为一个部分分析。3.的这种可能性另述。下面来分析三个无内含互相邻区域的特征,完成12的分析。
二.三区域相邻。(1)一区域包含其它两个相邻区域。如图5,或者相反,一区域被其它两个相邻区域包含。
2)三相邻区域中每两个区域的公共边只有一条,且交于一点。如图6.
图六:三个两两相邻区域,各公共边为一且交于一点
3-1):三相邻区域中每两个区域的公共边多于一条,且公共边不交于一点(为几段不连通的边线)。(3-2)三相邻区域中每两个区域的公共边多于一条,公共边交点为一(此种类型为不可能,因为两个区域的公共边多于一条,各公共边之间必然断开,即不可能出现公共交点为一的可能).直接排除。
4)三相邻区域中每两个区域的公共边只有一条,但不交于一点(公共边为三段或两段不连通的边线)如图7
1)一区域包含其它两个相邻区域,或被其它两区域包含。有内含区域,排除。
3-1. 3-2)三相邻区域中每两个区域的公共边多于一条,根据两个区域相邻公共边多于一条,必然存在内包含区域,排除(3-1)及(3-2)。
下面分析(4):公共边数量为一,交点多于一的情况。为方便讨论,以公共边为不连通的三段为例。如图7
区域1相邻区域2A⌒B,
! \. {4 Q$ j3 S/ P3 @. X' g区域2相邻区域3为C⌒D,区域1相邻区域3为E⌒F.
因为区域1相邻区域2A⌒B, 区域1相邻区域3为E⌒F,B.E两点不重合,各为区域1之边线上的两点,根据引理1得:必然存在B⌒E.因为 A⌒B与E⌒F为区域1上不连续的两段边线,根据引理3得: A⌒B上无区域3之边线.E⌒F上没有区域2之边线。B.E为区域1上的两点, (根据已知条件:区域1相邻区域2A⌒B, 区域1相邻区域3为E⌒F.) 则B⌒E上任何两点之间均无区域2.3的边线存在。同理必然存在E⌒C,C⌒B. 且E⌒C上无区域1.2之边线,C⌒B上无区域1.3之边线。如此可得由B⌒E,E⌒C,C⌒B构成的闭合有效面积之结构,计为4.区域4邻区域1为B⌒E,邻区域3为E⌒C,邻区域2为C⌒B。B⌒E,E⌒C,C⌒B连接闭合,根据引理3两个相邻区域相邻公共边确定,就不可能存在第三个区域以这些公共边(或其部分)为界与这两个区域相邻)得:C⌒B。B⌒E,E⌒C,C⌒B构成的区域4与其它区域不相邻。其内包含于区域1,2,3之间,与任何第五个区域不相邻。排除这种相邻结构。同理可证相邻边交于二点。亦有内含区域存在,不再赘述。那么只剩下一种情况: 2)三相邻区域中每两个区域的公共边只有一条,且交于一点。如图6,这实际上就是判断三个互相邻区域中有无内含区域的一个特征(公共边多于一条,无公共交点必有内包含区域)。用前文思路可证之。
对于这种三区域相邻结构。另外两个相邻区域与其再两两相邻,会有什么情况呢?三个两两相邻且无内包含区域再与两个互相邻区域两两相邻,那么这三个区域必与两个其中的一个两两相邻,下面来讨论这其中一个与另外三个的情况。如图8
区域1邻区域2AO,与区域3邻于BO.区域2与区域3邻与OC。区域4与区域1邻与S1S2,与区域2邻与S3S4.与区域3邻与S5S6。因为区域1邻区域2AO,区域1与区域4邻与S1% s0 e3 y7 v8 v/ I
S2.S2.A为区域1上之两点,由引理1得:区域1S2A存在。根据已知条件:区域1邻区域2AO,与区域3邻于BO. 区域4与区域1邻与S1S2,可得:S2A上无区域2.3.4的边线存在。同理得:区域2上之AS3存在。且AS3上无区域1.3.4的边线存在。因为S1S2为区域14的公共边,S3S4为区域24的公用边。得S2.S3为区域4边线上两点。根据引理1,必存在区域4上之边线S3S2S1S2S3S4已以相邻边方式存在)。根据区域4与区域1.2.3已知的相邻边,得S3S2上无区域1.2.3之边线。S2A. AS3. S3S2构成闭合区域X.同理:S4C,CS5.S5S4构成闭合区域Y,因为区域2邻区域1AO,邻区域XAS3.区域4S3S4.区域Y之于S4C.区域3之于OC.根据引理3:两个相邻区域相邻公共边确定,就不可能存在第三个区域以这些公共边(或其部分)为界与这两个区域相邻。则区域2为区域1.3.4.X.Y包含。同理得:区域X.Y皆为内包含区域。区域X内含于1.2.4之间。区域Y内含于2.3.4之间。根据假设:该平面存在五个互相邻区域。区域2为区域1.3.4.X.Y包含。则第五个区域必为X.Y中的一个,而区域X内含于1.2.4之间。与区域3不相邻。区域Y内含于2.3.4之间。与区域1不相邻。得出X.Y不是五相邻区域中之一。所以假设错误。再分析另一种情况:假设点S2=S3.S4=S5。即区域4与区域1.2.3的相邻边为连续的不间断连线。根据以上推导思路亦可得:区域2内包含于区域1.3.4中。不再赘证。所以,若满足平面上四个区域两两相邻,则其中必有内包含区域。
四.两个区域之间无完整的闭合区域,但能够与五相邻区域中其它一个或两个相邻区域共同包含另外两个或一个区域。这个问题可分解为(1)三区域内含两区域。(2)四区域内含一区域的两种情况。(2)四区域包含一区域的情况可将四个互相邻再分解为三个和一个。证明四个中存在内包含区域,从而排除这种可能性。(1)三区域内含两区域。转化为内含之两区域(为方便分析,可令此两区域内无内含子区域)同其外围三区域中任意一个得问题。可得这三个区域必无内含区域,否则与其外两个必不相邻,与假设矛盾。这样就又转化为三个互相邻的无内含区域再与第四个区域相邻的问题返上文所述,不再赘笔了。
综上所述,根据引理4:被包含区域同构成包含区域的其他区域不相邻。得:不存在五个两两相邻的区域。
本文实际上一直是根据设定的已知条件反复运用区域必闭合的性质,和引理3的排它性,区域必闭合揭示隐含的边线。引理3排除不存在的边线(区域),逐步将命题引向不可能性。利用文中的四条引理,实际上根据引理1,3可以有更好的,更直观严密的,不同的逻辑表达方式,因为时间关系,不能再将它构筑的更好,请各位同仁指正。
徐积峰.10.10.21.
zan

1

主题

9

听众

293

积分

升级  96.5%

  • TA的每日心情
    奋斗
    2024-2-27 00:10
  • 签到天数: 33 天

    [LV.5]常住居民I

    群组数学建模培训课堂2

    回复

    使用道具 举报

    wzlm_! 实名认证       

    2

    主题

    4

    听众

    54

    积分

    升级  51.58%

  • TA的每日心情
    无聊
    2011-11-27 23:03
  • 签到天数: 12 天

    [LV.3]偶尔看看II

    回复

    使用道具 举报

    wzlm_! 实名认证       

    2

    主题

    4

    听众

    54

    积分

    升级  51.58%

  • TA的每日心情
    无聊
    2011-11-27 23:03
  • 签到天数: 12 天

    [LV.3]偶尔看看II

    回复

    使用道具 举报

    hbdkfk2        

    0

    主题

    7

    听众

    689

    积分

    升级  22.25%

  • TA的每日心情
    开心
    2018-1-3 13:36
  • 签到天数: 124 天

    [LV.7]常住居民III

    自我介绍
    哈哈

    群组学术交流A

    群组学术交流B

    群组第二届数模基础实训

    群组A题讨论群

    回复

    使用道具 举报

    6#
    无效楼层,该帖已经被删除
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2024-3-28 23:03 , Processed in 0.580127 second(s), 79 queries .

    回顶部