搜索

五色定理的证明

gecimao 发表于 2019-06-18 22:03 | 查看: | 回复:

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

  五色定理是图论中的一个结论:将一个平面分成若干区域,给这些区域染色,且保证任意相邻区域没有相同颜色,那么所需颜色不超过五种。五色定理是比四色定理弱的定理,但是比四色定理更容易证明。1879年,阿尔弗雷德·布雷·肯普给出了四色定理的一个证明,当时为人所接受,但11年后,珀西·约翰·希伍德却发现了肯普的证明中存在错误,他把肯普的证明加以修改,得到了五色定理。

  设图G=(V,E),其中V={v,v1,v2……},且G为简单无向平面图。

  当deg(v0)=5时,如图所示,根据Jordan曲线不可能同时邻接,否则将会破坏图的平面性。不妨假设v1和v3不邻接。我们将v1 ,v0,v3这三点沿着边(v1 ,v0),(v0,v3)进行收缩。得到另一个图G’, 由于这一收缩是连续性变化,因而不会改变图的平面性,即图G’仍是平面图(如图2所示)。

  很明显图G’的顶点个数少于n,于是根据上述归纳可知G’可以用五种颜色:c1,c2,c3,

  c4,c5进行着色。我们不凡假设v2用c2,v5用c5, v4用c4,那个收缩后的点用c1……

  那么我们可以对图G 进行这样的着色,除了v0,v1,v3这些顶点以外其余顶点的着色方案和图G’完全相同。对于v1,v3我们用c1 即可,这样一来在图G中v1,v3用c1,而v2用c2,

  v4用c4,v5用c5,那么剩下的c3便图在顶点v0上,于是图G可用五种颜色进行着色。

  设图G=(V,E),其中V={v,v1,v2……},且G为简单无向平面图。 这里图G有n个顶点,且n3。那么由欧拉定理的推论可知,平面图G中至少有一个顶点其度数不超过5。不妨假设这一顶点就是v0。 我们用数学归纳法 当n=4,5时定理显然成立。 当deg(v0)=3,4时定理显然成立。 当deg(v0)=5时,如图所示,根据Jordan曲线不可能同时邻接,否则将会破坏图的平面性。不妨假设v1和v3不邻接。我们将v1 ,v0,v3这三点沿着边(v1 ,v0),(v0,v3)进行收缩。得到另一个图G’, 由于这一收缩是连续性变化,因而不会改变图的平面性,即图G’仍是平面图(如图2所示)。 很明显图G’的顶点个数少于n,于是根据上述归纳可知G’可以用五种颜色:c1,c2,c3,c4,c5进行着色。我们不凡假设v2用c2,v5用c5, v4用c4,那个收缩后的点用c1…… 那么我们可以对图G 进行这样的着色,除了v0,v1,v3这些顶点以外其余顶点的着色方案和图G’完全相同。对于v1,v3我们用c1 即可,这样一来在图G中v1,v3用c1,而v2用c2, v4用c4,v5用c5,那么剩下的c3便图在顶点v0上,于是图G可用五种颜色进行着色。根据归纳原理可知对于所有平面图五色定理都是成立的

  为什么 一张地图,无论有多少个国家只需4种颜色就能区分...

本文链接:http://saskatoonflowers.net/dinglizhengmingqi/545.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部