《离散数学课件》4二部、平面.ppt

  1. 1、本文档共34页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
《离散数学课件》4二部、平面

*/60 */60 四色猜想(四色问题) 在1852年,一个英国青年名叫盖思里(Francis Guthrie)提出:任何连通的平面图,可以用不多于4种颜色对每一个区域着色,使相邻区域着不同颜色。 1878~1880年两年间,数学家肯普和泰勒两人分别宣布证明了四色定理。后来,人们发现他们实际上证明了一个较弱的命题——五色定理。就是说对平面图着色,用五种颜色就够了。 1976年美国伊利诺州立大学的两位教授,阿佩尔(Kenneth Appel)和海肯(Wolfgang Haken)宣布,用计算机证明了这个问题。他们的证明需要对1900多种情况进行详尽的分析,在一台高速计算机上耗时超过1200小时。对数学家来说总还是希望能找到数学方法的证明。 */60 n色图 顶点着色:对一个图的每一个顶点着上一种颜色,使得相邻接的两个顶点着不同颜色。 定义 如果一个图至少需 n种颜色才能完成对顶点的着色就称这个图为 n色图, 记为 χ(G)=n */60 可k-着色的 是否可以把平面图的区域着色问题转化为平面图的顶点着色问题?答案是肯定的。 定义 一个图G称为可k-着色的(k-chromatic),如果可用k种颜色给G的所有顶点着色,使每个顶点着一种颜色,而同一边的两个端点着不同颜色。 */60 对偶图 设G是一个连通平面图。G已经被嵌入某一平面内,把平面分为n个区域f1,f2,…,fn,在每一个区域fi内取定一点ri代表这个区域,若ri和rj是两个区域,它们之间有若干条公共边,对每一条公共边我们连接ri和rj,并与这条公共边相交叉一条线(直线或曲线),有多少条公共边画多少条,这样我们得到一个新图记为G*,称为图G的对偶图。 从画法知, G和G*有相同的边数。 G G* 例 在本例中, G和G*同构。 一般地,未必同构。 */60 例 图9.21(p153) 注意图中的自环是怎样处理的(书上有错)。 */60 例 注意图中的一度顶点和自环是怎样处理的。 例 注意,当G1,G2为同构图的两种不同图示,那么它们的对偶图G1’与G2’不仅图示可能不同,而且可能是根本不同的图(不同构)。这就是说,一个图的对偶图未必是唯一的。 */60 对偶图的性质 图G的面与G*的顶点一一对应,且G中面的度(边界的长度)等于G*中对应顶点的度 。 G中两个面有公共边界,当且仅当G*中对应顶点之间有边关联。 G为平面图当且仅当G*为平面图。 对于图的面着色问题,可以通过研究其对偶图的顶点着色问题来解决。 V1={1,3,5,7} V2={2,4,5,8} 假设1在V1中, 则3在V2中. 那么4在哪里? 在连通的平面图中有一个关于顶点、边和面的数目的简单公式,名为欧拉(Enler)公式,因为欧拉首先对多面体的顶点和边所确定的平面图建立了这个公式。 K5: 5个顶点的完全图 K3,3 : 完全二部图 库拉托斯基定理虽然简单漂亮,但实现起来并不容易,特别是顶点数较多的时候,还有许多这方面的研究工作要做。 四色问题又称四色猜想,是世界近代三大数学难题之一。 四色问题的内容是:“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”用数学语言表示,即“将平面任意地细分为不相重迭的区域,每一个区域总可以用1,2,3,4这四个数字之一来标记,而不会使相邻的两个区域得到相同的数字。”(右图) 这里所指的相邻区域,是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点,就不叫相邻的。因为用相同的颜色给它们着色不会引起混淆。 四色猜想的提出来自英国。1852年,毕业于伦敦大学的弗南西斯·格思里来到一家科研单位搞地图着色工作时,发现了一种有趣的现象:“看来,每幅地图都可以用四种颜色着色,使得有共同边界的国家都被着上不同的颜色。”这个现象能不能从数学上加以严格证明呢?他和在大学读书的弟弟格里斯决心试一试。兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠,可是研究工作没有进展。 1852年10月23日,他的弟弟就这个问题的证明请教了他的老师、著名数学家德·摩尔根,摩尔根也没有能找到解决这个问题的途径,于是写信向自己的好友、著名数学家汉密尔顿爵士请教。汉密尔顿接到摩尔根的信后,对四色问题进行论证。但直到1865年汉密尔顿逝世为止,问题也没有能够解决。 1872年,英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题,于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。1878~1880年两年间,著名的律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文,宣布证明了四色定理,大家都认为四色猜想从此也就解决了。 肯普的

文档评论(0)

shuwkb + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档