欢迎来到天天文库
浏览记录
ID:41359285
大小:2.76 MB
页数:183页
时间:2019-08-22
《《ORnab图论》PPT课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第五章:图论(graphtheory)教师:宁爱兵Email:nabnab@163.com1第五章:图论(graphtheory)1.简介2.图论基本概念3.树及其优化问题4.最短路问题目录7.练习题5.最大流问题6.最小费用最大流问题2简介图论是应用非常广泛的运筹学分支,它已经广泛地应用于物理学控制论,信息论,工程技术,交通运输,经济管理,电子计算机等各项领域。对于科学研究,市场和社会生活中的许多问题,可以同图论的理论和方法来加以解决。例如,各种通信线路的架设,输油管道的铺设,铁路或者公路交通网络的合理布局
2、等问题,都可以应用图论的方法,简便、快捷地加以解决。3随着科学技术的进步,特别是电子计算机技术的发展,图论的理论获得了更进一步的发展,应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述,可以解决许多工程项目和管理决策的最优问题。因此,图论越来越受到工程技术人员和经营管理人员的重视。。4这里,将对图论与网络优化的基本概念与理论作初步的介绍。需要指出的是,不同文献中所使用的图论术语与符号都不尽相同,缺乏统一的标准,因此,此处尽量使用较普遍的术语与符号。5哥尼斯堡七桥问题图5.1aABCD8(见图5.1
3、a)当地的居民热衷于这样一个问题,一个漫步者如何能够走过这七座桥,并且每座桥只能走过一次,最终回到原出发地。尽管试验者很多,但是都没有成功。为了寻找答案,1736年欧拉将这个问题抽象成图5.1b所示图形的一笔画问题。哥尼斯堡七桥问题图5.1aABCD9哥尼斯堡七桥问题可简化为以下图形其中的四个顶点都是奇顶点ABCD10CADB图5.1b11即能否从某一点开始不重复地一笔画出这个图形,最终回到原点。欧拉在他的论文中证明了这是不可能的,因为这个图形中每一个顶点都与奇数条边相连接,不可能将它一笔画出,这就是古典图论
4、中的第一个著名问题。Euler在其论文中否定了这个可能性,本质上的原因是图中每个点所关联的都是奇数条线,从而彻底解决了这个长期困惑全城民众的难题。12二、四色问题四色问题的提出来自英国,1852年,毕业于伦敦大学的格思里(FrancisGuthrie)来到一家科研单位搞地图着色工作时,发现了一种有趣的现象:“看来,每幅地图都可以用四种颜色着色,使得有共同边界的国家着上不同的颜色。”这个结论能不能从数学上加以严格证明呢?他与在大学念书的弟弟决心试一试。兄弟二人为证明这一问题使用了一大叠稿纸,可研究工作没有任何进
5、展。1852年10月23日,他的弟弟拿这个问题请教他的老师、著名数学家德·摩尔根(AugustusdeMorgan),摩尔根也没有能找到解决这个问题的途径,于是写信向自己的好友、著名数学家哈密尔顿爵士(SirWilliamHamilton)请教。但直到1865年哈密尔顿逝世为止,这个问题也没有得到解决。131878年6月13日,英国当时著名的数学家凯利(ArthurCayley)正式向伦敦数学学会提出这个问题,之后,四色猜想开始成了世界数学界关注的问题。许多一流的数学家纷纷加入研究,1879年,著名的律师兼数
6、学家肯普(AlfredBrayKempe)提交了证明四色猜想的论文,宣布证明了四色定理,大家都认为四色猜想从此解决了。11年后,即1890年,数学家赫伍德(PercyJohnHeawood)以自己的精确计算指出肯普的证明是错误的,但该方法经补救后可用来证明五色定理。后来,越来越多的数学家虽然对此绞尽脑汁,但一无所获。于是,人们开始认识到,这个貌似容易的题目,其实是一个可与费马(Fermat)猜想相媲美的难题。14进入20世纪以后,科学家们对四色猜想的证明基本上是按照肯普的想法在进行。美国数学家富兰克林(Fra
7、nklin)于1922年证明了25国以下的地图都可以用四色着色,1926年,结果推进到27国,1938年,推进到31国,1940年,推进到35国,1970年,推进到40国,随后又推进到了96国。后来,由于计算机性能的迅速提高,以及人机对话的出现,大大加快了四色猜想证明的进程。1976年6月,美国数学家阿佩尔(KennethAppel)与哈肯(WolfgangHaken)经过整整4年的紧张工作,在伊利诺斯大学的两台不同计算机上,花费了1200个小时,作了100亿个判断,终于完成了四色定理的证明。15四色猜想的计
8、算机证明,轰动了世界。它不仅解决了一个历时100多年的难题,而且有可能成为数学史上一系列新思维的起点。不过也有一些数学家并不满足于计算机取得的成就,他们仍在寻找着简捷明快的纯数学证明方法。1995年,中国学者李宏棋给出了一个数学证明,收录于《中国科学技术文库》数理科学和化学卷。16图论基本概念一、名词术语图论中所考察的图不同于以往几何学与分析学中的图形,这里的图只考虑点与点之间由线连接的关系。至于画
此文档下载收益归作者所有