中国高校课件下载中心 》 教学资源 》 大学文库

《运筹学》课程教学资源(试卷习题)第8章 图与网络分析

文档信息
资源类别:文库
文档格式:PPT
文档页数:167
文件大小:1.85MB
团购合买:点击进入团购
内容简介
§8.1 图的基本概念与基本定理 §8.2 树和最小支撑树 §8.3 最短路问题 §8.4 最小费用流问题 §8.5 最大流问题 §8.6 网络计划 §8.7 中国邮递员问题 §8.7 指派问题
刷新页面文档预览

第八章图与网络分析主要内容:88.1图的基本概念与基本定理S8.2树和最小支撑树S8.3最短路问题88.4最小费用流问题88.5最大流问题88.6网络计划88.7中国邮递员问题88.7指派问题

第八章 图与网络分析 主要内容: §8.1 图的基本概念与基本定理 §8.2 树和最小支撑树 §8.3 最短路问题 §8.4最小费用流问题 §8.5最大流问题 §8.6网络计划 §8.7中国邮递员问题 §8.7指派问题

$ 8.11图的基本概念与基本定理图论是应用非常广泛的运筹学分支,它已经广泛地应用于物理学控制论,信息论,工程技术,交通运输,经济管理,电子计算机等各项领域。对于科学研究,市场和社会生活中的许多问题,可以同图论的理论和方法来加以解决。例如,各种通信线路的架设,输油管道的铺设,铁路或者公路交通网络的合理布局等问题,都可以应用图论的方法简便、快捷地加以解决

§8.1 图的基本概念与基本定理 图论是应用非常广泛的运筹学分支,它 已经广泛地应用于物理学控制论,信息论, 工程技术,交通运输,经济管理,电子计算 机等各项领域。对于科学研究,市场和社会 生活中的许多问题,可以同图论的理论和方 法来加以解决。例如,各种通信线路的架设, 输油管道的铺设,铁路或者公路交通网络的 合理布局等问题,都可以应用图论的方法, 简便、快捷地加以解决

随着科学技术的进步,特别是电子计算机技术的发展,图论的理论获得了更进一步的发展,应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述,可以解决许多工程项目和管理决策的最优问题。因此,图论越来越受到工程技术人员和经营管理人员的重视,关于图的第一篇论文是瑞士数学家欧拉(E.Euler)在1736年发表的解决“哥尼

随着科学技术的进步,特别是电子计 算机技术的发展,图论的理论获得了更进 一步的发展,应用更加广泛。如果将复杂 的工程系统和管理问题用图的理论加以描 述,可以解决许多工程项目和管理决策的 最优问题。因此,图论越来越受到工程技 术人员和经营管理人员的重视。 关于图的第一篇论文是瑞士数学家欧拉 (E. Euler)在1736年发表的解决“哥尼

斯堡”七桥难题的论文;德国的哥尼斯堡城有一条普雷格尔河,河中有两个岛屿,河的两岸和岛屿之间有七座桥相互连接,(见图8.1a)当地的居民热裹于这样一个问题,一个漫步者如何能够走过这七座桥,并且每座桥只能走过一次,最终回到原出发地。尽管试验者很多,但是都没有成功。为了寻找答案,1736年欧拉将这个问题抽象成图8.1b所示图形的一笔画问题

斯堡” 七桥难题的论文; 德国的哥尼斯堡城有一条普雷格尔河, 河中有两个岛屿,河的两岸和岛屿之间有七 座桥相互连接,(见图8.1 a)当地的居民热 衷于这样一个问题,一个漫步者如何能够走 过这七座桥,并且每座桥只能走过一次,最 终回到原出发地。尽管试验者很多,但是都 没有成功。为了寻找答案,1736年欧拉将这 个问题抽象成图8.1b所示图形的一笔画问题

哥尼斯堡七桥问题二D图 8.1a

哥尼斯堡七桥问题 图 8.1 a A B C D

哥尼斯堡七桥问题可简化为以下图形其中的四个顶点都是奇顶点AD

哥尼斯堡七桥问题可简化为以下图形 其中的四个顶点都是奇顶点 A B C D

CADD图8. 1 b

C A D B 图8.1 b

即能否从某一点开始不重复地一笔画出这个图形,最终回到原点。欧拉在他的论文中证明了这是不可能的,因为这个图形中每一个顶点都与奇数条边相连接,不可能将它一笔画出,这就是古典图论中的第一个著名问题。在实际的生产和生活中,人们为了反映事物之间的关系,常常在纸上用点和线来画出各式各样的示意图

即能否从某一点开始不重复地一笔画出这个图形, 最终回到原点。欧拉在他的论文中证明了这是不可 能的,因为这个图形中每一个顶点都与奇数条边相 连接,不可能将它一笔画出,这就是古典图论中的 第一个著名问题。 在实际的生产和生活中,人们为了反映事物 之间的关系,常常在纸上用点和线来画出各式各样 的示意图

例8.1图8.2是我国北京、上海、重庆等十四个城市之间的铁路交通图,这里用点表示城市,用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图,民用航空线图等等。北京天津太原石家庄塘沽济南青岛郑州徐州连云港图8.2重庆武汉南京上海福

例8.1 图8.2是我国北京、上海、重庆等 十四个城市之间的铁路交通图,这里用点 表示城市,用点与点之间的线表示城市之 间的铁路线。诸如此类还有城市中的市政 管道图,民用航空线图等等。 太原 石家庄 北京 天津 塘沽 济南 青岛 徐州 连云港 南京 上海 郑州 重庆 武汉 图8.2

例8.2有六支球队进行足球比赛,我们分别用点v1,…,v表示这六支球队,它们之间的比赛情况,也可以用图反映出来已知,队战胜v2 队,z队战胜队,V队战胜队,如此等等。这个胜负情况,可以用图8.3所示的有向图反映出来

例8.2 有六支球队进行足球比赛,我 们分别用点v1 ,.,v6表示这六支球队,它 们之间的比赛情况,也可以用图反映出来, 已知v1队战胜v2 队,v2 队战胜v3 队,v3 队 战胜v5队,如此等等。这个胜负情况,可以 用图8.3所示的有向图反映出来

刷新页面下载完整文档
VIP每日下载上限内不扣除下载券和下载次数;
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
相关文档