北京理工大学：《运筹学》课程电子教案（PPT教学课件）第八章 图与网络分析

运等学课件 1 第八章 制作;北京理工大学吴祈宗等

运筹学课件 第八章 图与网络分析 制作：北京理工大学 吴祈宗等

第八章图与网络分析 本章内容重点 图的基本概念与基本定理 树和最小支撑树 最短路问题 网络系统最大流冋题 网络系统的最小费用最大流问题 中国邮递员问题

2 第八章 图与网络分析 图的基本概念与基本定理 树和最小支撑树 最短路问题 网络系统最大流问题 网络系统的最小费用最大流问题 中国邮递员问题 本章内容重点

引 图论应用非常广泛 控制论,信息论,工程技术,交 通运输,经济管理,电子计算机等领 城 科学研究,市场和社会生活中的 许多问题,可以用图论的理论和方法 来加以解决。 例如,通信线路的架设,输油管 道的铺设,铁路或者公路交通网络的 租而同

引 言 图论应用非常广泛： 控制论，信息论，工程技术，交 通运输，经济管理，电子计算机等领 域； 科学研究，市场和社会生活中的 许多问题，可以用图论的理论和方法 来加以解决。 例如，通信线路的架设，输油管 道的铺设，铁路或者公路交通网络的 合理布局

3引 将复杂的工程系统和管理问 题用图的理论加以描述,可以 解决许多工程项目和管理决策 的优化问题。 图论越来越受到工程技术 人员和经营管理人员的重视

4 引 言 将复杂的工程系统和管理问 题用图的理论加以描述，可以 解决许多工程项目和管理决策 的优化问题。 图论越来越受到工程技术 人员和经营管理人员的重视

引 1736年瑞士科学家欧拉发表 了关于图论方面的第一篇科学论文, 解决了著名的哥尼斯堡七座桥问题。 德国的哥尼斯堡城有一条普雷 格尔河,河中有两个岛屿,河的两 岸和岛屿之间有七座桥相互连接 如图8-1a所示

5 引 言 1736年瑞士科学家欧拉发表 了关于图论方面的第一篇科学论文， 解决了著名的哥尼斯堡七座桥问题。 德国的哥尼斯堡城有一条普雷 格尔河，河中有两个岛屿，河的两 岸和岛屿之间有七座桥相互连接， 如图8-1a所示

引 / A B a △ D 图8-1a)

引 言 A B 图8-1 a） C D

引 当地的居民热衷于这样一个问题 个漫步者如何能够走过这七座桥,并且每 座桥只能走过一次,最终回到原出发地。 尽管试验者很多,但是都没有成功。 为了寻找答案,1736年欧拉将这个问 题抽象成图8-1b所示图形的一笔画问题。 即能否从某一点开始不重复地一笔画出这 个图形,最终回到原点。欧拉在他的论文 中证明了这是不可能的,因为这个图形中 每一个顶点都与奇数条边相连接,不可能 将它一笔画出,这就是古典图论中的第 个著名问题

引 言 当地的居民热衷于这样一个问题， 一 个漫步者如何能够走过这七座桥，并且每 座桥只能走过一次，最终回到原出发地。 尽管试验者很多，但是都没有成功。 为了寻找答案，1736年欧拉将这个问 题抽象成图8-1b所示图形的一笔画问题。 即能否从某一点开始不重复地一笔画出这 个图形，最终回到原点。欧拉在他的论文 中证明了这是不可能的，因为这个图形中 每一个顶点都与奇数条边相连接，不可能 将它一笔画出，这就是古典图论中的第一 个著名问题

引 B 图8-1b)

8 引 言 图8-1 b） A C D B

1.图的基本概念与基本定理 在实际的生产和生活中,人们为了 反映事物之间的关系,常常在纸上用 点和线来画出各式各样的示意图。 例81:图8-2是我国北京、上海、重 庆等十四个城市之间的铁路交通图, 这里用点表示城市,用点与点之间的 线表示城市之间的铁路线。诸如此类 还有城市中的市政管道图,民用航空 线图等等

在实际的生产和生活中，人们为了 反映事物之间的关系，常常在纸上用 点和线来画出各式各样的示意图。 例8.1:图8-2是我国北京、上海、重 庆等十四个城市之间的铁路交通图， 这里用点表示城市，用点与点之间的 线表示城市之间的铁路线。诸如此类 还有城市中的市政管道图，民用航空 线图等等。 1.图的基本概念与基本定理

1图的基本概心与基本定理 北京 太原 天津 石家庄 塘沽 济南青岛 郑州 徐州连云港 重庆 武汉 南京 上海 图8-2

10 1.图的基本概念与基本定理 太原 重庆 武汉 南京 徐州 连云港 上海 郑州 石家庄 塘沽 济南 青岛 天津 北京 图8-2