运筹学——.图与网络分析-最短路.ppt
《运筹学——.图与网络分析-最短路.ppt》由会员分享,可在线阅读,更多相关《运筹学——.图与网络分析-最短路.ppt(58页珍藏版)》请在咨信网上搜索。
1、 第6章 图与网络分析 图的基本概念与基本定理 树和最小支撑树 最短路问题 网络最大流本章内容重点引引 言言图论是应用非常广泛的运筹学分支,它已经广泛地应用于物理学控制论,信息论,工程技术,交通运输,经济管理,电子计算机等各项领域。对于科学研究,市场和社会生活中的许多问题,可以同图论的理论和方法来加以解决。例如,各种通信线路的架设,输油管道的铺设,铁路或者公路交通网络的合理布局等问题,都可以应用图论的方法,简便、快捷地加以解决。引引 言言随着科学技术的进步,特别是电子计算机技术的发展,图论的理论获得了更进一步的发展,应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述,可以解决许多工
2、程项目和管理决策的最优问题。因此,图论越来越受到工程技术人员和经营管理人员的重视。引引 言言 1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文,解决了著名的哥尼斯堡七座桥问题。德国的哥尼斯堡城有一条普雷格尔河,河中有两个岛屿,河的两岸和岛屿之间有七座桥相互连接,如图1a所示。引引 言言AB图1 aCD引引 言言 当地的居民热衷于这样一个问题,一个漫步者如何能够走过这七座桥,并且每座桥只能走过一次,最终回到原出发地。尽管试验者很多,但是都没有成功。为了寻找答案,1736年欧拉将这个问题抽象成图1b所示图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形,最终回到原点。欧拉在他的
3、论文中证明了这是不可能的,因为这个图形中每一个顶点都与奇数条边相连接,不可能将它一笔画出,这就是古典图论中的第一个著名问题。引引 言言图1 bACDB 在实际的生产和生活中,人们为了反映事物之间的关系,常常在纸上用点和线来画出各式各样的示意图。例:公路或铁路交通图、管网图、通讯联络图等各节点及联系的边。如果用点表示研究的对象,用边表示这些对象之间的联系,则图G可以定义为点和边的集合G=V,E式中:V点的集合,E边的集合 如果给图中的点和边赋以具体的含义和权数,如距离、费用、容量等这样的图称为网络图。1.1.图的基本概念与模型图的基本概念与模型 用点和点之间的线所构成的图,反映实际生产和生活中的
4、某些特定对象之间的特定关系。一般来说,通常用点表示研究对象用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下,图中的相对位置如何,点与点之间线的长短曲直,对于反映研究对象之间的关系,显得并不重要,因此,图论中的图与几何图,工程图等本质上是不同的。如图如图6-16-1所示:所示:端点,关联边,相邻环,多重边,简单图次,奇点,偶点,孤立点链,圈,路,回路,连通图完全图,偶图子图,部分图例12.2.树和最小支撑树树和最小支撑树树图(简称树,记作T(V,E)在各种各样的图中,有一类图是十分简单又非常具有应用价值的图,这就是树。性质1 任何树中必存在次为1的点。性质2 具有n个顶点的树的边数恰
5、好为 (n-1)条。性质3 任何具有n个点、(n-1)条边的连通 图是树图。2.1树的性质2.2 2.2 图的最小部分树图的最小部分树v如果G1是G2的部分图,则称G1是G2的部分树(或支撑树)。树图的各条边称为树枝(假定各边均有权重),一般图G2含有多个部分树,其中树枝总长最小的部分树,称为该图的最小部分树(也称最小支撑树)v定理1 图中任一个点i,若j是与i相邻点中距离最近的,则边i,j一定必含在该图的最小部分树内。v推论 把图的所有点分成V和 两个集合,则两集合之间连线的最短边一定含在最小部分树内。练习:写下图的树图v6v5v2v3v4v1v6v5v2v3v4v1练习练习v用破圈法求出下
6、图的一个树图。V V5 5V V4 4V V2 2V V3 3V V1 1e e6 6e e5 5e e4 4e e3 3e e2 2e e1 1e e7 7e e8 8 取一个圈(v1,v2,v3,v1),在一个圈中去 掉边e3。在剩下的图中,再取一个圈(v1,v2,v4,v3,v1),去掉边e4。再从圈(v3,v4 v5,v3)中去掉边e6。再从圈(v1,v2,v5,v4,v3,v1)中去掉边e7,这样,剩下的图不含圈,于是得到一个 支撑树,如下图所示。v v2 2e e1 1e e2 2e e5 5e e8 8v v1 1v v3 3v v4 42.3 避圈法和破圈法(1)避圈法v 从网
7、络图中依次寻找权数较小的边,寻找过程中,节点不得重复,即不得构成圈。注意在找较小权数边时不考虑已选过的边和可能造成圈的边。如此反复进行,直到得到最短树或证明网络不存在最短树。v在图中寻找最小部分树的步骤:P153(2)破圈法 在网络图中寻找一个圈。若不存在圈,则已经得到最短树或网络不存在最短树;去掉该圈中权数最大的边;反复重复 两步,直到最短树。练习:用破圈法求出下图的最小部分树图av6v5v2v3v4v1627535441v3v2v1v4v6v553142图b最短路问题最短路问题是网络理论中应用最广泛的问题之一。许多优化问题都可以使用这个模型,如设备更新、管道的铺设、线路的安排、厂区的布局等
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 网络分析 短路
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【1587****927】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【1587****927】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。