当前位置:刘伯温火凤凰公式网 > 三角剖分 >

四色问题书面证明方法

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  2013-09-03展开全部好啊 这个问题我以前回答过 不过我看不懂 贴过来探讨下——解答由以下ABCD四部分组成

  本文在原有的拓朴学、图论、及着色理论的基础上增加了一些必不可少的公理、定理及定义,从而建立了在着色问题上比较完善的理论系统,并采用了一些新的方法,证明了球面上及平面上平面图的四色定理。即在球面或平面上对于任何平面图有X(G)≤4。

  假设四色定理不能成立,即存在某平面图是必须用5种或5种以上的颜色来着色。即有X(G)≥5,不失一般性,可作一个任意复杂的图,如图(3),(注:读者也可在此尝试选择其它任何形状的图)其中的实线部分表示全图的一个很小的局部图,虚线部份表示省略了的大部份图形。其复杂程度可以由读者任意构筑和想象,但必须是“有限图”而不应该是“无限图”。

  第一步:在保持原图的所有点与连线的基础下,再将原图中尚未相连但却能够相连的各点两两之间尽可能多地连接起来,(应注意不再增加新的着色点,而仅仅增加连线)直至成为“三角剖分图”为止。由前面定理5可知这样处理之后新图的着色数不会比原图减少,这一步称之为“添线”。

  第二步:任取图内某一个“圈内点”及围绕这点的“最小圈”进行分析。例如我们取的这个“圈内点”为V ,且在“添线”时我们已经连接了V 与V 及V 与V ,并且还连接了V 与V 及V 与V …已经把原图变成了一个“三角剖分图”这时V 的“最小圈”就是V —V —V —V —V —V 。对于这个“局部图形”进行着色调整与分析。根据定理4,我们可以把V 的最小“点外圈”安排第一、第二、第三种颜色进行着色。把V 安排为第四种颜色进行着色。若然后再给所有“圈外的点”都着上颜色,由假设可知其“着色数”X(G)≥5,但由前面的“公理2”和“公理3”可知“圈内点”与“圈外点”不可能直达,故可以把V 这点的着色由原来安排的第四种颜色调整为第五种颜色,再由定义5可知若这时把V 这点连同V 直接相连的所有连线都去掉。这样做也并不会减少原图的“着色数”。(因为V 这点是被它的四周的“最小圈”阻断隔绝在圈内的,它与“圈外点”的着色是无关的。如果说这样做减少了原图的着色数,例如“着色数”从五减少为四,则说明原图的“着色数”本来就应该是四。)这一步称之为“去点”与“去线”。(这时的V 点是“着色可省略点”,而V 点既然已经去掉,则与它直接相连的各条线,也就自然没有存在的必要了。因为本文采用的是点着色的方法。)

  第三步:反复对图中其它各“圈内点”作第一步的“添线”或第二步的“去点”与“去线”,(可交替或不交替地使用)直至对图中的任何一点来说都再也没有“圈内点”可去了为止。最终使它成为一个“三角剖分图”。因为“点”在一个又一个地减少,且“圈内点”与“圈外点”是相对而言的。所以最终的结果只能如图(1)或图(2),即得到只有一个“圈”且圈内只有一个点的图(这时“圈内点”与“圈上点”相连)或一个只有“圈上点”的“三角剖分图”。但这时的“着色数”X(G)≤4。这显然与开始的假设X(G)≥5相矛盾,所以一开始的假设X(G)≥5是错误的。故在“球面”或“平面”上的着色数有X(G)≤4成立。证明完。

  一条定理希望得到证明,必须依靠一个完善的理论系统。在这个系统中有尽可能少但却是足够的公理和基本概念,以及足够的定理、定义、公式等。如果缺少了其中任何一个环节,论证就会变得寸步难行。四色定理之所以长期得不到理论性而非计算机进行的证明,主要就是因为没有建立起一个既简要而又完善的理论系统。下面所列出的公理、定理、定义大都是证明四色定理所需要的,其中绝大部分都是原来拓朴学和图论和着色理论中已有的,极少是新增加的。

  在“球面”或“平面”上在着色问题中的最重要的特点就是任何“圈”在“球面”或“平面”上的“阻断”作用。同样“圈”在所有“简单多面体”上也有这样的“阻断”作用。但在“非简单多面体”上有些“圈”就不再具有这种“阻断”作用,本文正是利用了这一特点证明了“四色定理”。

  “简单多面体”的顶点数,E是“棱数”F是“面数”)采用了逐步“去线”“去面”“去点”的方法,而本文采用的是先“添线”然后再逐步“去点”与“去线”…反复进行,最终完成了证明。这两种方法虽然不完全相同但却有相似之处。

  公理1:任何直达的(直接相连接的)两点,必须采用不相同的颜色。(注:本文均采用“点着色”的方法)

  公理3:在“平面”或“球面”上任何一个“封闭圈”(指若干条首尾相连的“线”所构成的图形)都可将“平面”或“球面”“分断隔离”成为不能直达的两部份,即这一部份内(即这个“圈”内)的点必须经过“封闭圈”(以后简称为“圈”)上的点才能到达另一部份内(即这个“圈”外)的点(在着色问题中,“线”与“线”之间是不能交叉的。因为如果“线”与“线”之间交叉则它们显然不能处于同一“平面”或“球面”上了。

  公理4:在“环面”(形如普通的救生圈)上有些“封闭圈”是不能起到“分断隔离”的作用的。即“圈”一侧的“点”可以不必非要通过“圈”上的点就可以到达“圈”的另一侧的点。(这种“环面”实际上是“七可着色”的,但本文不加以讨论)

  (注:本文中凡未加证明的定理均为“拓扑学”及“图论”中已有的定理,例如本文中的定理1、定理2、定理3、等。另外本文中所列举的公理也都是各种拓扑学和图论书中经常采用的,只不过是没有明确地列举出来而已)

  定义1:一个“奇圈”或“偶圈”内有一些点,则这些点叫作这个圈的“圈内点”。这个“圈”叫作这些点的“点外圈”。

  定义2:一个“奇圈”或“偶圈”外有一些点,则这些点叫作这个圈的“圈外点”。

  定义3:一个“奇圈”或“偶圈”上有一些点,则这些点叫作这个圈的“圈上点”。

  定义5:如果去掉了某一个“着色点”之后并不改变原图的“着色数”,那么称这点为“着色可省略点”。

  定理4:如果一个图中仅有一个“圈”及圈内仅有一个点,且这点与“圈上点”都分别相连则这个图的着色数:X(G)≤4。

  定理5:在平面图中增加一条连接原图中尚未连接的两点之间的连线,都不会减少原图的着色数。

  证明:假如这后来被连接的两点的原来的颜色是不相同的则连接之后也不用增加原来的着色数。假如这两点原来的着色是相同的,则此时有必要将其中的一个着色点改变为另一种颜色,则这时该图在局部需要再增加一种颜色。在该图的整体则可能增加一种颜色也可能不增加颜色,但不可能减少颜色.证明完。

  定理6:一个仅有“圈上点”(即既没有“圈内点”又没有“圈外点”)的三角剖分图是3可着色的。即X(G)=3

  证明:如图(2)有圈ABCDEFG……先对其中的某一个三角形的三个顶点着色。例如对A、B、C三个顶点分别着上第1、第2、第3共三种不同的颜色。然后对下一个与ΔABC有公共边AC的ΔACD的顶点D着上与B点相同的第2种颜色。然后再对下一个与ΔACD有公共边AD的ΔADF中的顶点F着上与C点相同的第3种颜色。……如此继续下去,就可以用3种不同的颜色给所有的顶点分别着色。这就证明了对于这种仅有“圈上点”的三角剖分图是3可着色的。即X(G)=3 证明完

  证明:在原图的基础上在圈内再增加若干条连线,使其成为“三角剖分图”这样做之后不会减少原图的着色数(根据定理5)。所以有X(G原)≤X(G新)。但增加了“连线”之后,新图的着色数

  定理7:对于任何平面图有着色数:X(G)≤5(此定理在本文证明四色定理时可以不利用,但若利用此定理则在叙述本文的证明时会更为方便些,此定理在各图论书中均有证明)

  定理8: 任何一个封闭的三维空间,只要它里面所有的封闭曲线都可以收缩成一个点,这个空间就一定是一个三维圆球。(庞加莱定理)

  定理8推论:在“球面”上挖一个“洞”就变成了拓扑学意义上的“平面”了。在“球面”上挖二个“洞”就变成了拓扑学意义上的“圆柱侧面”了。在“球面”上不论挖多少个“洞”都不会改变原来“球面”上的“着色数”。

http://idagoldadv.com/sanjiaopoufen/125.html
点击次数:??更新时间2019-06-07??【打印此页】??【关闭
  • Copyright © 2002-2017 DEDECMS. 织梦科技 版权所有  
  • 点击这里给我发消息
在线交流 
客服咨询
【我们的专业】
【效果的保证】
【百度百科】
【因为有我】
【所以精彩】