运筹学8图与网络分析.ppt

第八章图与网络分析

0102030405

主要内容：8.1图的基8.2树和最8.3最短路8.4最小费用

本概念与基小支撑树问题流问题

本定理

06070809

8.5最大流问8.6网络计划8.7中国邮递8.7指派问题

题员问题

8.1图的基本概念与基本定理

图论是应用非常广泛的运筹学分支，它已

经广泛地应用于物理学控制论，信息论，

工程技术，交通运输，经济管理，电子计

算机等各项领域。对于科学研究，市场和

社会生活中的许多问题，可以同图论的理

论和方法来加以解决。例如，各种通信线

路的架设，输油管道的铺设，铁路或者公

路交通网络的合理布局等问题，都可以应

用图论的方法，简便、快捷地加以解决。

1

随着科学技术的进步，特别是电子计算机技术的发展，图论的

理论获得了更进一步的发展，应用更加广泛。如果将复杂的工

程系统和管理问题用图的理论加以描述，可以解决许多工程项

目和管理决策的最优问题。因此，图论越来越受到工程技术人

员和经营管理人员的重视。

2

关于图的第一篇论文是瑞士数学家欧拉（E.Euler）在1736年

发表的解决“哥尼

斯堡”七桥难题的论文；

德国的哥尼斯堡城有一条普雷格尔河，河中有两

个岛屿，河的两岸和岛屿之间有七座桥相互连接，

（见图8.1a）当地的居民热衷于这样一个问题，

一个漫步者如何能够走过这七座桥，并且每座桥

只能走过一次，最终回到原出发地。尽管试验者

很多，但是都没有成功。为了寻找答案，1736

年欧拉将这个问题抽象成图8.1b所示图形的一

笔画问题。

哥尼斯堡七桥问题

C

AB

D

图8.1a

哥尼斯堡七桥问题可简化为以下图形

其中的四个顶点都是奇顶点

A

B

C

D

图8.1b

C

AB

D

即能否从某一点开始不重最终回到原点。欧拉在他

01复地一笔画出这个图形，02的论文中证明了这是不可

能的，因为这个图形中每连接，不可能将它一笔画

03一个顶点都与奇数条边相04出，这就是古典图论中的

在实际的生产和生活中，

第一个著名问题。

0506人们为了反映事物

之间的关系，常常在纸上

的示意图。

07用点和线来画出各式各样08

北京

天津

太原