《ORnab图论》PPT课件

《《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图论基本概念一、名词术语图论中所考察的图不同于以往几何学与分析学中的图形，这里的图只考虑点与点之间由线连接的关系。至于画