第6章图与网络分析课件.ppt

《第6章图与网络分析课件.ppt》由会员分享，可在线阅读，更多相关《第6章图与网络分析课件.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第6章章 图与网络分析图与网络分析1.图的基本概念与模型图的基本概念与模型2.树图和图的最小部分树树图和图的最小部分树3.最短路问题最短路问题4.网络的最大流网络的最大流5.最小费用流最小费用流1.图的基本概念与模型图的基本概念与模型v运筹学中研究的图用来表明一些研究运筹学中研究的图用来表明一些研究对象对象和这些对象之间和这些对象之间的相互的相互关系关系。v用点表示研究对象，用边表示这些对象之间的联系，则图用点表示研究对象，用边表示这些对象之间的联系，则图G可以定义为可以定义为点点和和边边的集合，记作的集合，记作G=V，Ev如果给图中的点和边赋以具体的含义和权数，如距离、费如果给图中的点和边

2、赋以具体的含义和权数，如距离、费用等，称为用等，称为网络图网络图。v 端点、关联边、相邻端点、关联边、相邻v 环、多重边、简单图环、多重边、简单图v 次、奇点、偶点、孤立点次、奇点、偶点、孤立点v 链、圈、路、回路、连通图链、圈、路、回路、连通图v 完全图、偶图完全图、偶图v 子图、部分图子图、部分图【例例】有甲、乙、丙、丁、戊、己六名运动员报名参加有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛。如下表所示，打六个项目的比赛。如下表所示，打的是各运动员报名参加的比赛项目。的是各运动员报名参加的比赛项目。问六个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加

3、两问六个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。项比赛。ABCDEF甲甲乙乙丙丙丁丁戊戊己己ACBEDF2.树图和图的最小部分树树图和图的最小部分树v树图是无圈的连通树图是无圈的连通图。图。v性质性质1：任何树图中：任何树图中必存在次为必存在次为1的点；的点；v性质性质2：具体：具体n个顶个顶点的树图的边数恰点的树图的边数恰好为（好为（n-1）条；）条；v性质性质3：任何具有：任何具有n个点、（个点、（n-1）条边）条边的连通图是树图。的连通图是树图。2.树图和图的最小部分树树图和图的最小部分树v图的最小部分树图的最小部分树如果如果G1是是G2的部分树，又是树图，则称的

4、部分树，又是树图，则称G1是是G2的部分的部分树（或支撑树）。树（或支撑树）。树图的各条边称为树枝，一般图含有多个部分树，其树图的各条边称为树枝，一般图含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树。中树枝总长最小的部分树，称为该图的最小部分树。定理定理1：图中任一个点：图中任一个点i，若，若j是与是与i相邻点中距离最近的，相邻点中距离最近的，则边则边i，j一定必含在该图的最小部分树内。一定必含在该图的最小部分树内。推论：把图的所有点分为推论：把图的所有点分为V和和V两个集合，则两集合之两个集合，则两集合之间连线的最短边一定包含在最小部分树内。间连线的最短边一定包含在最小部分树

5、内。DE避避圈圈法法【例例】如下图所示，如下图所示，S、A、B、C、D、E、T代表村镇，代表村镇，它们间连线表明村镇间现有道路交通情况，连线旁数字代它们间连线表明村镇间现有道路交通情况，连线旁数字代表道路的长度。现要求沿图中道路架设电线，使上述村镇表道路的长度。现要求沿图中道路架设电线，使上述村镇全部同上电，应如何架设使总的路线长度为最短。全部同上电，应如何架设使总的路线长度为最短。BSACT254175213574DE破破圈圈法法【例例】如下图所示，如下图所示，S、A、B、C、D、E、T代表村镇，代表村镇，它们间连线表明村镇间现有道路交通情况，连线旁数字代它们间连线表明村镇间现有道路交通情况

6、，连线旁数字代表道路的长度。现要求沿图中道路架设电线，使上述村镇表道路的长度。现要求沿图中道路架设电线，使上述村镇全部同上电，应如何架设使总的路线长度为最短。全部同上电，应如何架设使总的路线长度为最短。BSACT2541752135743.最短路问题最短路问题v最短路问题一般来说就是最短路问题一般来说就是从给定的网络图中找出从给定的网络图中找出任意两点之间距离最短的一条路任意两点之间距离最短的一条路。这里的距离只。这里的距离只是权数的代称，在实际的网络图中，权数可以是是权数的代称，在实际的网络图中，权数可以是时间、费用等。时间、费用等。v求解最短路问题有两种算法：求解最短路问题有两种算法：求从

7、某一点至其它各点之间最短求从某一点至其它各点之间最短距离的距离的狄克斯屈拉狄克斯屈拉（Dijkstra）算）算法；法；求网络图上任意两点之间最短距求网络图上任意两点之间最短距离的离的矩阵矩阵算法；算法；狄狄克克斯斯屈屈拉拉算算法法5722126643701.L11=02.L1p=minL11+d12,L11+d13=min0+5,0+2=2=L133.L1p=minL11+d12,L13+d34,L13+d36=min0+5,4.2+7,2+4=5=L124.L1p=minL12+d25,L12+d24,L13+d34,L13+d36=min5+7,5+2,2+7,2+4=6=L16256狄狄

8、克克斯斯屈屈拉拉算算法法5722126643705.L1p=minL12+d25,L12+d24,L13+d34,L16+d64,6.L16+d65,L16+d67=min5+7,5+2,2+7,6+2,7.6+1,6+6=7=L14=L156.L1p=minL15+d57,L16+d67=min7+3,6+6=107.=L172567710【练习练习】465715524168045591016矩矩阵阵算算法法57221266437构造一个新矩阵构造一个新矩阵D（1）,该矩阵给出了网络中任意两点之间直该矩阵给出了网络中任意两点之间直接到达和包括一个中间点时的最短距离。矩阵接到达和包括一个中间点

9、时的最短距离。矩阵D（1）中每个元中每个元素的计算方式为：素的计算方式为：一般有矩阵一般有矩阵D（k）给出了网络中任意两点之间直接到达，经过给出了网络中任意两点之间直接到达，经过一个、两个、一个、两个、到（、到（2k-1）个中间点时比较得到的最短距）个中间点时比较得到的最短距离。矩阵离。矩阵D（k）中每个元素的计算方式为：中每个元素的计算方式为：【例例】某人购买一台摩托车，准备在今后某人购买一台摩托车，准备在今后4年内使用。他可在第一年初购年内使用。他可在第一年初购买一台新车，连续使用买一台新车，连续使用4年，也可于任何一年末换一台新车。已知各年初年，也可于任何一年末换一台新车。已知各年初的新

10、车购置价如下表的新车购置价如下表1。不同役龄车的年使用维护费及年末处理价如下表。不同役龄车的年使用维护费及年末处理价如下表2。要求确定该人使用摩托车的最优更新策略，使。要求确定该人使用摩托车的最优更新策略，使4年内用于购买、更新年内用于购买、更新及使用维护的总费用为最省。单位：万元。及使用维护的总费用为最省。单位：万元。第一年第一年第二年第二年第三年第三年第四年第四年年初的购置价年初的购置价2.52.62.83.1摩托车役龄摩托车役龄01年年12年年23年年34年年年使用维护费年使用维护费0.30.50.81.2该役龄年末处该役龄年末处理费理费2.01.61.31.1第一年第一年第二年第二年第

11、三年第三年第四年第四年年初的购置价年初的购置价2.52.62.83.1摩托车役龄摩托车役龄01年年12年年23年年34年年年使用维护费年使用维护费0.30.50.81.2该役龄年末处该役龄年末处理费理费2.01.61.31.10.80.91.11.41.71.822.82.94.200.81.72.63.7一个邮递员从邮局出发，走遍他负责投递的每一条街道，然一个邮递员从邮局出发，走遍他负责投递的每一条街道，然后再返回邮局，问应选择什么样的路线，使走的路程为最短。后再返回邮局，问应选择什么样的路线，使走的路程为最短。因为这个问题由中国数学工作者提出，故称为因为这个问题由中国数学工作者提出，故称为

12、中国邮路问题中国邮路问题。欧拉回路欧拉回路的定义是：连通图的定义是：连通图G中，若存在一条回路，经过每中，若存在一条回路，经过每边一次且仅一次，称这条回路为欧拉回路。称具有欧拉回路边一次且仅一次，称这条回路为欧拉回路。称具有欧拉回路的图为欧拉图。的图为欧拉图。【例例】设某邮递员设某邮递员负责投递的街道如负责投递的街道如图所示，要求找出图所示，要求找出该邮递员的最短投该邮递员的最短投递路线。递路线。44575412454214422连通图连通图G是欧拉图的充分必要条件是图中的点全为是欧拉图的充分必要条件是图中的点全为偶点偶点。（1）每条边上最多重复一次；）每条边上最多重复一次；（2）在图）在图G

13、的每个回路上，有重复边的长度不超过回路总长的每个回路上，有重复边的长度不超过回路总长的一半。的一半。445754124542144224.网络最大流网络最大流v网络最大流的有关概念网络最大流的有关概念1.有向图与容量网络有向图与容量网络有向图上的连线是有规定指向的，称作有向图上的连线是有规定指向的，称作弧弧；所谓容量网络是指对网络上的每条弧都给出一个所谓容量网络是指对网络上的每条弧都给出一个最大的通过能力，称为该最大的通过能力，称为该弧的容量弧的容量，记为，记为c(vi,vj)或简写或简写cij；在容量网络中通常规定一个在容量网络中通常规定一个发点发点（记为（记为s）和一个）和一个收点收点（记

14、为（记为t），网络中既非发点又非收点的其它），网络中既非发点又非收点的其它点称为中间点；点称为中间点；网络最大流网络最大流是指网络中从发点到收点之间允许通是指网络中从发点到收点之间允许通过的最大流量。过的最大流量。4.网络最大流网络最大流2.流与可行流流与可行流所谓所谓流流是指加在网络各条弧上的一组负载量，记是指加在网络各条弧上的一组负载量，记作作f(vi,vj)或简写为或简写为fij；若网络上所有的若网络上所有的fij=0，这个流称为，这个流称为零流零流；在容量网络上满足以下条件的一组流称为可行流：在容量网络上满足以下条件的一组流称为可行流：I.容量限制条件，对所有弧有容量限制条件，对所有弧

15、有II.中间点平衡条件中间点平衡条件4.网络最大流网络最大流v割和流量割和流量割是指将容量网络中的发点和收点分割开，并使割是指将容量网络中的发点和收点分割开，并使st的流中断的一组弧的集合。的流中断的一组弧的集合。割的容量是组成它的集合中的各弧的容量之和。割的容量是组成它的集合中的各弧的容量之和。9(4)9(9)8(8)7(5)5(4)2(0)6(1)5(5)10(8)9(4)9(9)8(8)7(5)5(4)2(0)6(1)5(5)10(8)VV割割容量容量4.网络最大流网络最大流v最大流最小割定理最大流最小割定理如果在网络的发点和收点之间能找到一条链，在这条如果在网络的发点和收点之间能找到一

16、条链，在这条链上所有指向为链上所有指向为st的弧（称为的弧（称为前向弧前向弧，记作，记作+），），存在存在f0，这样的链称为，这样的链称为增广链增广链。4.网络最大流网络最大流v最大流最小割定理最大流最小割定理当增广链存在时，找出当增广链存在时，找出再令再令定理：定理：在网络中在网络中st的最大流量等于它的最小割集的的最大流量等于它的最小割集的容量容量。4.网络最大流网络最大流vFord-Fulkerson标号算法标号算法1.首先给发点首先给发点s标号标号 。括弧中的第一个数字是。括弧中的第一个数字是使这个点得到标号的前一个点的代号；括弧中的第使这个点得到标号的前一个点的代号；括弧中的第二个数

17、字表示从上一个标号到这个标号点的流量的二个数字表示从上一个标号到这个标号点的流量的最大允许调整值。最大允许调整值。2.列出与已标号点相邻的所有未标号点：列出与已标号点相邻的所有未标号点：I.考虑从已标号点考虑从已标号点i出发的弧（出发的弧（i，j）：）：j点不标号点不标号j点标号点标号2.列出与已标号点相邻的所有未标号点：列出与已标号点相邻的所有未标号点：II.考虑所有指向已标号点考虑所有指向已标号点i的弧（的弧（h，i）：）：III.如果某未标号点如果某未标号点k有两个以上相邻的标号点，为减少迭有两个以上相邻的标号点，为减少迭代次数，可按代次数，可按I、II中所述规则分别计算出中所述规则分别

18、计算出 的值，的值，并取其中最大的一个标记。并取其中最大的一个标记。3.重复第重复第2步，可能出现两种结局：步，可能出现两种结局：I.标号过程中断，标号过程中断，t得不到标号，说明网络中不存在增广得不到标号，说明网络中不存在增广链，给定的流量即为最大流。记已标号点的集合为链，给定的流量即为最大流。记已标号点的集合为V,未未标号点集合为标号点集合为V，（，（V，V）为网络的最小割；）为网络的最小割；II.t点得到标号，反向追踪找出增广链；点得到标号，反向追踪找出增广链；h点不标号点不标号h点标号点标号4.修改流量，设图中原有可行流为修改流量，设图中原有可行流为f，按一下方式获得，按一下方式获得新

19、的可行流新的可行流f：5.抹掉图中所有标号，重复第抹掉图中所有标号，重复第1到第到第4步，直至图中找步，直至图中找不到任何增广链，即出现第不到任何增广链，即出现第3步的结局步的结局I为止，这时为止，这时网络图中的流量即为最大流。网络图中的流量即为最大流。9(4)9(9)8(8)7(5)5(4)2(0)6(1)5(5)10(8)9(4)9(9)8(8)7(5)5(4)2(0)6(1)5(5)10(8)7(6)5(3)9(5)6(0)10(9)最小割最小割最大流：最大流：145(5)6(4)3(3)5(4)2(0)3(3)3(2)4(4)2(2)2(0)8(6)6(6)5(5)6(5)3(3)5(

20、5)2(0)3(2)3(3)4(4)2(1)2(0)8(7)6(6)最小割最小割最大流：最大流：13DBCEAF1234567891011 1213【例例】某河流中有某河流中有4个岛屿，从两岸至各岛屿及各岛屿之间个岛屿，从两岸至各岛屿及各岛屿之间的桥梁编号如图所示，在一次敌对的军事行动中，问至少应的桥梁编号如图所示，在一次敌对的军事行动中，问至少应炸断哪几座桥梁，才能完全切断两岸的交通联系？炸断哪几座桥梁，才能完全切断两岸的交通联系？DBCEAF1234567891011 1213ABCDEF221211113ABCDEF2(1)21(1)2(1)1111(1)3(1)ABCDEF2(1)21

21、(1)2(1)1111(1)3(1)ABCDEF2(2)21(1)2(2)111(1)1(1)3(2)最小割：最小割：(D,F),(D,E),(A,E)DBCEAF1234567891011 12135.最小费用流最小费用流v最小费用流问题最小费用流问题对于容量网络，除考虑各条弧上的流量、容量外，对于容量网络，除考虑各条弧上的流量、容量外，还需考虑弧上通过单位流量时的费用（还需考虑弧上通过单位流量时的费用（bij），保证），保证最终给出的流量或最大流也是费用最少的。最终给出的流量或最大流也是费用最少的。关键点：确定关键点：确定“最小费用增广链最小费用增广链”。(5,8)(8,7)(2,5)(4

22、,9)(10,9)(3,2)(8,4)【例例】各弧旁数字各弧旁数字为为(cij,bij)，试求，试求图中从图中从st的最小的最小费用最大流。费用最大流。1.从原容量网络的零流从原容量网络的零流f0开始；开始；2.对原容量网络的可行流对原容量网络的可行流fk构造构造加权网络加权网络W(fk):对对0fijcij的弧的弧(i,j)，在加权网络的，在加权网络的i点和点和j点之间分别绘制弧点之间分别绘制弧(i,j)和和(j,i)，其权数分别为，其权数分别为bij和和-bij；对对fij=cij的弧，在加权网络的的弧，在加权网络的i点和点和j点之间绘制弧点之间绘制弧(j,i)，其权数，其权数为为-bij

23、；对对fij=0的弧，在加权网络的的弧，在加权网络的i点和点和j点之间绘制弧点之间绘制弧(i,j)，其权数为，其权数为bij。3.确定最小费用增广链等价于求解加权网络确定最小费用增广链等价于求解加权网络st之间的最之间的最短路。找出增广链之后调整原容量网络的流量；短路。找出增广链之后调整原容量网络的流量；4.重复重复2、3步骤，直到步骤，直到st之间找不出最短路为止，此时之间找不出最短路为止，此时求得原容量网络的最小费用最大流。求得原容量网络的最小费用最大流。5.最小费用流最小费用流(5,8)(8,7)(2,5)(4,9)(10,9)(3,2)(8,4)875992407810145(3)8(

24、0)2(0)4(0)10(0)3(3)8(3)(5,8)(8,7)(2,5)(4,9)(10,9)(3,2)(8,4)5(3)8(0)2(0)4(0)10(0)3(3)8(3)875994-8-2-4875994-8-2-45(3)8(0)2(0)4(0)10(0)3(3)8(3)5(5)8(0)2(0)4(2)10(0)3(3)8(3)875994-8-2-4(5,8)(8,7)(2,5)(4,9)(10,9)(3,2)(8,4)5(5)8(0)2(0)4(2)10(0)3(3)8(3)75994-8-2-4-975994-8-2-4-975994-8-2-4-95(5)8(0)2(0)4(

25、2)10(0)3(3)8(3)5(5)8(5)2(0)4(2)10(5)3(3)8(8)(5,8)(8,7)(2,5)(4,9)(10,9)(3,2)(8,4)5(5)8(5)2(0)4(2)10(5)3(3)8(8)7599-8-2-4-9-7-97599-8-2-4-9-7-97599-8-2-4-9-7-95(5)8(5)2(0)4(2)10(5)3(3)8(8)5(5)8(7)2(2)4(4)10(5)3(3)8(8)(5,8)(8,7)(2,5)(4,9)(10,9)(3,2)(8,4)5(5)8(7)2(2)4(4)10(5)3(3)8(8)7-59-8-2-4-9-7-97-59-8-2-4-9-7-95(5)8(7)2(2)4(4)10(5)3(3)8(8)