运筹学第五章图与网络分析

1、第章图与网络分析第章图与网络分析u.基本概念基本概念u.最小支撑树问题最小支撑树问题u.最短路问题最短路问题u.最大流问题最大流问题5. 基本概念基本概念1.1.图图、子图、子图与简单图与简单图u图：图：由节点和线组成的图形由节点和线组成的图形 记为：记为： G = ( V, E ) G = ( V, E ) V=v V=v1 1,v,v2 2,v vm m节点集节点集, ,表示研究对象表示研究对象. . E=eE=e1 1,e,e2 2,e,en n边集，表示研究对象之边集，表示研究对象之间的关系间的关系. .e1e2e3e5e6e4e7v3v2v1v411111( ,),GV EVV EE

2、其中。e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4图图u子图：子图：图的一部分，记为图的一部分，记为u多重边多重边：两节点之间有多于一条边。：两节点之间有多于一条边。u环：环：首尾相接的边首尾相接的边u简单图：简单图：无环、无多重边的图。无环、无多重边的图。2.有向图与无向图有向图与无向图v有向图有向图：有方向的图。：有方向的图。v无向图无向图：无方向的图。：无方向的图。 e1 V2 V1 e2 V3 v1 e v23.关联与相邻关联与相邻v关联关联(边与节点的关系边与节点的关系):若若e是是v1、v2两节点间两节点间 的边，记的边，记e=v1，v2 ，称称

3、v1、v2 与与e关联关联。v相邻相邻（边与边、节点与节点的关系）：（边与边、节点与节点的关系）： 点点v1与与v2有公共边，称节点有公共边，称节点v1与与v2相邻相邻； 边边e1与与e2 有公共节点，称边有公共节点，称边e1与与e2相邻相邻。圈圈 封闭的链称为封闭的链称为圈圈如：如：=(1,2),(2,4),(3,4),(1,3 链链:由图由图G中的某些相连的边构成的图形（首尾中的某些相连的边构成的图形（首尾不能相接），称为图不能相接），称为图G中的一条中的一条链链。 如：如： =(1,2),(3,2),(3,4)4. 链、圈与连通图链、圈与连通图42314231连通图连通图 任意两个节点之

4、间至任意两个节点之间至少有一条链的图称为少有一条链的图称为连连通图通图42315.网络图网络图 给图中的节点和边赋以给图中的节点和边赋以具体的含义和权数（如距离具体的含义和权数（如距离、时间、费用、容量等），、时间、费用、容量等），则称这样的连通图为则称这样的连通图为网络图网络图。4231 50 70 20 45v典例: 会议日程安排某单位要在今后的三天内召开6个会议,每天上下午各安排一个会议，参加会议的领导如下会议A: 朱、马、牛、姬、江、姚会议B: 朱、杨、张、江会议C: 马、姬、侯、王、姚会议D: 朱、姬、张会议E: 杨、侯、王会议F: 刘、杨、王、江、姚每位领导每天最多只参加一个会议。

5、会议A要安排在第一天上午,会议F安排在第三天下午，会议B要安排在任何一天的下午。试根据上述要求排出一个会议日程表，使各位领导都能参加相应的会议ABCDEF会议日程安排如下: 上午 下午第一天 会议A E 第二天 会议C B第三天 会议D F 解: 用节点表示会议，若两个会议能安排在一天， 则用连线连接。5.2 最小支撑树问题最小支撑树问题C1C2C3C4根根叶叶v树：无圈的连通图，记为树：无圈的连通图，记为T。v树的性质树的性质243512435124351如果树如果树T有有m个节点，则个节点，则边的个数为边的个数为m-1。 树中任意两个节点间有树中任意两个节点间有且只有一条链且只有一条链。

6、在树中任意去掉一条边，在树中任意去掉一条边，则不连通则不连通。v图的支撑树图的支撑树图图G1和和G2 的节点相同，但图的节点相同，但图G1边的集合边的集合包包含于含于G2边的集合，且边的集合，且 G1是树图，则是树图，则 图图G1是是G2 的支撑树。的支撑树。一个图的支撑树不是唯一的。一个图的支撑树不是唯一的。图 G1图 G2v最小支撑树 树枝总长最短的支撑树。特点：各节点都连通且线路总长最短v最小支撑树的求法1 破圈法2 避圈法5.2.1 求解最小支撑树问题的破圈法求解最小支撑树问题的破圈法v方法：去边破圈的过程。方法：去边破圈的过程。v步骤步骤：1）在给定的赋权的连通图上任找）在给定的赋权

7、的连通图上任找 一一 个圈。个圈。 2）在所找的圈中去掉一条权数最）在所找的圈中去掉一条权数最 大的边。大的边。 3）若所余下的图已不含圈，则计）若所余下的图已不含圈，则计 算结束，余下的图即为最小支撑算结束，余下的图即为最小支撑 树，否则返回树，否则返回 1）。）。v例：用破圈法求右图例：用破圈法求右图 的最小支撑树。的最小支撑树。V4V2V3V13 7 4 5 8 1V4V2V3V1V1V4V2V3V4V2V3V1V4V2V3V1总权数总权数=3+4+1=85.2.2 求解最小支撑树的避圈法求解最小支撑树的避圈法v方法：选边的过程。方法：选边的过程。v步骤：步骤：1）从网络中任意选一点）从

8、网络中任意选一点vi，找出找出与与vi相关联的权最小的边相关联的权最小的边vi,vj，得第二个得第二个顶点顶点vj。 2）把顶点集）把顶点集V分为互补的两部分分为互补的两部分A,，其中：其中： A：与已选边相关联的点集与已选边相关联的点集 ：不与已选边相关联的点集不与已选边相关联的点集 3) 考虑所有这样的边考虑所有这样的边vi,vj，其中其中viA,vj,挑选其中权最小的。挑选其中权最小的。 4）重复）重复3），直至全部顶点均属于），直至全部顶点均属于A即即可。可。v例：用避圈法求图的最小例：用避圈法求图的最小 支撑树。支撑树。V4V2V3V13 7 4 5 8 1任选点任选点v1，挑与之相

9、关挑与之相关联的权最小的边（联的权最小的边（ v1,v4）.A= v1,v4,=v2,v3 从边（从边（ v1,v2）,（ v1,v3）, （ v4,v2）, （ v4,v3） 中选权最小的边（中选权最小的边（ v1,v2）。）。V4V2V3V13 7 4 5 8 1A= v1,v2 ,v4,=v3 从边（从边（ v1,v3）, （ v2,v3）, （ v4,v3） 中选中选权最小的边（权最小的边（ v2,v3）。）。 A= v1,v2 , v3， v4l网络的生成树和线性规划的关系网络的生成树和线性规划的关系网络的一个生成树对应于线性规划的网络的一个生成树对应于线性规划的一个基一个基生成树上

10、的边对应于线性规划的基变生成树上的边对应于线性规划的基变量量生成树的弦对应于线性规划的非基变生成树的弦对应于线性规划的非基变量量生成树的变换对应于线性规划单纯形生成树的变换对应于线性规划单纯形法的进基和离基变换法的进基和离基变换71425673734243562412破圈法举例避圈法举例1425673734243562412例例 校园局域网问题校园局域网问题某大学准备把所属个学院办公室的计某大学准备把所属个学院办公室的计算机联网这个网络的可能联通的途径算机联网这个网络的可能联通的途径如图所示边上权数为这条边的长度，如图所示边上权数为这条边的长度，单位为百米试设计一个网络联通个单位为百米试设计一

11、个网络联通个学院办公室，并使总长度为最短学院办公室，并使总长度为最短v1v4v5v3v7v6v2513724843103v1v4v5v3v7v6v2137233权和权和例例 电话线网架设问题电话线网架设问题某个城市之间的道路网如图所示要某个城市之间的道路网如图所示要求沿着已知长度的道路联结个城市的求沿着已知长度的道路联结个城市的电话线网，并使电话线的总长度最短电话线网，并使电话线的总长度最短v1v4v2v6v5v3617524453v1v4v2v6v5v312453权和权和5.3 最短路问题最短路问题问题：求网络中一定点到其它点的最短路。问题：求网络中一定点到其它点的最短路。5.3.1 最短路

12、问题的最短路问题的Dijstra解法解法方法：给方法：给vi点标号点标号i,vk 其中：其中：i：vi点到起点点到起点vs的最短距离的最短距离 vk: vi的前接点的前接点方法：方法：(1) 给起点给起点vs标号标号0，vs。（2）把顶点集）把顶点集v分为互补的两部分分为互补的两部分A和和 其中：其中：A：已标号点集：已标号点集 ：未标号点集：未标号点集 （3）考虑所有这样的边）考虑所有这样的边vi, vj, 其中其中vi A,vj 挑选其中与挑选其中与vs距离最短的点距离最短的点vj标号标号 mini+cij,vi(4) 重复（重复（3），直至终点），直至终点vt标上号标上号t,vk，则，则

13、 t即为即为vs至至vt的最短距。的最短距。反向追踪可求得最短路。反向追踪可求得最短路。例：求例：求v1至至v8的最短路。的最短路。v2v3v7v1v8v4v5v66134105275934682v2v3v7v1v8v4v5v66134105275934682(1) v1:0,v1计算min 0+2, 0+1, 0+3 = min 2,1,3=1 v4:1.v11,v10,v1(2)A=v1检查边（v1,v2),(v1,v4),(v1,v3)v2v3v7v1v8v4v5v66134105275934682(3)A=v1,v4计算 min0+2, 0+3, 1+10, 1+2=min 2,3,1

14、1,3 =2 v2:2,v10,v11,v12,v1考虑边（考虑边（v1,v2),(v1,v6),(v4,v2),(v4,v7)v2v3v7v1v8v4v5v66134105275934682（4）A=v1,v2,v4 计算计算min 0+3, 2+6, 2+5, 1+2 v6:3,v1 =min 3,8,7,3=3 2,v11,v10,v13,v1考虑边（考虑边（v1,v6),(v2,v3),(v2,v5),(v4,v7)v2v3v7v1v8v4v5v66134105275934682(5)A=V1,V2,V4,V6计算计算 min 2+6, 2+5, 1+2, 3+4=min 8,7,3,

15、7=3 v7:3,v42，V11，V10，V13，V13,v4考虑边考虑边(v2,v3),(v2,v5),(v4,v7),(v6,v7)V2V3V7V1V8V4V5V66134105275934682(6)A=V1,V2,，V4,V6,V7计算计算min 2+6, 2+5, 3+3, 3+8=min 8,7,6,11=6 v5:6,v72,v11,v10,v13,v13,v46,v7考虑边考虑边(v2,v3),(v2,v5),(v7,v5),(v7,v8)v2v3v7v1v8v4v5v66134105275934682(7)A=V1,V2,V4,V6,V7计算min 2+6, 6+9, 6+4

16、, 3+8=min 8,15,10,11=8 v3:8,v22,V11,V10,V13,V13,V46,V78,v2考虑边考虑边(v2,v3),(v5,v3),(v5,v8),(v7,v8)v2v3v7v1v8v4v5v66134105275934682(8)A=v1,v2,v3,v4,v6,v7 计算 min 8+6, 6+4, 3+7=min 14,10,11=10 v8:10,v52,v11,v10,v13,v13,v46,v78,v210,v5考虑边（考虑边（v3,v8),(v5,v8),(v7,v8)v2v3v7v1v8v4v5v66134105275934682(9)A=v1,v2

17、,v3,v4,v6,v7,v8v1到到v10的最短路径为的最短路径为v1v4v7v5v8，最短路长度，最短路长度为为10。2,v11,v10,v13,v13,v46,v78,v210,v5反向追踪：反向追踪：v8-v5-v7-v4-v1例例6 设备更新问题设备更新问题某厂使用一种设备，每年年初设备科需要对该设某厂使用一种设备，每年年初设备科需要对该设备的更新与否作出决策。五年内：备的更新与否作出决策。五年内：购买新设备购买新设备-购置费；购置费；13，14，16，19，24；使用老设备使用老设备-维护费。维护费。8，10，13，18，27。问：在问：在5年内如何制定更新计划，以便使新设备年内如

18、何制定更新计划，以便使新设备购置费和老设备维修费的总费用最小？购置费和老设备维修费的总费用最小？341245632131323244622489224563473727v1-v3-v6minL=78例例7 7火车调度问题火车调度问题某火车货运调车场，主要调运建筑材料中某火车货运调车场，主要调运建筑材料中的黄沙、碎石和水泥。该调车场有的黄沙、碎石和水泥。该调车场有3 3个装运个装运点：黄沙装运点、碎石装运点和水泥装运点：黄沙装运点、碎石装运点和水泥装运点；另有点；另有2 2个机车挂钩处（挂火车头的地方个机车挂钩处（挂火车头的地方），即图），即图1 1中的节点中的节点1 1、2 2、5 5和和9

19、9、1010。货运。货运火车的各节车厢在一个装运点装货后，必火车的各节车厢在一个装运点装货后，必须由调车场的火车头把装好货的车厢拉走须由调车场的火车头把装好货的车厢拉走，按调车场的铁路网络的某一路线运行到，按调车场的铁路网络的某一路线运行到某一机车挂钩处，由那里的火车头把满载某一机车挂钩处，由那里的火车头把满载的车厢拉走。网络图中，各条弧代表铁路的车厢拉走。网络图中，各条弧代表铁路线，节点代表铁路交叉口，弧旁的线，节点代表铁路交叉口，弧旁的数字代数字代表距离（单位：百米），这里需注意表距离（单位：百米），这里需注意的是，网络图只是描述了各换轨点的是，网络图只是描述了各换轨点(即即交叉口）、装运

20、点和机车挂钩处之间交叉口）、装运点和机车挂钩处之间的关系，并不表示铁路线的实际走向。的关系，并不表示铁路线的实际走向。调车场的调度室需要解决的问题是：调车场的调度室需要解决的问题是：各车厢在某一装运点装好货后应把它各车厢在某一装运点装好货后应把它拉到哪一个机车挂钩处，而且应走哪拉到哪一个机车挂钩处，而且应走哪一条运行路线最短，从而提高调车场一条运行路线最短，从而提高调车场作业的效率，减少装载的车厢等候挂作业的效率，减少装载的车厢等候挂钩时间而尽快拉离调车场。钩时间而尽快拉离调车场。分别求出结点分别求出结点1、2、5到结点到结点9和和10的最短路径的最短路径及最小路径值。及最小路径值。 结果分析

21、结果分析黄沙装运点、水泥装运点、碎石装运点到两个机车黄沙装运点、水泥装运点、碎石装运点到两个机车挂钩处的最短路径及最短路径值，如下挂钩处的最短路径及最短路径值，如下 30 30； 35 35； 27 27； 32 32； - 19 19； - 24 245. 最大流问题最大流问题v2v3v5v4v6v7v1f=0f=062 4 74 3 79 3188l问题的一般提法：问题的一般提法： 有一网络有一网络D=(V,A;C) 其中其中V：点集；：点集；A：弧集；：弧集；C=cij,cij为弧为弧（vi,vj)上的容量。上的容量。 现现D上要安排通过一个流上要安排通过一个流f=fij，其中，其中fi

22、j为为弧弧(vi,vj)上的流量。上的流量。问题：如何安排流量问题：如何安排流量fij，可使，可使D上通过上通过 的总流量的总流量V(f)最大？最大？5.4.1 网络流的基本概念与基本定理网络流的基本概念与基本定理(1)弧的容量和流量弧的容量和流量容量容量cij，流量流量fij(2)可行流可行流a、每一个节点流量平衡、每一个节点流量平衡b、0fij cij1.弧的容量和流量、可行流jifij=5cij=5jifij=3cij=52. 饱和弧、不饱和弧、流量的间隙（i，j）是饱和的）是饱和的(2)如果如果fij0，弧从弧从j到到i的方向是不饱和的；的方向是不饱和的；（j，i）是不饱和的）是不饱和

23、的间隙为间隙为 ij=fij=53.可增广链（或可扩充链）可增广链（或可扩充链）网络网络D中中st的链，记为的链，记为 +：前向弧（与：前向弧（与方向一致）方向一致） -：后向弧（与：后向弧（与方向相反）方向相反） 若链若链 上的流量满足：所有的前向弧皆未饱和，后向上的流量满足：所有的前向弧皆未饱和，后向 弧皆非零，则称弧皆非零，则称为为D中关于可行流中关于可行流fij的可增广链。的可增广链。(4,2) (3,1) (5,3) (4,1) (3,2)4.截集与截量截集与截量l截集：将网络图中的起点与终点分开并截集：将网络图中的起点与终点分开并使流中断的一组正向弧的集合。使流中断的一组正向弧的集

24、合。 即将顶点即将顶点V分为二个非空互补集分为二个非空互补集E和和 ，使，使s s E,t ,称弧集称弧集（ E，)= (i,j) | i E,j 为为D的截集。的截集。l截量：截集上的容量之和。记为截量：截集上的容量之和。记为C(E, ).5.流量与截量的关系流量与截量的关系n任何一个可行流的流量任何一个可行流的流量V(f)都不会超过任一都不会超过任一截量。即截量。即V(f) C(E, )n最大流最大流-最小截定理：最小截定理：max V(f) = minC(E, )n判别最大流的条件：可行流判别最大流的条件：可行流f是最大流是最大流 D中不存在关于中不存在关于f 的可增广链的可增广链5.4

25、.2 最大流问题的标号解法最大流问题的标号解法步骤：先找一个可行流步骤：先找一个可行流检验检验调整调整算法步骤：算法步骤：1.标号找可增广链标号找可增广链（1）给）给vs标号标号,v vs s,选与选与v vs s相关联的流出未饱相关联的流出未饱和弧和弧( (v vs s,v,vi i) ) ，给，给v vi i标号标号 i i,v,vs s. 其中其中i i= csisi-fsisi（3）考虑所有这样的弧）考虑所有这样的弧(vi,vj),其中其中 viE,vj（2）点集点集V=E，其中，其中 E：已标号点集：已标号点集 ：未标号点集：未标号点集若若(vi,vj)为流出未饱和弧，则为流出未饱和

26、弧，则vj:j , v, vi j=mincij-fij, i若若(vi,vj)为流入非为流入非0弧，则弧，则vj:j , -vi j=min fij, i (4)直到终点已标号为止直到终点已标号为止,反向追踪便得可增反向追踪便得可增广链广链. 若未标到终点若未标到终点,但已标不下去，说明网络但已标不下去，说明网络D中不存在可增广链，便得最大流中不存在可增广链，便得最大流maxV(f),同时同时得得 到最小截集到最小截集min(E，).2.调整流量：调整流量：选择一条可增广链选择一条可增广链, ,调整流量。调整流量。 f fij ij+ + t t ( (v vi i,v,vj j)+f fi

27、j ij = = f fij ij- - t t ( (v vi i,v,vj j)- - f fij ij 其其它它调调整后得到新的整后得到新的网络图网络图, ,重重复复步步骤骤1.1.例：用标号法求下面网络的最大流。 vs v1 v3 V2 v4vt(4,3)(3,3) (1,1) (5,3)(1,1) (3,0)(5,1) (2,1)(2,2)1.标号找可增广链标号找可增广链(1) vs:,v,vs v v1:4,v:4,vs (2) E=v(2) E=vs,v,v1 v v2:1,-v:1,-v1 (3) E=v(3) E=vs,v,v1,v,v2 v v4:1,v:1,v2 v v3

28、:1,-v:1,-v2 vs v1 v3 v2 v4vt(4,3) (3,3) (1,1) (5,3) (1,1) (3,0) (5,1) (2,1)(2,2),v vs 4,vs1,-v11,v21,-v2(4)E=vs,v1,v2,v3,v4 vt:1,v4 1,v3可增广链：可增广链： vt-v4-v2-v1-vs vt-v3-v2-v1-vs1,v4 1,v32.调整流量调整流量(选择一条可增广链选择一条可增广链:vs-v1-v2-v4-vt)调整量调整量 t调整后得到调整后得到新流量图新流量图.再标号找增广链再标号找增广链(1) vs:,vs v1:,vs(2)E=vs,v1,但是标

29、号不能进行下去，说明网络图但是标号不能进行下去，说明网络图中已不存在可增广链，即当前流为最大流。中已不存在可增广链，即当前流为最大流。.maxv(f)=3+2=4+1=5 vs v1 v3 v2 v4vt(4,4) (1,0) (3,0)(2,2),v vs s 3,vs(3,3) (1,1) (5,4) (5,2) (2,1)5.min(E,5.min(E,)=(v)=(vs s,v,v2 2) )，(v(v1 1,v,v3 3) minc(Eminc(E, , )=3+2=5)=3+2=5例例10：求结点：求结点v1至结点至结点v v7的最大流的最大流，同时写出其最小截集及截量。，同时写出

30、其最小截集及截量。v2v3v5v4v6v7v1f=0f=062 4 74 3 79 3188解：解：（1）给出一个可行流给出一个可行流f=0， 找到一条从找到一条从v1到到v7的可增广链的可增广链可增广链为：可增广链为：v7-v6-v3-v1；可调整流量为：；可调整流量为： =1调整链的流量：调整链的流量：xij=xij+ ；f=f+1=1v2v3v5v4v6v7v1f=0f=0(6,0)(2,0)(4,0)(7,0)(4,0)(3,0)(7,0)(9,0)(3,0)(1,0)(8,0)(8,0)，v18,v13,v21,v31,v6（2）调整流量f=1,继续求出网络的一条可增广链。v2v3v

31、5v4v6v7v1f=1f=1(6,0)(3,1)(7,0)(9,0)(2,0)(4,0)(4,0)(3,0)(7,0)(8,1)(1,1)(8,1)可增广链为：可增广链为：v7-v5-v2-v3-v1;可调整流量为：可调整流量为： =1； 调调整链的流量为：整链的流量为： xij=xij+1; f=f+1=2,v17,v12,-v32,v22,v5(3)调整流量f=2,继续求出网络的一条可增广链.v2v3v5v4v6v7v1f=2f=2(6,1)(3,0)(7,1)(9,1)(2,0)(4,0)(4,0)(3,0)(7,0)(8,1)(1,1)(8,1),v17,v15,v25,v5可增广链

32、为：可增广链为：v7-v5-v2-v1;可调整流量为：可调整流量为： =5； 调整调整链的流量为：链的流量为： xij=xij+5, f=f+5=2+5=7(4)调整流量f=7,继续求出网络的一条可增广链.v2v3v5v4v6v7v1f=7f=7(6,6)(3,0)(7,1)(9,6)(2,0)(4,0)(4,0)(3,0)(7,0)(8,1)(1,1)(8,6),v13,v56,v14,v34,v4可增广链为：v7-v5-v4-v3-v1;可调整流量为：=3, 调整链上的流量为： xij=xij+3, f=f+3=7+3=10(5)调整流量f=10,继续求出网络的一条可增广链.v2v3v5v

33、4v6v7v1f=10f=10(3,0)(7,4)(9,9)(2,0)(4,3)(4,3)(3,0)(7,0)(8,1)(8,6),v13,v61,v33,v13,v4(6,6)可增广链为：v7-v6-v4-v3-v1;可调整流量为：=1； 调整链上的流量为： xij=xij+1, f=f+1=10+1=11(1,1)(6)调整流量f=11,继续求出网络的一条可增广链.v2v3v5v4v6v7v1f=11(3,0)(7,5)(9,9)(2,0)(4,4)(4,3)(3,1)(7,0)(8,2)(8,6),v13,v1(6,6)f=11(1,1)2,v1网络已不存在可增广链，因此，当前流达到网络已不存在可增广链，因此，当前流达到最大流。最大流。(7)已求得最大流 f=11v2v3v5v4v6v7v1f=11(6,6)(2,0)(