第八章图与网络分析 本章内容重点 图的基本概念与基本定理 树和最小支撑树 最短路问题 网络系统最大流冋题 网络系统的最小费用最大流问题 中国邮递员问题
2 第八章 图与网络分析 图的基本概念与基本定理 树和最小支撑树 最短路问题 网络系统最大流问题 网络系统的最小费用最大流问题 中国邮递员问题 本章内容重点
引 图论是应用非常广泛的远筹学分支,它 已经广泛地应用于物理学控制论,信息论, 工程技术,交通运输,经济管理,电子计算 机等各项领域。对于科学研究,市场和社会 生活中的许多问题。可以同图论的理论和方 法来加以解决。例如,各种通信线路的架设 输油管道的铺设,铁路或者公路交通厕络的 合理布局等问题,都可以应用图论的方法, 便、快捷地加以解决
3 引 言 图论是应用非常广泛的运筹学分支,它 已经广泛地应用于物理学控制论,信息论, 工程技术,交通运输,经济管理,电子计算 机等各项领域。对于科学研究,市场和社会 生活中的许多问题,可以同图论的理论和方 法来加以解决。例如,各种通信线路的架设, 输油管道的铺设,铁路或者公路交通网络的 合理布局等问题,都可以应用图论的方法, 简便、快捷地加以解决
3引 随着科学技术的进步,特别是电子 计算机技术的发展。囹论的理论获得了 更进一步的发展,应用更加广泛。如果 将复杂的工程系统和管理问题用图的理 论加以描述。可以解决许多工程项目和 管理决策的最优问题。因此,图论越来 越受到工程技术人员和经营管理人员的 重视
4 引 言 随着科学技术的进步,特别是电子 计算机技术的发展,图论的理论获得了 更进一步的发展,应用更加广泛。如果 将复杂的工程系统和管理问题用图的理 论加以描述,可以解决许多工程项目和 管理决策的最优问题。因此,图论越来 越受到工程技术人员和经营管理人员的 重视
引 1736年瑞士科学家欧拉发表 了关于图论方面的第一篇科学论 文,解决了著名的哥尼斯堡七座 桥问题。德国的哥尼斯堡城有· 条普雷格尔河,河中有两个岛屿, 河的两岸和鸟屿之间有七座桥相 互连接,如图8.1a所示
5 引 言 1736年瑞士科学家欧拉发表 了关于图论方面的第一篇科学论 文,解决了著名的哥尼斯堡七座 桥问题。德国的哥尼斯堡城有一 条普雷格尔河,河中有两个岛屿, 河的两岸和岛屿之间有七座桥相 互连接,如图8.1a所示
引 言 当地的居民热衷于这样一个问题,一个漫 步者如何能够走过这七座桥。并且每座桥只能 走过一次,最终回到原出发地。尽管试验者很 多,但是都没有成功。 为了寻找答案,1736年欧拉将这个问题抽 象成图8.1b所示图形的一笔画问题。即能否从 某一点开始不重复地一笔画出这个图形。最终 回到原点。欧拉在他的论文中证明了这是不可 能的,因为这个图形中每一个顶点都与奇数条 边相连接,不可能将它一笔画出,这就是古典 图论中的第一个著名问题
7 引 言 当地的居民热衷于这样一个问题,一个漫 步者如何能够走过这七座桥,并且每座桥只能 走过一次,最终回到原出发地。尽管试验者很 多,但是都没有成功。 为了寻找答案,1736年欧拉将这个问题抽 象成图8.1b所示图形的一笔画问题。即能否从 某一点开始不重复地一笔画出这个图形,最终 回到原点。欧拉在他的论文中证明了这是不可 能的,因为这个图形中每一个顶点都与奇数条 边相连接,不可能将它一笔画出,这就是古典 图论中的第一个著名问题
1图的基本概念与基本定理 在实际的生产和生活中,人们为了反映 事物之间的关系,常常在纸上用点和线来画 出各式各样的示意图。 例8.1:图8.2是我国北京、上海、重庆等 十四个城市之间的铁路交通图,这里用点表 示城市,用点与点之间的线表示城市之间的 铁路线。诸如此类还有城市中的市政管道囹 民用航空线图等等
9 在实际的生产和生活中,人们为了反映 事物之间的关系,常常在纸上用点和线来画 出各式各样的示意图。 例8.1:图8.2是我国北京、上海、重庆等 十四个城市之间的铁路交通图,这里用点表 示城市,用点与点之间的线表示城市之间的 铁路线。诸如此类还有城市中的市政管道图, 民用航空线图等等。 1.图的基本概念与基本定理