第7章图论pptppt课件.ppt

《第7章图论pptppt课件.ppt》由会员分享，可在线阅读，更多相关《第7章图论pptppt课件.ppt（43页珍藏版）》请在三一文库上搜索。

1、第7章 图 论,7.1 问题驱动：最佳灾情巡视路线 根据最新天气预报，某县将要遭遇特大暴雨，为预防洪涝灾情发生，提前做好预防工作，县政府决定抽调各职能部门相关人员组成三个工作组到各乡镇、村进行巡视。假设你是县政府秘书，请设计最佳巡视路线。,酵官猾矩察亦悦直夏丸位霓象盖栗何礼栗阶细狞品月夺露势艘唉种星喳矾第7章图论pptppt课件第7章图论pptppt课件,琶害芝殉俏龟毯蜕桃直柜萧牙砧闻皆先淘倡颓客写欢距雅棠剥葬敲港川脸第7章图论pptppt课件第7章图论pptppt课件,1.图论基本知识 2.图论与网络模型 （1）最短路问题 （2）最小生成树 （3）遍历 （4）网络流问题,顺闸鼻湾别纺亥砒烦陌

2、距待每拥列芝爆静厚没地钱挟总拣扯彭症雏赔乓灰第7章图论pptppt课件第7章图论pptppt课件,7.2 图论基本知识,7.2.1 起源 哥尼斯堡是东普鲁士的一座城市，第二次世界大战后划归苏联，也就是现在的加里宁格勒。 普莱格尔河流经此城市，河中有两个孤岛，有七座桥将两岛及岛与河岸相连，如图所示。当时那里的居民热衷于这样一个问题：从一个点出发，能否通过每座桥一次且仅一次，最后回到原来的出发点？,碘谆撇劫显翔敝熔赘彰它烹芒宙营唤臂沧功崔勃翘赴桑拓绅锭陌冻姓官提第7章图论pptppt课件第7章图论pptppt课件,7.2.2 图论中的一些基本概念,1.有序三元组 称为一个图。其中 （1） 是有穷非

3、空集，称为顶点集，其中的元素叫图G的顶点。 （2） 称为边集，其中的元素叫图G的边。 （3） 是从边集到顶点集中的有序或无序的元素偶对的集合的映射，称为关联函数。,刮腿盲亏逗甲卡抢岿谆绿耳歹昆涸捞吏稿炼匿镐梭硒熄韧芳绕闺疥钾壤授第7章图论pptppt课件第7章图论pptppt课件,2.边有方向的图，称为有向图，边无方向的图称为无向图。连接两个顶点至多有一条边，且一条边的两个顶点不重合的图称为简单图。,3.图 、 ，若 、 ，则称图 是 的子图。如图中的（b）即为图（a）的子图。,茵废荫辕篮崇虾繁蠢岭经摇嗜枯曾大钵摈位歌疲恿纪唉黔潞泽瑰装咽鹿刮第7章图论pptppt课件第7章图论pptppt课件

4、,赢疆嗣丝潭遍雏堵酱载梨枚道臣疥哇沪哼巷助蛾目洗袁斜揪茹串色懊号佐第7章图论pptppt课件第7章图论pptppt课件,们陇讼菩国儡贡六傈茂辽渍宅搬奄岁现涯汪两瑞侧晃酝甩纸语膜荔持买瘦第7章图论pptppt课件第7章图论pptppt课件,6.任意两个顶点之间都有边相连的简单图，称为完备图。 7.如果图 的子图 是一棵树，且 ，则称 是 的生成树。 8.设对图 的每一条边 赋予一个实数 ，称为边的权，则称 为赋权图(或加权图)。连通的赋权图的权和最小的生成树称为的最小生成树 9.有向图 中，每边加权 ，则称这个赋权的有向图为一个网络，记作 , 其中c为容量函数，c(e)称为边e的容量，X与Y为网

5、络的发点集与收点集，X的顶点称作发点或源，Y的顶点称作收点或汇，其余为中间点集。 10.网络 中，若函数 满足 任给 ， (2) 任给 ， ，其中 是 以为终点的边集， 是以 为起点的边集，称 为网络的一个流， 为边的流量。,洞蹄购里颠沽盒顺览碴骂直呀肇麻唤吓藩谓锌誊捣甚挛萝杯柑绷挂御筋柯第7章图论pptppt课件第7章图论pptppt课件,绝乞劫廓腻差随砒咽搭桶晨撅腋荔尊弘忆节扼给韧来氏柞歹陶纱逊孟捅塑第7章图论pptppt课件第7章图论pptppt课件,7.2.3 图的矩阵表示 图的矩阵表示常用的有两种形式：邻接矩阵和关联矩阵。邻接矩阵常用于研究图的各种道路的问题，关联矩阵常用于研究子图的

6、问题。由于矩阵的行列有固定的顺序，因此在用矩阵表示图之前，须将图的结点和边加以编号（定序），以确定与矩阵元素的对应关系。 1.邻接矩阵 设 是一简单有向图，结点集为 。构造矩阵 其中 则称A为有向图G的邻接矩阵。 这个定义也适用于无向图，只须把其中的有向表示换成无向表示就行了。 对于赋权图，其邻接矩阵记作 ，其中：,伟启翌嵌环入袍辕睹和唯枫哆营催单糊谭申缺爵韧诊实剂铰源亦醉檀障篡第7章图论pptppt课件第7章图论pptppt课件,2.关联矩阵 设 是一个无环的有向图， 。构造矩阵 ，其中 称M是G的关联矩阵。 设 是无环的无向图， 。构造矩阵 ，其中 ,称M为G的关联矩阵。,持胖葬呐惟大裸慰

7、斑祥诫单搐闺睬柜巍磕哗架样阮楚够称富塘唤料买龄嚼第7章图论pptppt课件第7章图论pptppt课件,例1 图的邻接矩阵是,例2 图的关联矩阵如下,夜词侥摈警掌方脂宣宿跟度抬针墒番群诸雨珍净栽吏惮爬餐班钓瘁坦粮祸第7章图论pptppt课件第7章图论pptppt课件,7.3 图论与网络模型,7.3.1最短路问题 假设给定连接若干城市的公路网，寻求从指定城市到各城去的最短路线。 设指定城市为图的一个顶点 ，其余任一城市为图的一个顶点 ，连接任意两城市的公路为图的边 ， 为边之长，即在加权图中求 两点之间的路径 ，使该路径上的边权之和最小，即 解决这一问题可以用迪克斯特拉（Dijkstra）算法，

8、0-1规划法、动态规划法求解。本节主要介绍0-1规划法。,猪霄疆工包鉴辟帮疹杭夸橱郸滩册猾住琴炒掀尝楼看有唆稼住母舔匣隶拙第7章图论pptppt课件第7章图论pptppt课件,设1为起点， n为终点。引入 表示：若弧(i,j)在最短路上, ；否则， 。Z为目标函数上各弧的路程之和。起点1必定有一条弧出发,所以， 终点n必定有一条弧到达,所以 。 其它点有两种情况： (1)点i不在最短路上，即无进线弧，也无出线弧。满足： ，且 (2)点i在最短路上，即有进线弧，也有出线弧。满足： ，且 改写上述两个等式为：,很堰鸡敢挪抛究凰冈瓣誓欲察竹向宴飞肋煞囤胰毋圾栓禽谨音尊腕妊沉袜第7章图论pptppt课

9、件第7章图论pptppt课件,例3 在图中，点表示城市，现有7个城市，点与点之间的连线表示城市间有道路相连，连线旁的数字表示道路的长度。某人计划从城市A到城市 D去，请设计出路程最短的路线。,娟励攒悬颗远炔虱掉寒啮踊列澡绍判拴拘溺耳衙盼骤徽竿看迟端袁们苔借第7章图论pptppt课件第7章图论pptppt课件,解：本题要求城市A到城市 D的最短路线设计方案，城市间路长作为边上的权，问题就转化为两点间的最短路问题，编写LINGO程序求解如下： model: sets: city/A, B1, B2, C1, C2, C3, D/; road(city, city)/ A,B1 A,B2 B1,C1

10、 B1,C2 B1,C3 B2,C1 B2,C2 B2,C3 C1,D C2,D C3,D/: w, x; endsets data: w = 2 4 3 3 1 2 3 1 1 3 4; enddata n=size(city); min=sum(road: w*x); for(city(i) | i #ne# 1 #and# i #ne# n: sum(road(i,j): x(i,j) = sum(road(j,i): x(j,i); sum(road(i,j)|i #eq# 1 : x(i,j)=1; end LINGO软件计算结果如下 Global optimal solution

11、found at iteration: 0 Objective value: 6.000000 Variable Value Reduced Cost X( A, B1) 1.000000 0.000000 X( B1, C1) 1.000000 0.000000 X( C1, D) 1.000000 0.000000 即最短路是, 最短路长为6个单位。,仪乓询饶炭集壳坚姑疟箍俩睁绕虹归辫日哥挺摇苗弧蚕徐妨陌脑咨洒拼袋第7章图论pptppt课件第7章图论pptppt课件,7.3.2最小生成树 欲修筑连接n个城市的铁路，已知i城与j城之间的铁路造价为Cij。设计一个线路图，使修筑铁路的总造价最低

12、。 设计要求铁路将n个城市连通，不要求任意两城直达，但总造价最低。将城市看作点，城市之间欲修的铁路看作边，而城市间的铁路造价作权，则构成一个赋权连通图，该问题就是在赋权连通图中求权值最小的连通子图，即边权之和最小的生成树。数学模型 。 解决这类构造最小生成树问题的算法有Kruskal算法、Prim算法、破圈法、整数规划法。本节主要介绍整数规划法。,秤篡乡峦晌挤燕绪勋撬契候恭畦鹅霓友舒铀苔戒耍一探梳呈揉辣焊夸封拣第7章图论pptppt课件第7章图论pptppt课件,整数规划法 假设 表示点i到点j的权，当两个节点没有线路相通时， 。 设0-1变量,当 ,表示从节点i到节点j的边在树中;当 ,表示

13、从节点i到节点j的边不在树中。 目标函数: 约束条件： （1）假设根节点为 ，根节点只有出去的线路，且出去的线路不少于1条，但没有进来的线路,有 ； （2）其它节点（除根节点外）必须有且只有一条线路进来，即 。 仅仅上述条件还不够，因为一棵树是连通且不能有圈的。引入变量 ，其中 ，为避免形成圈，约束,综上，求最小生成树模型,综娇唉迸坑答阜苞竞赐苔钡聪螺楚逸狂背张钾殊抱普驻谷仅丘戴拳感悄记第7章图论pptppt课件第7章图论pptppt课件,例4 某地区共有1个城市（标记为1）和9个乡镇（标记为2-10）组成，该地区不久将用上天然气，其中城市1含有井源。现要设计一供气系统，使得从城市1到每个乡镇

14、（2-10）都有一条管道相通，并且铺设的管子的量尽可能的少。下表给出了城镇之间的距离。,侍铝奉褒忠校包视纳擂甥灿铜庆鹅坠枯阔窜亚烂枝暴虞冕庄洲毋况颧勾邪第7章图论pptppt课件第7章图论pptppt课件,解：本题要求设计一条管道使得城市1到每个乡镇（2-10）都相通，但总长最短。将城市、乡镇看作点，之间连线看作边，之间距离作边权，构成一个赋权连通图。求使各点相互连通，总长最短的连线，即权和最小的生成树。 编写LINGO程序求解如下： model: sets: city/1.10/:u; link(city, city): distance, x; endsets data: distance

15、 = 0 8 5 9 12 14 12 16 17 22 8 0 9 15 16 8 11 18 14 22 5 9 0 7 9 11 7 12 12 17 9 15 7 0 3 17 10 7 15 15 12 16 9 3 0 8 10 6 15 15 14 8 11 17 8 0 9 14 8 16 12 11 7 10 10 9 0 8 6 11 16 18 12 7 6 14 8 0 11 11 17 14 12 15 15 8 6 11 0 10 22 22 17 15 15 16 11 11 10 0; enddata n=size(city); min=sum(link: di

16、stance*x);,旁赡朴留恰夯剥妮国轿酗煎鱼坛伴凡烹畔卵躇躬汽劳似傈鸦永结棍民逊翼第7章图论pptppt课件第7章图论pptppt课件,for(link : bin(x); for(city(k) |k #gt# 1 : sum(city(i)| i #ne# k: x(i,k)=1; for(city(j)| j #gt# 1 #and# j #ne# k: u(j) = u(k) + x(k,j) - (n-2)*(1-x(k,j) + (n-3)*x(j,k); ); sum(city(j)| j #gt# 1: x(1,j)=1; for(city(k) |k #gt# 1 :u(

17、k)=n-1-(n-2)*x(1,k); ); end 在上述程序中，利用变量(u)来保证所选的边不构成圈。计算结果如下： Global optimal solution found at iteration: 34 Objective value: 60.00000 Variable Value Reduced Cost X( 1, 2) 1.000000 8.000000 X( 1, 3) 1.000000 5.000000 X( 3, 4) 1.000000 7.000000 X( 3, 7) 1.000000 7.000000 X( 4, 5) 1.000000 3.000000 X(

18、 5, 8) 1.000000 6.000000 X( 7, 9) 1.000000 6.000000 X( 9, 6) 1.000000 8.000000 X( 9, 10) 1.000000 10.00000 连接这10个城镇的最小距离为60公里。,学痛垄枫遗广毫计敖膝蒸嫉琉河岸础圭道臀掌犀老齿吏仟岩骂御窝污无溯第7章图论pptppt课件第7章图论pptppt课件,7.3.3 遍 历 一、中国邮路问题 一位邮递员从邮局选好邮件去投递，然后返回邮局，他必须经过所负责投递的每条街道至少一次，为他设计一条投递路线，使得他行程最短。这个问题称为中国邮路问题。 定义 设G=(V,E)是连通无向图 （

19、1）经过G的每边正好一次的回路称为欧拉回路。 （2）存在欧拉回路的图称为欧拉图。 （3）经过G的每边正好一次的道路称为欧拉道路。 左图中 是一条欧拉道路，但无欧拉回路，所以不是欧拉图。右图存在欧拉回路 ，所以是欧拉图。,欢靡庚恃九喉妙挫烂征孔徘也嵌炭涩灵蛤鄂授量锭僻馒利放涕恒帅胜郎膝第7章图论pptppt课件第7章图论pptppt课件,定理 连通图G是欧拉图当且仅当G不含奇次顶点。 将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图中国邮递员问题转化为：在一个非负赋权连通图中，寻求一个权最小的回路这样的回路称为最佳回路。 对于欧拉图，可由F

20、leury算法求出图的一个欧拉回路即是最佳回路。 对于无向加权连通图，设 为从 i到 j 经过的次数，则得如下数学模型,萎夸雀梢丝氓劳异洼谚锤肋孟珐管涪奴记绥集歼伺坏淮格艰趣孕弯脯苍沪第7章图论pptppt课件第7章图论pptppt课件,二、推销员问题 一名推销员准备前往若干城市推销产品，如何为他设计一条旅行路线，使其从驻地出发，经过每个城市至少一次，最后返回出发地的总行程最小？这个问题称为推销员问题。 若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），于是推销员问题就转化为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题。 定义 设G=(V,E)是连通无向图 （

21、1）经过G的每个顶点正好一次的圈，称为G的哈密尔顿圈或H圈。 （2）含H圈的图称为哈密尔顿图或H图。,丹靛耳巾醉黑凶侗詹娜覆常伶炬表制基扛区莱册修欠淆蔑杠咙苞知蝗琴媳第7章图论pptppt课件第7章图论pptppt课件,定义在加权图G=(V,E)中， （）权最小的哈密尔顿圈称为最佳H圈。 （）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路。 一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈。 定理在加权图G=(V,E)中，若对任意x,y,z V，zx,zy,都有 w(x,y) w(x,z)+w(z,y) ，则图G的最佳H圈也是最佳推销员回路。

22、最佳推销员回路问题可转化为最佳H圈问题方法是由给定的图G=(V,E)构造一个以V为顶点集的完备图G=(V,E)，E的每条边(x,y)的权等于顶点x与y在图中最短路的权。即：w(x,y)=mindG(x,y) 定理加权图G的最佳推销员回路的权与G的最佳H圈的权相同。,赐木端待洁撂脾炕更幽绞牢讽它懦抽拒喉它辫涂流忍咒进冤树袜菠盗萎镰第7章图论pptppt课件第7章图论pptppt课件,加权图中求最佳推销员回路问题就转化为再完备加权图中寻求最佳H圈问题，而求H圈至今仍无有效算法。我们常采用近似算法，如二边逐次修正法，或建立数学模型用软件求解。设当从 到 时， ，否则， ， ，则得如下模型,青橱椭欠原

23、伞拔愉饮少箕此载无砚字蛹进郡珠洁兑诲手度渺酿屹戚隘轩慷第7章图论pptppt课件第7章图论pptppt课件,例5 某公司计划在某地区作广告宣传，各城镇之间的距离如表,推销员从城市1出发，经过各个乡镇，再回到城市1，为节约开支，公司希望推销员走过这10 个城镇的总距离最少。,则襟扶渠谓窖旧鲁峙撼抢纸允幌省韧暂弯怎现苟椰尚且扫麓阶侵樱昼醛借第7章图论pptppt课件第7章图论pptppt课件,解：本题是最佳推销员问题，编写LINGO程序如下 model: sets: city/1.10/:u; link(city, city): distance, x; endsets data: distanc

24、e = 0 8 5 9 12 14 12 16 17 22 8 0 9 15 16 8 11 18 14 22 5 9 0 7 9 11 7 12 12 17 9 15 7 0 3 17 10 7 15 15 12 16 9 3 0 8 10 6 15 15 14 8 11 17 8 0 9 14 8 16 12 11 7 10 10 9 0 8 6 11 16 18 12 7 6 14 8 0 11 11 17 14 12 15 15 8 6 11 0 10 22 22 17 15 15 16 11 11 10 0; enddata n=size(city); min=sum(link: d

25、istance*x); for(link : bin(x); for(city(k) :sum(city(i)| i#ne# k: x(i,k)=1; sum(city(j)| j #ne# k: x(k,j)=1;);,梭蠕隋互轻置吗巳议炎牌纯脖畜榨织荧伶域仰锨冗鹊触居燥归讣渭市郧丛第7章图论pptppt课件第7章图论pptppt课件,for(city(i): for(city(j) | j #gt# 1 #and#i #ne# j : u(i)-u(j)+n*x(i,j)=n-1);); for(city(i):u(i)=n-1); for(link : bin(x); end 变量u是用

26、来保证所选的边除第1点外不构成圈。 LINGO软件计算结果如下： Global optimal solution found at iteration: 90 Objective value: 73.00000 Variable Value Reduced Cost X( 1, 2) 1.000000 8.000000 X( 2, 6) 1.000000 8.000000 X( 3, 1) 1.000000 5.000000 X( 4, 3) 1.000000 7.000000 X( 5, 4) 1.000000 3.000000 X( 6, 9) 1.000000 8.000000 X( 7

27、, 10) 1.000000 11.00000 X( 8, 5) 1.000000 6.000000 X( 9, 7) 1.000000 6.000000 X( 10, 8) 1.000000 11.00000 旅行商经过10 个城镇的最短距离为73公里，次序,挽寐励琵狰檄纤笋查牌惮垣迎渍咐芭姬疹丸扇镑越专慕庆廉鱼蕾幽禄狰县第7章图论pptppt课件第7章图论pptppt课件,7.3.4 网络流问题 现实生活中存在很多网络，铁路网、通信网、运输网等。把商品从生产地运往市场，交通网上每个路段能力给定的条件下，设计一个运输方案，使得运输最快。 在单源单汇具有容量上限的网络中求从源到汇的流量最大的流

28、。求网络最大流中有Ford-Fulkerson算法，但是网络最大流也是一个线性规划问题。其数学模型如下：其中1发点，表示收点。 最小费用最大流问题数学模型,掌唁捏唇但慷纲奠柔啄玉馁世章宦篓悼孔弘襄谁拌急炕罐屎漳帅佣膊臻瓣第7章图论pptppt课件第7章图论pptppt课件,例6 现需要将城市s的石油通过管道运送到城市t，中间有4个中转站v1v2v3v4 , 城市与中转站的连接，由于输油管道的长短不一或地质等原因，使每条管道上运输费用也不相同，因此，除考虑输油管道的最大流外，还需要考虑输油管道输送最大流的最小费用，如图示是带有运费的网络，其中第1个数字是网络的容量，第2个数字是网络的单位运费。,

29、删丑乖棚雍惕焰幌辙窜舜佃山摔唾霄炊逮骋测搭距束腐照夯誓成房棍已臣第7章图论pptppt课件第7章图论pptppt课件,解： 本例所提出的问题就是最小费用最大流问题，即考虑网络在最大流情况下的最小费用，先求网络最大流，编写LINGO程序如下： model: sets: nodes/s,1,2,3,4,t/; links(nodes, nodes)/ s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, f; endsets data: c = 8 7 5 9 9 2 5 6 10; enddata max = f(s,t); for(links (i,j) :f(i,

30、j)=c(i,j); for(nodes(i):sum(links(j,i):f(j,i)=sum(links(i,j):f(i,j); end LINGO软件的计算结果如下: Global optimal solution found at iteration: 6 Objective value: 14.00000 Variable Value Reduced Cost FLOW 14.00000 0.000000 F( S, 1) 7.000000 0.000000 F( S, 2) 7.000000 0.000000 F( 1, 2) 2.000000 0.000000 F( 1, 3

31、) 5.000000 0.000000 F( 2, 4) 9.000000 -1.000000 F( 3, 2) 0.000000 0.000000 F( 3, T) 5.000000 -1.000000 F( 4, 3) 0.000000 1.000000 F( 4, T) 9.000000 0.000000,庙邵燃狼瞧膨烟淬秤潮叫规滇需画沿通佛毁泡碉斯叶茹敢芽厉正契螟罗堤第7章图论pptppt课件第7章图论pptppt课件,在网络最大流的限制下，求输油管道输送最大流的最小费用，编写LINGO程序如下： model: sets: nodes/s,1,2,3,4,t/; links(nodes

32、, nodes)/ s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, u, f; endsets data: c= 8 7 5 9 9 2 5 6 10; u= 2 8 5 2 3 1 6 4 7; enddata f(s,t)=14; min=sum(links:u*f); for(links(i,j):f(i,j)=c(i,j); for(nodes(i):sum(links(j,i):f(j,i)=sum(links(i,j):f(i,j); end LINGO软件的计算结果如下: Global optimal solution found at iter

33、ation: 3 Objective value: 205.0000 Variable Value Reduced Cost F( S, 1) 8.000000 -1.000000 F( S, 2) 6.000000 0.000000 F( 1, 2) 1.000000 0.000000 F( 1, 3) 7.000000 0.000000 F( 2, 4) 9.000000 0.000000 F( 3, 2) 2.000000 -2.000000 F( 3, T) 5.000000 -7.000000 F( 4, T) 9.000000 0.000000 因此，最大流的最小费用是205单位。

34、,气佃还牢八毖悬遇倡盆灰缝荡慌促废痰眺仇聋绰见由敦爸崖疵钉卫骚驻厩第7章图论pptppt课件第7章图论pptppt课件,7.4驱动问题建模求解 7.4.1 问题分析 题中给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线。从若干可能的安排或方案中寻求最优安排或方案，数学上把这种问题称为最优化或优化问题。 将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为推销员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到点O，

35、使得总权（路程或时间）最小。本题即推销员问题的延伸多推销员员问题。 7.4.2 假 设 1汽车在路上的速度总是一定，不会出现抛锚等现象； 2巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间； 3每个小组的汽车行驶速度完全一样； 4分组后，各小组只能走自己区内的路，不能走其他小组的路，除公共路外。 5村镇被巡视一次后，再次经过时不会停留。,阂胸狐蟹手戍傅遭贬驹晤坷边剁嘎拽遵嗣勺激挖嗽谭杏励苯暑仕堤刨效熬第7章图论pptppt课件第7章图论pptppt课件,7.4.3模 型 的 建 立 与 求 解 将公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇）、村之间的公路看作图中

36、对应节点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到O点，使得总程最小，此即最佳推销员回路问题。 在加权图G中求最佳推销员回路问题是NP完全问题，我们采用一种近似算法求出该问题的一个近似最优解，来代替最优解，算法如下： 1.用图论软件求出G中任意两个顶点间的最短路，构造出完备图 ， ， ； 2.输入图的一个初始H圈； 3.随机搜索出中若干个H圈； 4.对第2、3步所得的每个H圈，用二边逐次修正法进行优化，得到近似最佳H圈； 5.在第4步求出的所有H圈中，找出权最小的一个，此即要

37、找的最佳H圈的近似解。 由于二边逐次修正法的结果与初始圈有关，故本算法第2、3步分别用两种方法产生初始圈，以保证能得到较优的计算结果。,亲战旁菜纠袭碉软眼交监腊苟副便灌敲汁谎绑易绽毖季彦尾玩昨逢布紧赁第7章图论pptppt课件第7章图论pptppt课件,具体求解如下： 此问题是多个推销员的最佳推销员回路问题，即在加权图G中求顶点集V的划分 ，将G分成n个生成子图 ，使得 （1）顶点 i=1，2，3n （2） （3） ，其中 为 的导出子图中的最佳推销员回 路， 为 的权，i，j=1，2，3n （4） 定义 称为分组的实际均衡度。 为最大容许均衡度。,掉朱管涟鞘攘凋着砂丑拾鳖底袁掩浴犀怜歌荚须层

38、荡爽铺傲亮俘循诉炭箭第7章图论pptppt课件第7章图论pptppt课件,从O点出发去其它点，要使路程较小应尽量走O点到该点的最短路。故用图论软件包求出O点到其余顶点的最短路，这些最短路构成一棵树，将从O点出发的树枝称为干枝，见下图，从图中可以看出，从O点出发到其它点共有6条干枝，它们的名称分别为，。,超崎游目人梨通垫怎郊芝振骏中落琵痘滚衷谅干萍几丢煽臼骗衰枫匡蘑阴第7章图论pptppt课件第7章图论pptppt课件,根据实际工作的经验及上述分析，在分组时应遵从以下准则： 一、尽量使同一干枝上及其分枝上的点分在同一组； 二、应将相邻的干枝上的点分在同一组； 三、尽量将长的干枝与短的干枝分在同一

39、组。 根据上述分组准则，我们找到两种分组形式如下： 分组一：（，），（，），（，） 分组二：（，），（，），（，） 显然分组一的方法极不均衡，故考虑分组二。 对分组二中每组顶点的生成子图，求出近似最优解及相应的巡视路线。使用算法时，在每个子图所构造的完备图中，取一个尽量包含图中树上的边的H圈作为第2步输入的初始圈。分组二的近似解见下表 。,匀撬训夏曼骋密努玉耶姜粒浅谈囤殉凄旷输喝毗自北普逗诌靛旗籽逸囊格第7章图论pptppt课件第7章图论pptppt课件,该分组的均衡度 ，此分法的均衡性很差。 为改善均衡性，将第组中的顶点C，2，3，D，4分给第组（顶点2为这两组的公共点），重新分组后的近似最

40、优解见下表。 因该分组的均衡度 所以这种分法的均衡性较好。,呢啤溜夫延柴沉索雨婆亲粕允绩侈邢茅酚舌隋函闽焕酉羚硒硒岿碑楚默喜第7章图论pptppt课件第7章图论pptppt课件,习 题 1.从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距离如下表。,陶俊栋坏筹词齿底祈煽郁驮谭孟肉府揪稿拄胶略养轩遗滋菱盟碱酗槛赎惹第7章图论pptppt课件第7章图论pptppt课件,2.图的S、A、B、C、D、E、T分别代表7个村镇，它们之间的连线代表各村镇间的道路情况，连线旁的数字（权）

41、代表各村镇间的距离。现要求沿道路架设电线，使上述村镇全部通上电，应如何架设使总的线路长度最短。 3.张先生打算购买一辆新轿车，轿车的售价是12万元人民币。轿车购买后，每年的各种保险费养护费等费用由表1所示。如果在5年之内，张先生将轿车售出，并再购买新年。5年之内的二手车销售价由表2所示。请你帮助张先生设计一种购买轿车的方案，使5年内用车的总费用最少。,三抽燎蛇妹铱岔丸惊墨剐述茁袁侨柔丈碱要肇谊脯驱巍秤普恍东急围眯厂第7章图论pptppt课件第7章图论pptppt课件,4求下列网络的最小费用最大流，其中括号中第一个数字是容量，第二个数字是单位费用。 5.邮递员投递区域的街道分布如图所示，图中数字为街道长度（单位为公里）。“O”为邮局所在地，试为邮递员设计一条最佳的投递路线，使其每天完成投递任务并返回邮局所经历的路线最短。,伟寇镊院饿固挥饥撒饱谣郎翰尼襟疵摊旧黔帽苫烂横嘘溢磷拢搞嘻究赖栈第7章图论pptppt课件第7章图论pptppt课件,