第6章图与网络分析

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

2、给图中的点和边赋以具体的含义和权数，如距离、费用等，称为费用等，称为网络图网络图。1v4v2v3v5v1e2e3e7e6e5e8e4ev 端点、关联边、相邻端点、关联边、相邻v 环、多重边、简单图环、多重边、简单图v 次、奇点、偶点、孤立点次、奇点、偶点、孤立点v 链、圈、路、回路、连通图链、圈、路、回路、连通图v 完全图、偶图完全图、偶图v 子图、部分图子图、部分图4v2v3v5v7e6e8e4e1v4v2v3v5v2e3e7e6e8e4e【例【例】有甲、乙、丙、丁、戊、己六名运动员报名参加有甲、乙、丙、丁、戊、己六名运动员报名参加a、b、c、d、e、f六个项目的比赛。如下表所示，打六个项目

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

4、通图是树图。的连通图是树图。2. 树图和图的最小部分树树图和图的最小部分树v图的最小部分树图的最小部分树 如果如果g1是是g2的部分树，又是树图，则称的部分树，又是树图，则称g1是是g2的部分的部分树（或支撑树）。树（或支撑树）。 树图的各条边称为树枝，一般图含有多个部分树，其树图的各条边称为树枝，一般图含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树。中树枝总长最小的部分树，称为该图的最小部分树。 定理定理1：图中任一个点：图中任一个点i，若，若j是与是与i相邻点中距离最近的，相邻点中距离最近的，则边则边i，j一定必含在该图的最小部分树内。一定必含在该图的最小部分树内。 推论：

5、把图的所有点分为推论：把图的所有点分为v和和v两个集合，则两集合之两个集合，则两集合之间连线的最短边一定包含在最小部分树内。间连线的最短边一定包含在最小部分树内。de避避圈圈法法【例】如下图所示，【例】如下图所示，s、a、b、c、d、e、t代表村镇，代表村镇，它们间连线表明村镇间现有道路交通情况，连线旁数字代它们间连线表明村镇间现有道路交通情况，连线旁数字代表道路的长度。现要求沿图中道路架设电线，使上述村镇表道路的长度。现要求沿图中道路架设电线，使上述村镇全部同上电，应如何架设使总的路线长度为最短。全部同上电，应如何架设使总的路线长度为最短。bsact254175213574de破破圈圈法法【

6、例】如下图所示，【例】如下图所示，s、a、b、c、d、e、t代表村镇，代表村镇，它们间连线表明村镇间现有道路交通情况，连线旁数字代它们间连线表明村镇间现有道路交通情况，连线旁数字代表道路的长度。现要求沿图中道路架设电线，使上述村镇表道路的长度。现要求沿图中道路架设电线，使上述村镇全部同上电，应如何架设使总的路线长度为最短。全部同上电，应如何架设使总的路线长度为最短。bsact2541752135743. 最短路问题最短路问题v最短路问题一般来说就是最短路问题一般来说就是从给定的网络图中找出从给定的网络图中找出任意两点之间距离最短的一条路任意两点之间距离最短的一条路。这里的距离只。这里的距离只是

7、权数的代称，在实际的网络图中，权数可以是是权数的代称，在实际的网络图中，权数可以是时间、费用等。时间、费用等。v求解最短路问题有两种算法：求解最短路问题有两种算法： 求从某一点至其它各点之间最短求从某一点至其它各点之间最短距离的距离的狄克斯屈拉狄克斯屈拉（dijkstra）算法；算法； 求网络图上任意两点之间最短距求网络图上任意两点之间最短距离的离的矩阵矩阵算法；算法；狄狄克克斯斯屈屈拉拉算算法法1v2v3v4v5v6v7v5722126643701. l11=02. l1p=minl11+d12, l11+d13=min0+5, 0+2=2=l133. l1p=minl11+d12, l13

8、+d34, l13+d36=min0+5, 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狄狄克克斯斯屈屈拉拉算算法法1v2v3v4v5v6v7v5722126643705. l1p=minl12+d25, l12+d24, l13+d34, l16+d64, l16+d65, l16+d67=min5+7, 5+2, 2+7, 6+2, 6+1, 6+6=7=l14=l156. l1p=minl15+d57, l16+d67=min7+3, 6+6=10 =

9、l172567710【练习【练习】1v2v3v4v5v6v7v465715524168045591016矩矩阵阵算算法法1v2v3v4v5v6v7v57221266437111213141516172122232425262731323334353637(0)4142434445464751525354555657616263646566677172737475767705250272074270dddddddddddddddddddddddddddddddddddddddddddddddddd 627601342106360构造一个新矩阵构造一个新矩阵d（1）, 该矩阵给出了网络中任意两点之

10、间直该矩阵给出了网络中任意两点之间直接到达和包括一个中间点时的最短距离。矩阵接到达和包括一个中间点时的最短距离。矩阵d（1）中每个元中每个元素的计算方式为：素的计算方式为：(1)minijirrjddd(0)05250272074270627601342106360d (1)05271265072741027065410726032812753013644210410108340d一般有矩阵一般有矩阵d（k）给出了网络中任意两点之间直接到达，经过给出了网络中任意两点之间直接到达，经过一个、两个、一个、两个、到（、到（2k-1）个中间点时比较得到的最短距）个中间点时比较得到的最短距离。矩阵离。矩

11、阵d（k）中每个元素的计算方式为：中每个元素的计算方式为：( )(1)(1)minkkkijirrjddd(1)05271265072741027065410726032812753013644210410108340d(2)052776105072548270654872603267553013644210410886340d(3)(2)dd【例】某人购买一台摩托车，准备在今后【例】某人购买一台摩托车，准备在今后4年内使用。他可在第一年初年内使用。他可在第一年初购买一台新车，连续使用购买一台新车，连续使用4年，也可于任何一年末换一台新车。已知各年，也可于任何一年末换一台新车。已知各年初的新车

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

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

14、数学工作者提出，故称为中国邮路问题中国邮路问题。欧拉回路欧拉回路的定义是：连通图的定义是：连通图g中，若存在一条回路，经过每中，若存在一条回路，经过每边一次且仅一次，称这条回路为欧拉回路。称具有欧拉回路边一次且仅一次，称这条回路为欧拉回路。称具有欧拉回路的图为欧拉图。的图为欧拉图。【例【例】设某邮递员设某邮递员负责投递的街道如负责投递的街道如图所示，要求找出图所示，要求找出该邮递员的最短投该邮递员的最短投递路线。递路线。1v2v3v4v5v6v7v8v9v10v11v12v13v44575412454214422连通图连通图g是欧拉图的充分必要条件是图中的点全为是欧拉图的充分必要条件是图中的点

15、全为偶点偶点。（1）每条边上最多重复一次；）每条边上最多重复一次；（2）在图）在图g的每个回路上，有重复边的长度不超过回路总的每个回路上，有重复边的长度不超过回路总长的一半。长的一半。1v2v3v4v5v6v7v8v9v10v11v12v13v445754124542144224. 网络最大流网络最大流v 网络最大流的有关概念网络最大流的有关概念1. 有向图与容量网络有向图与容量网络 有向图上的连线是有规定指向的，称作有向图上的连线是有规定指向的，称作弧弧； 所谓容量网络是指对网络上的每条弧都给出一个所谓容量网络是指对网络上的每条弧都给出一个最大的通过能力，称为该最大的通过能力，称为该弧的容量

16、弧的容量，记为，记为c(vi, vj)或简写或简写cij； 在容量网络中通常规定一个在容量网络中通常规定一个发点发点（记为（记为s）和一个）和一个收点收点（记为（记为t），网络中既非发点又非收点的其它），网络中既非发点又非收点的其它点称为中间点；点称为中间点； 网络最大流网络最大流是指网络中从发点到收点之间允许通是指网络中从发点到收点之间允许通过的最大流量。过的最大流量。4. 网络最大流网络最大流2.流与可行流流与可行流所谓所谓流流是指加在网络各条弧上的一组负载量，记是指加在网络各条弧上的一组负载量，记作作f(vi ,vj)或简写为或简写为fij；若网络上所有的若网络上所有的fij=0，这个流

17、称为，这个流称为零流零流；在容量网络上满足以下条件的一组流称为可行流：在容量网络上满足以下条件的一组流称为可行流：i.容量限制条件，对所有弧有容量限制条件，对所有弧有ii. 中间点平衡条件中间点平衡条件0( ,)( ,)ijijf v vc v v( ,)(,)0 (, )ijjif v vf v v is t4. 网络最大流网络最大流v割和流量割和流量割是指将容量网络中的发点和收点分割开，并使割是指将容量网络中的发点和收点分割开，并使st的流中断的一组弧的集合。的流中断的一组弧的集合。割的容量是组成它的集合中的各弧的容量之和。割的容量是组成它的集合中的各弧的容量之和。st1v2v3v4v9(

18、4)9(9)8(8)7(5)5(4)2(0)6(1)5(5)10(8)st1v2v3v4v9(4)9(9)8(8)7(5)5(4)2(0)6(1)5(5)10(8)vv割割容量容量1234,v v v v t12( ,)( ,)s vs v15s1, s v234,v v v t13122( ,)( ,)( ,)v vv vs v212, s v134,v v v t124( ,)(,)s vv v1712,s v v34,v v t1324( ,)(,)v vv v1813,s v v24,v v t332122( , )( ,)( ,)( ,)v t v vv vs v1924,s v v

19、13,v v t1434( ,)(,)(, )s vv vv t24123,s v v v4,v t243(,)( , )v vv t14124,s v v v3,v t13434( ,)(,)(, )v vv vv t251234,s v v v vt34( , )(, )v t v t154. 网络最大流网络最大流v最大流最小割定理最大流最小割定理如果在网络的发点和收点之间能找到一条链，在这条如果在网络的发点和收点之间能找到一条链，在这条链上所有指向为链上所有指向为st的弧（称为的弧（称为前向弧前向弧，记作，记作 + +），），存在存在f0，这样的链称为，这样的链称为增广链增广链。11fc

20、20f 30f 44fc55fcst4. 网络最大流网络最大流v最大流最小割定理最大流最小割定理当增广链存在时，找出当增广链存在时，找出再令再令定理：定理：在网络中在网络中st的最大流量等于它的最小割集的的最大流量等于它的最小割集的容量容量。()min0iiicf f对对对对iiiffff 对对所所有有对对所所有有对对非非增增广广链链上上的的弧弧4. 网络最大流网络最大流vford-fulkerson标号算法标号算法1.首先给发点首先给发点s标号标号 。括弧中的第一个数字是。括弧中的第一个数字是使这个点得到标号的前一个点的代号；括弧中的第使这个点得到标号的前一个点的代号；括弧中的第二个数字表示

21、从上一个标号到这个标号点的流量的二个数字表示从上一个标号到这个标号点的流量的最大允许调整值。最大允许调整值。2.列出与已标号点相邻的所有未标号点：列出与已标号点相邻的所有未标号点：i. 考虑从已标号点考虑从已标号点i出发的弧（出发的弧（i，j）：）：(0, ( )sijijfcj点不标号点不标号ijijfcj点标号点标号( , ( )ij( )min ( ),()ijijjicf2.列出与已标号点相邻的所有未标号点：列出与已标号点相邻的所有未标号点：ii.考虑所有指向已标号点考虑所有指向已标号点i的弧（的弧（h，i）：）：iii.如果某未标号点如果某未标号点k有两个以上相邻的标号点，为减少迭有

22、两个以上相邻的标号点，为减少迭代次数，可按代次数，可按i、ii中所述规则分别计算出中所述规则分别计算出 的值，的值，并取其中最大的一个标记。并取其中最大的一个标记。3.重复第重复第2步，可能出现两种结局：步，可能出现两种结局：i.标号过程中断，标号过程中断，t得不到标号，说明网络中不存在增广得不到标号，说明网络中不存在增广链，给定的流量即为最大流。记已标号点的集合为链，给定的流量即为最大流。记已标号点的集合为v,未未标号点集合为标号点集合为v，（，（v，v）为网络的最小割；）为网络的最小割；ii.t点得到标号，反向追踪找出增广链；点得到标号，反向追踪找出增广链；0hifh点不标号点不标号0hi

23、fh点标号点标号( , ( )ih( )min ( ),hihif( )k4.修改流量，设图中原有可行流为修改流量，设图中原有可行流为f，按一下方式获得，按一下方式获得新的可行流新的可行流f：5.抹掉图中所有标号，重复第抹掉图中所有标号，重复第1到第到第4步，直至图中找步，直至图中找不到任何增广链，即出现第不到任何增广链，即出现第3步的结局步的结局i为止，这时为止，这时网络图中的流量即为最大流。网络图中的流量即为最大流。( )( )ftfftf 对对增增广广链链上上所所有有前前向向弧弧对对增增广广链链上上所所有有后后向向弧弧所所有有非非增增广广链链上上的的弧弧st1v2v3v4v9(4)9(9

24、)8(8)7(5)5(4)2(0)6(1)5(5)10(8)(0,)( ,2)s2(,2)v1( ,2)v3( ,1)v4(,1)vst1v2v3v4v9(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)(0,)( ,1)s2(,1)v1( ,1)v(0,)最小割最小割最大流：最大流：14324( , ),(,)v tv vst1v2v3v4v5v5(5)6(4)3(3)5(4)2(0)3(3)3(2)4(4)2(2)2(0)8(6)6(6)st1v2v3v4v5v5(5)6(5)3(3)5(5)2(0)3(2)3(3)4(4)2

25、(1)2(0)8(7)6(6)(0,)( ,2)s2(,1)v5(,1)v3( ,1)v1( ,1)v4(,1)v(0,)( ,1)s最小割最小割最大流：最大流：131325(,),(,),(,)ssvvvv vvdbceaf1234567891011 1213【例】某河流中有【例】某河流中有4个岛屿，从两岸至各岛屿及各岛屿之间个岛屿，从两岸至各岛屿及各岛屿之间的桥梁编号如图所示，在一次敌对的军事行动中，问至少应的桥梁编号如图所示，在一次敌对的军事行动中，问至少应炸断哪几座桥梁，才能完全切断两岸的交通联系？炸断哪几座桥梁，才能完全切断两岸的交通联系？dbceaf1234567891011 12

26、13abcdef221211113abcdef2(1)21(1)2(1)1111(1)3(1)abcdef2(1)21(1)2(1)1111(1)3(1)(0,)( ,1)a( ,2)a( ,1)b( ,1)d( ,1)eabcdef2(2)21(1)2(2)111(1)1(1)3(2)(0,)( ,2)a( ,1)c( ,1)d最小割：最小割：(d, f), (d, e), (a, e)dbceaf1234567891011 12135. 最小费用流最小费用流v最小费用流问题最小费用流问题对于容量网络，除考虑各条弧上的流量、容量外，对于容量网络，除考虑各条弧上的流量、容量外，还需考虑弧上通过

27、单位流量时的费用（还需考虑弧上通过单位流量时的费用（bij），保），保证最终给出的流量或最大流也是费用最少的。证最终给出的流量或最大流也是费用最少的。关键点：确定关键点：确定“最小费用增广链最小费用增广链”。st1v2v3v(5, 8)(8, 7)(2, 5)(4, 9)(10, 9)(3, 2)(8, 4)【例】各弧旁数字【例】各弧旁数字为为(cij, bij)，试求图，试求图中从中从st的最小费的最小费用最大流。用最大流。1.从原容量网络的零流从原容量网络的零流f0开始；开始；2.对原容量网络的可行流对原容量网络的可行流fk构造构造加权网络加权网络w(fk):对对0fijcij的弧的弧(i

28、, j)，在加权网络的，在加权网络的i点和点和j点之间分别绘制弧点之间分别绘制弧(i, j)和和(j, i)，其权数分别为，其权数分别为bij和和-bij；对对fij=cij的弧，在加权网络的的弧，在加权网络的i点和点和j点之间绘制弧点之间绘制弧(j, i)，其权数为，其权数为-bij；对对fij=0的弧，在加权网络的的弧，在加权网络的i点和点和j点之间绘制弧点之间绘制弧(i, j)，其权数为，其权数为bij。3.确定最小费用增广链等价于求解加权网络确定最小费用增广链等价于求解加权网络st之间的最之间的最短路。找出增广链之后调整原容量网络的流量；短路。找出增广链之后调整原容量网络的流量；4.重

29、复重复2、3步骤，直到步骤，直到st之间找不出最短路为止，此时之间找不出最短路为止，此时求得原容量网络的最小费用最大流。求得原容量网络的最小费用最大流。5. 最小费用流最小费用流st1v2v3v(5, 8)(8, 7)(2, 5)(4, 9)(10, 9)(3, 2)(8, 4)1vt2v3vs87599240781014st1v2v3v5(3)8(0)2(0)4(0)10(0)3(3)8(3)st1v2v3v(5, 8)(8, 7)(2, 5)(4, 9)(10, 9)(3, 2)(8, 4)st1v2v3v5(3)8(0)2(0)4(0)10(0)3(3)8(3)1vt2v3vs875994-8-2-412312308780950920440 s v v v tsvvvt(0)d(1)d(2)d12312308716178015935091310204640 s v v v tsvvvt123123087131780159350913102304146740 s v v v tsvvvt1vt2v3vs875994-8-2-4st1v2v3v5(3)8(0)2(0)4(0)10(0)3(3)8(3)st1v2v3v5(5)8(0)2(0)4(2)10(0)3(3)8(3)1vt2v3vs875994-8-2-4st1v2v3v(5, 8)(8, 7)(2,