基础运筹学教程（第三版）- 第五章-1 引论、图论基本概念 .ppt

*v1v2v3v4v5连通图v1v5v4v3v2v6连通图：图中任意两点之间均至少有一条通路，否则称为不连通图。*【定理4】设图G为一条简单链，则至多除始点与终点外，每一个中间点必为偶点。【证】设vk为任一中间点，因vk既为前邻边之终点，又为后邻边之始点，故若vk在链中出现n次，则得d(vk)=2n，此为偶数，即vk为偶点。*【推论】任何具有超过两个奇点的图G必不能一笔画成。【证】由定理3知，此时至少有4个奇点，若存在包含G中所有边的链，则此链中至少有两个中间点为奇点，由定理4知，它必非简单链。由于一笔画成等价于G为简单链，故G若有奇点，则必为2个，且这2个奇点必为简单链之始、终点。多于两个奇点之图不能作一笔画。*【例2】Euler的哥尼斯堡七桥问题，实质上是想对图5-2所示之G找出一个圈，使之能一笔画成。由于d(A)=d(C)=d(D)=3，d(B)=5，四个顶点均为奇点，故不可能一笔画成。从而，当地民众希冀的散步方案永远无法实现。CADB**第五章图论与网络优化*图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。*随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。这里，将对图论与网络优化的基本概念与理论作初步的介绍。需要指出的是，不同文献中所使用的图论术语与符号都不尽相同，缺乏统一的标准，因此，此处尽量使用较普遍的术语与符号。*§5-1引论§5-2图论基本概念§5-3树及其优化问题§5-4最短路问题§5-5最大流问题§5-6中国邮递员问题*§5-1引论图论的历史发展源远流长，其中，一些脍炙人口的著名问题及其研究对于这门学科的建立和发展无疑起了十分重要甚至是里程碑式的作用，如：七桥问题、四色问题、旅行商问题等等，有些难题遗留至今已数百年，仍未能解决。一、七桥问题追根溯源，图论的奠基人是瑞士数学家Euler，他于1736年（29岁时）发表了图论方面的第一篇论文，其中讨论了下述著名的七桥问题。*图5.1ABCD东普鲁士的哥尼斯堡城中，有一条普莱格尔河，河中有两个岛屿（奈佛夫岛），河上建有七座桥，将岛与两岸陆地相连（图5-1）。当地居民喜欢散步，并提出这样一个问题：若从岸或岛上任一处陆地出发，能否通过每座桥正好一次而回到原地。*（见图5.1）当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，1736年欧拉将这个问题抽象成图5.1b所示图形的一笔画问题。哥尼斯堡七桥问题图5.1aABCD*哥尼斯堡七桥问题可简化为以下图形其中的四个顶点都是奇顶点ABCD*CADB图5.2即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。Euler在其论文中否定了这个可能性，本质上的原因是图中每个点所关联的都是奇数条线，从而彻底解决了这个长期困惑全城民众的难题。*二、四色问题四色问题的提出来自英国，1852年，毕业于伦敦大学的格思里(FrancisGuthrie)来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜色。”这个结论能不能从数学上加以严格证明呢？他与在大学念书的弟弟决心试一试。兄弟二人为证明这一问题使用了一大叠稿纸，可研究工作没有任何进展。*1852年10月23日，他的弟弟拿这个问题请教他的老师、著名数学家德·摩尔根(AugustusdeMorgan)，摩尔根也没有能找到解决这个问题的途径，于是写信向自己的好友、著名数学家哈密尔顿爵士(SirWilliamHamilton)请教。但直到186