图论方法.ppt
《图论方法.ppt》由会员分享,可在线阅读,更多相关《图论方法.ppt(85页珍藏版)》请在咨信网上搜索。
1、 引言 图论(Graph Theory)是专门研究图的理论的一门数学分支,属于离散数学范畴,与运筹学有交叉,它有200多年历史,大体可划分为三个阶段:第一阶段是从十八世纪中叶到十九世纪中叶,处于萌芽阶段,多数问题围游戏而产生,最有代表性的工作是所谓的Euler七桥问题,即一笔画问题。第二阶段是从十九世纪中叶到二十世纪中叶,这时,图论问题大量出现,如Hamilton问题,地图染色的四色问题以及可平面性问题等,这时,也出现用图解决实际问题,如Cayley把树应用于化学领域,Kirchhoff用树去研究电网络等.第三阶段是二十世纪中叶以后,由生产管理、军事、交通、运输、计算机网络等方面提出实际问题,
2、以及大型计算机使大规模问题的求解成为可能,特别是以Ford和Fulkerson建立的网络流理论,与线性规划、动态规划等优化理论和方法相互渗透,促进了图论对实际问题的应用。BACDl哥尼斯堡七桥问题哥尼斯堡七桥问题(Knigsberg Bridge Problem)lLeonhard Euler(1707-1783)在在1736年发表第一篇图论方面年发表第一篇图论方面的论文,奠基了图论中的一些基本定理的论文,奠基了图论中的一些基本定理.l很多问题都可以用点和线来表示,一般点表示实体,线表示很多问题都可以用点和线来表示,一般点表示实体,线表示实体间的关联实体间的关联例例6.16.1:哥尼斯堡七桥问
3、题:哥尼斯堡七桥问题1 1 图与网络的基本概念图与网络的基本概念l一般研究无向图l树图:倒置的树,根(root)在上,树叶(leaf)在下l多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图 2 最小支撑树最小支撑树(生成树生成树)一一 树的定义及其性质树的定义及其性质l无圈连通图称为树无圈连通图称为树(treetree),记为记为T T 树的性质:树的性质:l任何树必存在次数为任何树必存在次数为 1 1 的点的点l具有具有 n n 个节点的树个节点的树 T T 的边恰好为的边恰好为 n n 1 1 条,反之,任何有条,反之,任何有n n 个节点,个节点,n n 1
4、1 条边的连通图必是一棵树条边的连通图必是一棵树图的生成树图的生成树:若图若图G G的一个支撑图的一个支撑图T T是一棵树是一棵树,则称则称T T是是G G的一棵的一棵生成树生成树(spanning treespanning tree).).在赋权图在赋权图G G中,一棵生成树所有边上权的和,称为生成树的权。中,一棵生成树所有边上权的和,称为生成树的权。具有最小权的生成树,称为具有最小权的生成树,称为最小树最小树(或最优树)(或最优树),求最小树有求最小树有破圈破圈法法和和避圈法避圈法.定理 图 G有生成树的充分必要条件为图是连通图。定义(最优树)在赋权图G中,一棵生成树所有树柱上权的和,称为
5、生成树的权。具有最小权的生成树,称为最优树(或最小树)。求最小树的方法有破圈法和避圈法。3 最小枝杈树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636例例10-7破圈法破圈法v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v
6、5v6v6202015159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323v1v1v7v7v4v4v3v
7、3v2v2v5v5v6v69 93 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 317174 41 12323总造价总造价=1+4+9+3+17+23=57v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636避圈法避圈法v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41
8、 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1
9、v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636总造价总造价=1+4+9+3+17+23=574:最短路问题最短路问题是网络理论中应用最广泛的问题之一。许多优化问题都可以使用这个模型,如设备更新、管道的铺设、线路的安排、厂区的布局等。最短路问题的一般提法是:设 为连通图,图中各边 有权 (表示 ,之间没有边),为图中任意两点,求一条道路 ,使它是从 到 的所有路中总权最小的路。即:最小。最短路算法中1959年由 (狄克斯特洛)提出的算法被公认为是目前最好的方法,我们称之为 算法。下面通过例子来说明此法的
10、基本思想。条件:所有的权数 思路:逐步探寻。下求 到 的最短路:1)从 出发,向 走。首先,从 到 的距离为0,给 标号(0)。画第一个弧。(表明已 标号,或已走出 )从 出发,只有两条路可走 ,其距离为2)可能最短路为 给 划成粗线。划第二个弧。给 标号(4)。表明走出 后走向 的最短路目前看是 ,最优距离是4。现已考察完毕第二个圈内的路,或者说,已完成 的标号。3)接着往下考察,有三条路可走:可选择的最短路为 给 划成粗线。划第3个弧。给 标号(6)。4)接着往下考察,有四条路可走:可选择的最短路为 给 划成粗线。划第4个弧。给 标号(8)。5)接着往下考察,有四条路可走:可选择的最短路为
11、 给 划成粗线。划第5个弧。给 标号(9)。6)接着往下考察,有四条路可走:可选择的最短路为 给 划成粗线。划第6个弧。给 标号(13)。7)接着往下考察,有四条路可走:可选择的最短路为 同时给 划成粗线。分别给 标号(14)。最后,从 逆寻粗线到 ,得最短路:长度为15。例例例例5-3 5-3 用狄克斯拉算法用狄克斯拉算法用狄克斯拉算法用狄克斯拉算法求解图求解图求解图求解图5-15-1所示最短路问题。所示最短路问题。所示最短路问题。所示最短路问题。4v1v2v3v4v6v5v722561413412图图5-1 例例5-3网络图网络图解:先将图解:先将图解:先将图解:先将图5-15-1的网络用
12、矩阵形式表示出来的网络用矩阵形式表示出来的网络用矩阵形式表示出来的网络用矩阵形式表示出来:步骤步骤 考察点考察点 T标号点集标号点集 标标 号(号(表表P标号)标号)1v1v2,v7v1 v2 v3 v4 v5 v6 v7 0 -0+20+5 2 5 -23456v2v3v4v5v6v3,v7v4,v7v5,v6,v7v5,v72+22+42+6 4 6 8 -4+14+3 5 8 7 -5+45+1 5+4 8 6 96+2 8 8v78+18反向追踪,得到最优路线:反向追踪,得到最优路线:v1 v2 v3 v4 v6 v7v5讨讨论论:若若先先把把v7的的标标号号改改为为永永久久性性标标号
13、号,该怎麽继续作下去?该怎麽继续作下去?56v6v7v5,v7v5v1 v2 v3 v4 v5 v6 v7 6+2 8 8 8+18 8 6 9反向追踪,得到相同的最优路线。反向追踪,得到相同的最优路线。反向追踪,得到相同的最优路线。反向追踪,得到相同的最优路线。在在在在得得得得到到到到从从从从起起起起点点点点到到到到终终终终点点点点的的的的最最最最短短短短路路路路长长长长的的的的同同同同时时时时,还还还还能得到什麽附加信息能得到什麽附加信息能得到什麽附加信息能得到什麽附加信息?(5)D氏标号法(氏标号法(Dijkstra)的特点的特点(获得的附加信息):(获得的附加信息):能能得得到到从从
14、(起起点点)到到各各点点的的最最短短路线和最短路长。路线和最短路长。第二讲:最短路问题的两个应用最短路问题在图论应用中处于很重要的地位,下面举两个实 际应用的例子。例 设备更新问题某工厂使用一台设备,每年年初工厂要作出决定:继续使 用,购买新的?如果继续使用旧的,要负维修费;若要购买 一套新的,要负购买费。试确定一个5年计划,使总支出最小若已知设备在各年的购买费,及不同机器役龄时的残值与维修费,如表所示.项目第1年第2年第3年第4年第5年购买费1112131414机器役龄0-11-22-33-44-5维修费5681118残值43210表8-2解:把这个问题化为最短路问题。用点 表示第i年初购进
15、一台新设备,虚设一个点 ,表示第5年底。边 表示第i年购进的设备一直使用到第j年初(即第j-1年底)。边 上的数字表示第i年初购进设备,一直使用到第j年初所需支付的购买费、维修的全部费用(可由表8-2计算得到)。这样设备更新问题就变为:求从 到 的最短路问题.给 划成彩线。给 划成彩线。给 划成彩线。给 划成彩线。给 划成彩线。计算结果:最短路最短路路长为49。即:在第一年、第三年初各购买一台新设备为最优决策。这时5年的总费用为49。例13(选址问题)已知某地区的交通网络如图所示,其中点代表居民小区,边代表公路,为小区间公路距离,问区中心医院应建在哪个小区,可使离医院最远的小区居民就诊时所走的
16、路程最近?解 求中心的问题。解决方法:先求出 到其它各点的最短路长如再求即为所求。比如求 给 划成彩线。给 划成彩线。给 标号20。给 划成彩线。给 标号30。分别给 划成彩线。分别给 标号33。给 划成彩线。给 标号63。其它计算结果见下表:小区号0 30 50 63 93 45 609330 0 20 33 63 15 306350 20 0 20 50 25 405063 33 20 0 30 18 336393 63 50 30 0 48 639345 15 25 18 48 0 154860 30 40 33 63 15 063表 8.1由于 最小,所以医院应建在 ,此时离医院最远的
17、小区 距离为48。一 概念l网路流一般在有向图上讨论,弧的方向为流的方向l定义网路上支路的容量为其最大通过能力,记为 rij,支路上的实际流量记为 xij,网络流为所有通过弧的流量的集合.l图中规定一个发点s,一个收点tl节点没有容量限制,流在节点不会存储4 4 最大流问题最大流问题可行流可行流满足以下条件的流称为可行流:满足以下条件的流称为可行流:1 1、每一个节点流量平衡、每一个节点流量平衡(流进流进=流出流出)2 2、00 x xijij u uijij(容量限制容量限制)总流量最大的可行流为总流量最大的可行流为最大流最大流链的前向弧链的前向弧,后向弧后向弧l是网络是网络G G中一条从始
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。