庞加莱公式_百度文库

庞加莱公式_数学_自然科学_专业资料。1 四色定理的非计算机证明:庞加莱定理的一个应用 何宗光(浙江科技工程学校) 何宗明(上海医疗器械五厂) 摘 要 本文在原有的拓朴学、 图论、 及着色理论的基础上增加了一些必 不可少的公理、

1 四色定理的非计算机证明:庞加莱定理的一个应用 何宗光(浙江科技工程学校) 何宗明(上海医疗器械五厂) 摘 要 本文在原有的拓朴学、 图论、 及着色理论的基础上增加了一些必 不可少的公理、 定理及定义, 从而建立了在着色问题上比较完善的理 论系统, 并采用了一些新的方法, 证明了球面上及平面上平面图的四 色定理。即在球面或平面上对于任何平面图有 X(G)≤4。 关 封闭圈, 分断隔离, 着色调整与分析, 键 词 着色可省略点, 三角剖分图, 添线, 去点, 去线。 一、 引 言 一条定理希望得到证明, 必须依靠一个完善的理论系统。 在这个系 统中有尽可能少但却是足够的公理和基本概念, 以及足够的定理、 定 义、 公式等。 如果缺少了其中任何一个环节, 论证就会变得寸步难行。 四色定理之所以长期得不到理论性而非计算机进行的证明, 主要就是 因为没有建立起一个既简要而又完善的理论系统。下面所列出的公 理、定理、定义大都是证明四色定理所需要的,其中绝大部分都是原 来拓朴学和图论和着色理论中已有的,极少是新增加的。 在“球面”或“平面”上在着色问题中的最重要的特点就是任何 “圈”在“球面”或“平面”上的“阻断”作用。同样“圈”在所有 “简单多面体”上也有这样的“阻断”作用。但在“非简单多面体” 2 上有些“圈”就不再具有这种“阻断”作用,本文正是利用了这一特 点证明了“四色定理” 。 另一方面,数学家欧拉在证明“欧拉公式”V+F–E=2(其中 V 是 “简单多面体” 的顶点数,E 是 “棱数”F 是 “面数” 采用了逐步 ) “去 线” “去面” “去点”的方法,而本文采用的是先“添线”然后再逐步 “去点”与“去线”…反复进行,最终完成了证明。这两种方法虽然 不完全相同但却有相似之处。 二、预 备 公理 1:任何直达的(直接相连接的)两点,必须采用不相同的 颜色。 (注:本文均采用“点着色”的方法) 公理 2:任何不能直达的两点可以采用相同的颜色着色。 公理 3:在“平面”或“球面”上任何一个“封闭圈” (指若干 条首尾相连的“线”所构成的图形)都可将“平面”或“球面” “分 断隔离”成为不能直达的两部份,即这一部份内(即这个“圈”内) 的点必须经过“封闭圈” (以后简称为“圈” )上的点才能到达另一部 份内(即这个“圈”外)的点(在着色问题中, “线”与“线”之间 是不能交叉的。因为如果“线”与“线”之间交叉则它们显然不能处 于同一“平面”或“球面”上了。 公理 4:在“环面” (形如普通的救生圈)上有些“封闭圈”是 不能起到“分断隔离”的作用的。即“圈”一侧的“点”可以不必非 要通过“圈”上的点就可以到达“圈”的另一侧的点。 (这种“环面” 3 实际上是“七可着色”的,但本文不加以讨论) 定理 1:每一个没有三角形的可平面图是 3 可着色的(即 X(G) ≤3) (注:本文中凡未加证明的定理均为“拓扑学”及“图论”中已 有的定理,例如本文中的定理 1、定理 2、定理 3、等。另外本文中 所列举的公理也都是各种拓扑学和图论书中经常采用的, 只不过是没 有明确地列举出来而已) 定理 2:一个图是双可着色的,当且仅当它没有“奇圈” 。 定理 3:在“平面”或“球面”上的完全图 K 4的着色数为 4。 定义 1:一个“奇圈”或“偶圈”内有一些点,则这些点叫作这 个圈的“圈内点” 。这个“圈”叫作这些点的“点外圈” 。 定义 2:一个“奇圈”或“偶圈”外有一些点,则这些点叫作这 个圈的“圈外点” 。 实际上“内”与“外”都是相对而言的。特别是在“球面”上更 为明显。 定义 3:一个“奇圈”或“偶圈”上有一些点,则这些点叫作这 个圈的“圈上点” 。 定义 4:如果一个圈内仅有一个点,则这个“圈”称为这个点的 “最小圈” 。 定义 5:如果去掉了某一个“着色点”之后并不改变原图的“着 色数” ,那么称这点为“着色可省略点” 。 定理 4:如果一个图中仅有一个“圈”及圈内仅有一个点,且这 4 点与“圈上点”都分别相连则这个图的着色数:X(G)≤4。 证明:如图(1)ABCDE……的着色数 X(G)≤3(根据定理 1) 当再加上圈内一点 0 之后,由于 0 与圈上所有的点都相连,所以点 0 必须取与圈上的点颜色都不相同的另一种颜色。 故其着色数应再增加 一,故有 X(G)≤4。证明完。 图(1) 定理 5: 在平面图中增加一条连接原图中尚未连接的两点之间的 连线,则新图的着色数不小于原图的着色数。 证明: 假如这后来被连接的两点的原来的颜色是不相同的则连接 之后也不会改变原来的着色数。 假如这两点原来的着色是相同的, 则 此时有必要将其中的一个着色点改变为另一种颜色, 并对全图的着色 进行重新调整。 这时新图的着色数仍不会小于原图的着色数。 这是因 为假设新图的着色数小于原图的着色数, (反证法)设原图的着色数 为 N,则新图的着色数为 N-K,, (N、K 都是正整数且 KN) 。然后再将 新增加的那一条连线去掉之后,其它部分可完全采用新图的着色法, 也能满足邻点异色的要求。这说明原图的着色数本来就应该至多是 N-K。这与前面的假设原图的着色数为 N 相矛盾。因此新图的着色数 小于原图的着色数是不可能的。 所以在平面图中增加一条连接原图中 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 证明完 图(2) 定理 6 推论:一个仅有“圈上点”的图的着色数有 X(G)≤3 证明:在原图的基础上在圈内再增加若干条连线,使其成为“三 角剖分图”这样做之后不会减少原图的着色数(根据定理 5) 。所以 有 X(G 原)≤X(G 新) 。但增加了“连线”之后,新图的着色数 X(G 新)=3(根据定理 6) 。 故有 X(G 原)≤3 证明完。 6 定理 7:对于任何平面图有着色数:X(G)≤5(此定理在本文 证明四色定理时可以不利用, 但若利用此定理则在叙述本文的证明时 会更为方便些,此定理在各图论书中均有证明) 定理 8: 任何一个封闭的三维空间,只要它里面所有的封闭曲线 都可以收缩成一个点,这个空间就一定是一个三维圆球。 (庞加莱定 理) 定理 8 推论:在“球面”上挖一个“洞”就变成了拓扑学意义上 的“平面”了。在“球面”上挖二个“洞”就变成了拓扑学意义上的 “圆柱侧面”了。在“球面”上不论挖多少个“洞”都不会改变原来 “球面”上的“着色数” 。 证明:将有限“平面”的“四周”在空间向外收缩为一点,或将 “圆柱”的上下底面都收缩为一个点就也成了三维圆球的球面。 (庞 加莱定理)所以“平面” “圆柱侧面”等曲面在拓扑意义上就是“球 面”所以它们的“着色数”也一定相同。 (证明完) 三、四色定理的证明 四色定理:在球面或平面上对于任何平面图有 X(G)≤4 证明: (反证法) 假设四色定理不能成立, 即存在某平面图是必须用 5 种或 5 种以 上的颜色来着色。即有 X(G)≥5,不失一般性,可作一个任意复杂 的图,如图(3)(注:读者也可在此尝试选择其它任何形状的图) , 其中的实线部分表示全图的一个很小的局部图, 虚线 的大部份图形。 其复杂程度可以由读者任意构筑和想象, 但必须是 “有 限图”而不应该是“无限图” 。 图(3) 然后对此图作以下几个步骤的处理与分析: 第一步: 在保持原图的所有点与连线的基础下, 再将原图中尚未 相连但却能够相连的各点两两之间尽可能多地连接起来, (应注意不 再增加新的着色点, 而仅仅增加连线) 直至成为 “三角剖分图” 为止。 由前面定理 5 可知这样处理之后新图的着色数不会比原图减少, 这一 步称之为“添线” 。 第二步:任取图内某一个“圈内点”及围绕这点的“最小圈”进 行分析。
更多精彩尽在这里,详情点击:http://thecarrotcompany.com/,皇家贝蒂斯例如我们取的这个“圈内点”为 V 0,且在“添线”时我们 已经连接了 V 0与 V 4及 V 0与 V 5, 并且还连接了 V 3与 V 7 及 V 4与 V 8…已经 把原图变成了一个“三角剖分图”这时 V 0的“最小圈”就是 V 1—V 2— V 3—V 4—V 5—V 1。对于这个“局部图形”进行着色调整与分析。根据 定理 4,我们可以把 V 0的最小“点外圈”安排第一、第二、第三种颜 色进行着色。把 V 0安排为第四种颜色进行着色。若然后再给所有“圈 外的点”都着上颜色,由假设可知其“着色数”X(G)≧5,但由前 8 面的“公理 2”和“公理 3”可知“圈内点”与“圈外点”不可能直 达,故可以把 V 0这点的着色由原来安排的第四种颜色调整为第五种 颜色,再由定义 5 可知若这时把 V 0这点连同 V 0直接相连的所有连线 都去掉。皇家贝蒂斯这样做也并不会减少原图的“着色数”(因为 V 0这点是被 。 它的四周的“最小圈”阻断隔绝在圈内的,它与“圈外点”的着色是 无关的。如果说这样做减少了原图的着色数,例如“着色数”从五减 少为四,则说明原图的“着色数”本来就应该是四。 )这一步称之为 “去点”与“去线点是“着色可省略点” 。 ,而 V 0点既然 已经去掉,则与它直接相连的各条线,也就自然没有存在的必要了。 因为本文采用的是点着色的方法。 ) 第三步:反复对图中其它各“圈内点”作第一步的“添线”或第 二步的“去点”与“去线”(可交替或不交替地使用)直至对图中的 , 任何一点来说都再也没有“圈内点”可去了为止。最终使它成为一个 “三角剖分图” 。因为“点”在一个又一个地减少,且“圈内点”与 “圈外点”是相对而言的。所以最终的结果只能如图(1)或图(2) , 即得到只有一个 “圈” 且圈内只有一个点的图 (这时 “圈内点” “圈 与 上点”相连)或一个只有“圈上点”的“三角剖分图” 。但这时的“着 色数”X(G)≤4。这显然与开始的假设 X(G)≥5 相矛盾,所以一 开始的假设 X(G)≥5 是错误的。故在“球面”或“平面”上的着色 数有 X(G)≤4 成立。证明完。 为了便于读者更好地理解这一证明,读者可以多自选一些图形, 由简单到复杂,按照本文中所提供的方法(即证明中的三个步骤)进 9 行反复试验和思考,便能够悟出本证明其中的无比奥妙和正确性。 四、一个细节的说明 为了使读者更好地了解本文的思路,作一点补充说明。本文的主要 思路是围绕着“全图”中的“局部图”的“圈”及“圈内点” “圈外点”进行 , 分析与处理的。 “三角剖分”图中的“三角”实质上就是由三点构成的“圈” 。 如果图中出现由大于三点所构成的“圈” ,则可以通过“添线”的方法使其成为 “三角剖分图”然后再进行分析与处理。如果图中出现由二点构成的“圈”或 出现由一点构成的“圈” (例如出现一个区域包围了另一个区域的情况) ,前文 中虽然没有提及,但对于它的分析与处理方法与由三点所构成的“圈”可完全 相同。 参考文献: (1) 龚光鲁: 《有限数学引论》 ,第一版,上海科技出版社, 1986 年 5 月 288—343 页 (2) 江泽涵: 《多面形的欧拉定理和闭曲面的拓扑分类》第一 版,人民教育出版社 1979 年 1 月 32—42 页 (3) [美] F?哈拉里著: 《图论》 第一版 上海科技出版社 1980 年 1 月 145—166 页 (4) 王树禾编著《图论及其算法》 第一版 中国科技大学出 版社出版 1990 年 10 月 第一版 1994 年 8 月第二次印 刷 141—157 页

manbext

发表评论

电子邮件地址不会被公开。 必填项已用*标注