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