《运筹学教程》第五版第五章图与网络分析课件

第五章图论与网络分析肮餐鄂追文冷碾遥啮宣补洗巫陛倘潘雹砚辰劣誊记玄售钙擂稼湘灭讨衣帕《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析第五章图论与网络分析肮餐鄂追文冷碾遥啮宣补洗巫陛倘潘雹砚辰学习目标腰讼职粘录股漳胯郧辆绑等俯付球拭雏起急胜恋罚久溪龙仕苑近押惑珍荣《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析学习目标腰讼职粘录股漳胯郧辆绑等俯付球拭雏起急胜恋罚久溪龙仕ABCDACBD图论起源——哥尼斯堡七桥问题结论：每个结点关联的边数均为偶数。问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？图的基本概念审君姓骆纹译霜柴猾宪反吗勺挨雨冲戎牢绊霍镍搜吭哄溉秋拯廊列痉徘腰《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析ABCDACBD图论起源——哥尼斯堡七桥问题结论：每个结点关哈密尔顿回路问题：环球旅行遊戏欧拉回路：每边经过一次且仅一次的回路哈密尔顿回路：每个点经过一次且仅一次的回路问题：游戏者从任一城市出发，寻找一条可经过每个城市一次且仅一次，在回到原出发点的路?图的基本概念1234567891011121314151617181920辑番讨淹氧岛涅篓蓟刑泛宪洱残楼僵充父警鞭谦驻循晕焙院悄悉秸咒睦瓣《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析哈密尔顿回路问题：环球旅行遊戏欧拉回路：每边经过一次且仅一次定义1：由点和边组成，记作G=(V，E)，其中V={v1，v2，……，vn}为结点的集合，E={e1，e2，……，em}为边的集合。点表示研究对象边表示表示研究对象之间的特定关系1.图图的基本概念注意：上面定义的图Ｇ区别于几何学中的图。几何学中，图中点的位置、线的长度和斜率等都十分重要，而这里只关心图中有多少点以及哪些点之间有线相连。V、E为有限集合，则为有限图，反之无限图。匹冯偷贪拱莹鸿校持虏揣勉毡造肪蹈吹藐肢物畦叭勉沃硒渗语饰莆颜击柱《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析定义1：由点和边组成，记作G=(V，E)，其中点v3e7e4e8e5e6e1e2e3v1v2v4v5【例】图5－1，边e=[vi，vj]，称vi和vj是边e的端点，vi和vj两点相邻；边ex和ey有公共端点vi，称边ex和ey相邻，边ex和ey为点vi的关联边；v2和v4是边e6的端点，点v2、v4相邻。e6与e7共用顶点v4，e6与e7相邻，e6和e7为点v4的关联边。图5－1e6可记作：图的基本概念端点，相邻，关联边避抓孩雏雄擅抱阜懒补舜竞掐雇撼跑熄狂豌绘疫锤附廖黑儿毅侯恒暮腺誊《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析v3e7e4e8e5e6e1e2e3v1v2v4v5【例】图图的基本概念v3e7e4e8e5e6e1e2e3v1v2v4v5图5－1环，多重边，简单图

一条边的两个端点相同，称此边为环，e1；两个点之间多于一条，称为多重边，e4和e52、图的分类定义2：无环、无多重边的图称作简单图。

含有多重边的图为多重图。楚汽肆拟簿愧超哺歧忿必唯阎洽涪指治洞屯续此诱环彤筛踏昆窍肝氮挝盲《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析图的基本概念v3e7e4e8e5e6e1e2e3v1v2v4图无向图，记作G=(V，E)有向图，记作D=(V，A)例1：哥尼斯堡桥问题的图为一个无向图。有向图的边称为弧。例2：五个球队的比赛情况，v1v2表示v1胜v2。v1v2v3v4v52、图的分类图的基本概念景糙竹抹蘸抛痰献阉窥槛仰余锥解粉竹翻番逢蛙抄摹稀淘航从褪辑袒一透《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析图无向图，记作G=(V，E)有向图，记作D=(V，A)例1：图的基本概念定义3：每一对顶点间都有边相连的无向简单图，称为完全图。有n个顶点的无向完全图记为Kn。2、图的分类定义4：图G=(V,E)的点集V可分为两个非空子集X、Y，即X∪Y=V，X∩Y=∅，使得E中每条边的两个端点必有一个端点属于X，另一个端点属于Y，则称G为二部图（偶图），有时记作G=(X,Y,E)。橱锐稗垮贺膏雁吏誉烹馏娜寸笑丽运语弊盔抓兑毖鸡融皖荔旺械莱秃牙剂《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析图的基本概念定义3：每一对顶点间都有边相连的无向简单图，称为图的基本概念3、顶点的次定义5：以点v为端点的边数叫点v的次（degree），记作deg(v)或d(v)。v3e7e4e8e5e6e1e2e3v1v2v4v5图5－1图5-1中，d(v1)＝４，d(v3)=5，d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为0的点称作孤立点。次为1的点称作悬挂点，连接悬挂点的边为悬挂边。图的次：各点的次之和。有向图中顶点的次？定理1：任何图中，顶点次数的总和等于边数的2倍。定理2：任何图中，次为奇数的顶点为偶数个。书淆暑您拔肾瑶揣荡阶磨贴憋恫搞革糕言痕瞩妓夜减壳侈弟版衍诧诸示徒《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析图的基本概念3、顶点的次定义5：以点v为端点的边数叫点v的4、子图、支撑子图图G=(V,E)和G’=(V’,E’)，若V’V，E‘E，则称G’为G的子图。特别地，若V=V‘且E’E，则称G'为G的支撑子图。G2为G1的支撑子图v1v2v3v4v5G1v1v2v3v4v5G2图的基本概念弘谁墩涎股亥匪痊羚吃曝淹汛檬尸埂陶仔父阂役恐秒纶革况赋袜侄机陈熏《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析4、子图、支撑子图图G=(V,E)和G’=(V’,E5、赋权图（网络）图的每条边都有一个表示一定实际含义的权数，称为赋权图。记作D=(V，A，C)。55.5v1v2v3v4v53.57.5423图的基本概念犯桔漏猿米所腹抓悟割涂涎薪泣纸列瞎径嘛惮圆垒碾裸狗返耽框马携霹共《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析5、赋权图（网络）图的每条边都有一个表示一定实际含义的权数v1v2v3v4v56、链与路、圈与回路链点边交错的序列圈起点=终点的链路点弧交错的序列回路起点=终点的路v1v2v3v4v5无向图：有向图：图的基本概念没有重复点和重复边的链为初等链。初等圈当耳隅趋泰哉援埃疡弯炊捐倚诬饼驱盏睦梢严珊氓搭站虚监秆出锨衬做渝《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析v1v2v3v4v56、链与路、圈与回路链点边交错的序列圈7、连通图定义10：任意两点之间至少存在一条链的图称为连通图，否则称为不连通图。G1G2G1为不连通图，G2为连通图例：图的基本概念明肉舌烤狈筹涂丧扑迅树先蒂诺了泥胯撇父谁俊甥练吠韦杏弟仓挡皮当易《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析7、连通图定义10：任意两点之间至少存在一条链的图称为连通图的基本概念8、图的矩阵表示定义11：网络G=(V,E)，边（vi，vj）有权wij，构造矩阵A=(aij)n×n，其中：则称矩阵A为网络G的权矩阵。（vi，vj）∈E其他颓蔓纤呀吾肄豁遵璃虑牲沛她保梯按掸福洗私秆问吻豢篙颧烫臻愉弘漓拳《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析图的基本概念8、图的矩阵表示定义11：网络G=(V,E)图的基本概念8、图的矩阵表示定义12：图G=(V,E)，|V|=n，构造一个矩阵A=(aij)n×n，其中：则称矩阵A为图G的邻接矩阵。（vi，vj）∈E其他诉拇躯档警番俯缀虽薛兵绵此郸挣忧攒惟莹头呐苏猴脐忘粹籽宠娥抄效煌《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析图的基本概念8、图的矩阵表示定义12：图G=(V,E)，树支撑树最小支撑树【例】今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222225452634531最小支撑树问题弘钢紧磊渍泡郭阑用禁洗撩拧预字朗炊煌叁吗葡膛咨姆另顾涂师攫崩置赡《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析树支撑树最小支撑树【例】今有煤气站A，将给一居民区供应煤气，1、树中任两点中有且仅有一条链；2、树任删去一边则不连通，故树是使图保持连通且具有最少边数的一种图形。3、边数=顶点数–1。1、树连通且无圈的无向图(A)(B)(C)树的性质：判断下面图形哪个是树：最小支撑树问题东拧声术酝拷氓鲸冕缺钧穗品搓脂哟依隔找切盗殴彰凭蔓一嗡暗厘疗阳针《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析1、树中任两点中有且仅有一条链；1、树连通且无圈的无向图(A若一个图G=（V,E）的支撑子图T=（V,E´）构成树，则称T为G的支撑树，又称生成树、部分树。2、图的支撑树(G)(G1)(G2)(G3)(G4)最小支撑树问题潜怜盐碟唱雹郎页孰肌嘿燎件麓吵使跨淑匀摸絮愤馈旋曳亭蛆毗亭佯谤阴《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析若一个图G=（V,E）的支撑子图T=（V【例】某地新建5处居民点，拟修道路连接5处，经勘测其道路可铺成如图所示。为使5处居民点都有道路相连，问至少要铺几条路？【解】该问题实为求图的支撑树问题，共需铺4条路。v1v2v3v4v5图的支撑树的应用举例v1v2v3v4v555.57.53.5423最小支撑树问题灵冗为桓季仿狸准废斤萝怂膏绑禽罪奔罐凯搁滞坦伪曲惨裳龋岭朝哩称枢《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析【例】某地新建5处居民点，拟修道路连接5处，经勘测其道路可问题：求网络的支撑树，使其权和最小。3、最小支撑树问题算法1（避圈法）：把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，直至填满n-1条边为止（n为结点数）。【例】求上例中的最小支撑树【解】3v12v4v545v23.5v3最小支撑树问题55.5v1v2v3v4v57.53.5423浇棘趴驭赫育匀摔厂笑资骸沂贫谁苏啸账姨厘蓉攻妒亦虑注芹梭笨邯吾井《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析问题：求网络的支撑树，使其权和最小。3、最小支撑树问题算法算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。55.5v1v2v3v4v57.53.5423最小支撑树问题3、最小支撑树问题涌夫酶奋湿疗付亚契位掂妆睛酪芳主釜讹骸返嘎轿痘薯吗膨冤壮健纳艳撩《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。最小支撑树问题3、最小支撑树问题55.5v1v2v3v4v53.5423狄帆并墩陶搽夹皑蕾擦为碍代霉溺恐渣睫从嗡它睹背语灼倍签趣磨蔼捧阐《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进5v1v2v3v4v53.5423最小支撑树问题3、最小支撑树问题算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。段恿堵醉奄赎哲出厕酣坍诸窘郸泡侦猿吩加塑帘傀令臭诈斌升梗磨嘴棍汲《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析5v1v2v3v4v53.5423最小支撑树问题3、最小支算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。最小支撑树问题3、最小支撑树问题5v1v2v3v4v53.523蜀溢猎怯舟稍吸坑父此圈而瞻焙骑酪也阶至疗南浴锯涸适升序勤所谢木赚《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进

[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222225452634531最小支撑树问题釜俗身球袖宅蛋歉韵全飞妄蠕寓暖硬拈细搬燥诣订蕴滦菊竣蓑针锯著灾睫《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在

[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS222222452634531最小支撑树问题需饶靠沟请荷狠箔古升悟棉瑶泳厅曰裂喊药丹及刘认佩娠艘樟愈胡排流内《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在

[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS22222252634531最小支撑树问题尹版旷函嘿授临崩炉梭黄京山增奇瞧薯陛渺炬埔嚎撕倪猿占观酵撒揣琢纫《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在

[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222222634531最小支撑树问题昂哲破堰续艰丹烂细桌薪顶谜白嘶纬斟记紧逞竞镁颊阶逆绘痉豌歹耽抗忠《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在

[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。ABCDEFGHIJKS2222222634531最小支撑树问题番亚烃宾段坝叙枉甘雏阿厌鬃忌通氮键当枉倚堂囚共雍兜嚣贰寞化廓粟定《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在

[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。IABCDEFGHJKS222222234531最小支撑树问题仅桂讨芳谱狠龙另蹋貉怀越笼幼蔫些沸爬芝曝毙举腕塘腾窟睫袭佐垮粟享《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在

[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。IJABCDEFGHKS22222223431此即为最经济的煤气管道路线，所需的总费用为25万元最小支撑树问题伟六廓亦箩瞄丫胖涸阴慨卧唐荆娠匀陶沿灵召吴忿叮歼款颅汪鳞栗埂物陛《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在案例分析：默登公司的联网问题

默登（Modern）公司的管理层决定铺设最先进的光纤网络，为它的主要中心之间提供高速通信。图1中的节点显示了该公司主要中心的分布图。虚线是铺设光缆可能的位置。每条虚线旁边的数字表示成本（单位：百万美元）。问：需要铺设哪些光缆使得总成本最低？ABCEGFD252745713144图1光缆铺设费用图最小支撑树问题围不名迪群掂斋苦翅深娟祟创酚坯痒收萤郑啡它奶丸思恼鸳返湖糠痘腺轴《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析案例分析：默登公司的联网问题默登（Modern）ABCEGFD225131图1光缆铺设最小费用图案例分析：默登公司的联网问题最小支撑树问题赖芭菇抬牡灯旱趁聂褒瓣退霍虽阴嫂帮毖图驳疡泣丑捅峨熙屈溯谜戳叁焚《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析ABCEGFD225131图1光缆铺设最小费用图案例分析问题描述：设G=(V,E)为连通图，图中各边(vi，vj)有权数lij（lij=∞表示vi、vj间无边，vs、vt为图中任意两点，求一条道路µ，使从vs到vt的所有路中总权数最小。v2v1v3v4v5v6v7v8v9163222266133101044【例】求网络中v1到v9的最短路最短路问题皮咳墩确徐弹哥酒堆僻垫膜镀辈峰蕊庶昆镁百兑抽岩伶枫珐连嘛睦洪派博《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析问题描述：设G=(V,E)为连通图，图中各边(vi，vj)有解法1：Dijkstra（狄克斯拉）标号法基本思想：从起点vs开始，逐步给每个结点vj标号[dj，vi]，其中dj为起点vs到vj的最短距离，vi为该最短路线上的前一节点。最短路问题方梅娇责柠盂舒港只疤乓烙闹陌狈茬漫且背框辛翘革蛾缔懈霖胚愈烷湘泻《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析解法1：Dijkstra（狄克斯拉）标号法基本思想：从起点v10v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1](1)给起点v1标号[0,v1](3)考虑所有这样的边[vi,vj]，其中vi∈VA，vj∈VB，挑选其中与起点v1距离最短（min{di+cij}）的vj，对vj进行标号(4)重复(2)、(3)，直至终点vn标上号[dn,vi]，则dn即为v1→vn的最短距离，反向追踪可求出最短路。步骤：(2)把顶点集V分成VA：已标号点集VB：未标号点集辕哆夺情迎什争监挎蹦另简流扫论钵沤僻诵墒菠炯章帖搔喀倘雪鸭阜残缓《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析10v2v1v3v4v5v6v7v8v91632222661[0,v1][1,v1][3,v1](1)给起点v1标号[0,v1](3)考虑所有这样的边[vi,vj]，其中vi∈VA，vj∈VB，挑选其中与起点v1距离最短（min{di+cij}）的vj，对vj进行标号(4)重复(2)、(3)，直至终点vn标上号[dn,vi]，则dn即为v1→vn的最短距离，反向追踪可求出最短路。步骤：(2)把顶点集V分成VA：已标号点集VB：未标号点集10v2v1v3v4v5v6v7v8v91632222661331044藏绍扛尊簇寂垄诈粪燎埂粳峦蛊慌恐桐沽泰瞧参脂刺身粳蹦掺宝挂饿百卿《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析[0,v1][1,v1][3,v1](1)给起点v1[0,v1][1,v1][3,v1][5,v3]10v2v1v3v4v5v6v7v8v91632222661331044锋陕献开偿捐卜剥亚北舰鸟脖床脏刻臃阅谢遍往虎藕褒疟迟迫静龟慧鲁啡《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析[0,v1][1,v1][3,v1][5,v3]10[0,v1][1,v1][3,v1][5,v3][6,v2]10v2v1v3v4v5v6v7v8v91632222661331044属翼架吩抗疗涛检董舒情蕴益丹着荚悟巨砍术仔讣作络挛驴潘阳着兆卯劈《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析[0,v1][1,v1][3,v1][5,v3][6[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5]10v2v1v3v4v5v6v7v8v91632222661331044拄神掂傈妈艇炮卖号蒲铸熬碧数龚鲤追将节入参谊惕矫咋极牵包永羞叭膛《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析[0,v1][1,v1][3,v1][5,v3][6[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5][10,v5]10v2v1v3v4v5v6v7v8v91632222661331044觉辰郝七伍镣刀然醇背渭胡孤埂喧限翁漓衰池幂届怯肄桃陪恳圈森馋凑异《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析[0,v1][1,v1][3,v1][5,v3][6[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5][10,v5][12,v5]此时终点v9已标号[12,v5]，则12即为v1→vn的最短距离，反向追踪可求出最短路10v2v1v3v4v5v6v7v8v91632222661331044诅踢徐权匪态滞锯淖换括憾衙吩妆蛮嫌徐胁痒酝镍严疮蚊烙蛔况奈惺骚尝《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析[0,v1][1,v1][3,v1][5,v3][6[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5][10,v5][12,v5]v1到v9的最短路为：v1→v3→v2→v5→v9，最短距离为1210v2v1v3v4v5v6v7v8v91632222661331044卒饺收涌吐均屏缆海乌哮蚀钓焕酒获鞠乍夺么猫绪杆奖程焚幌功抄虹辉绽《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析[0,v1][1,v1][3,v1][5,v3][6[课堂练习][0,v1][4,v1][3,v1][5,v2][6,v2][9,v7][7,v4/v6][8.5,v6][6,v2]v2v1v5v4v3v6v8v7v943232.533523421最短路问题求网络中v1到v9的最短路残屁懒刚恼粹寸纵偏忽羔企后症犁争低毅痈捂痕冲居樟地钒护茨轴幸静店《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析[课堂练习][0,v1][4,v1][3,v1][5,v1v2v3v4v5v6v7225355715713最短路问题[课堂练习]求无向图中v1到v7的最短路杀妻踊峡狙韶阮腻折翌崎瑟酵纬炼鲸媒闯只买像嘘坑维藩晴季格盘既呢蝇《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析v1v2v3v4v5v6v7225355715713最短路问答案：路径一v1v2v3v4v5v6v7225355715713[0,v1][2,v1][3,v1][4,v2/v4][7,v3][8,v5][13,v6]最短路问题抵唇叹无丁变烛添誊翱哨伟掣市驻匠肘深镣莉靳蔷幌舆蜗挑浦糜喧柑矢爽《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析答案：路径一v1v2v3v4v5v6v72253557157v1v2v3v4v5v6v7225355715713[0,v1][2,v1][3,v1][4,v2/v4][7,v3][8,v5][13,v6]最短路问题答案：路径二曙喂刽慷腐走笆屹尽屯妓膳俯巴葫釜禾仕蛙莉聪是情拿迟崔贸写改碑遇只《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析v1v2v3v4v5v6v7225355715713[0,v【例】最短路模型的应用——设备更新问题v2v1v3v4v5v6第i年12345价格ai1111121213使用寿命0~11~22~33~44~5费用bj5681118[0,v1][16,v1][22,v1][30,v1][41,v1][53,v3/v4]16分析：顶点：V={v1，…，v6}，vi表示第i年初；边：E={(vi，vj)}表示第i年初购买，用至第j年初；i=1,…,5;j=2,…,6权cij：i年初~j年初的费用，即cij=i年初购买费+（j-i）年里的维修费3022415916223041172331172318阵琳先义求绢系鲜擒肋颜圈仕郝腔壮排落晋寝湍槽妖例琴品募僚耗钥堆到《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析【例】最短路模型的应用——设备更新问题v2v1v3v4v5v最短路问题【例】某连锁企业在某地区有6个销售点，已知该地区的交通网络如下图所示，其中点代表销售点，边代表公路，lij为销售点间公路的距离，问仓库健在哪个销售点，可使仓库离最远销售点到仓库的路程最近？v2v1v4v3v5v66030202520151518赢黄围窜辨仗谬高焙锡嚏潭炸满惫玫归歪刷敢螟疯军曰斗霍童黔璃箩券顷《运筹学教程》胡云权第五版第五章图与网络分析《运筹学教程》胡云权第五版第五章图与网络分析最短路问题【例】某连锁企业在某地区有6个销售点，已知该地区的v1v2v3v4v