第6章_网络模型.ppt

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

1、第第6 6章章 网络模型网络模型6.1 图论导引图论导引6.2 网络中的流网络中的流6.3 最短路和最小费用流问题最短路和最小费用流问题6.4 网络计划方法网络计划方法6.5 应用实例应用实例6.1 图论导引图论导引什么是图什么是图?哥尼斯堡七桥示意图哥尼斯堡七桥示意图问题问题1(1(哥尼斯堡七桥哥尼斯堡七桥问题问题):):能否从任一陆地出发通过每座桥恰好一次而能否从任一陆地出发通过每座桥恰好一次而回到出发点？回到出发点？ABDC七桥七桥问题模拟图问题模拟图欧拉指出：欧拉指出：如果每块陆地所连接的桥都是偶数座，则如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而从任一

2、陆地出发，必能通过每座桥恰好一次而回到出发地回到出发地.问题问题2(2(设备更新问题设备更新问题)某企业每年年初某企业每年年初,都要作出决定都要作出决定,如果继续使如果继续使用旧设备用旧设备,要付维修费；若购买一台新设备要付维修费；若购买一台新设备,要付要付购买费购买费.试制定一个试制定一个5 5年更新计划年更新计划,使总支出最少使总支出最少.已知设备在每年年初的购买费分别为已知设备在每年年初的购买费分别为11,11,11,11,12,12,13.12,12,13.使用不同时间设备所需的维修费分别使用不同时间设备所需的维修费分别为为5,6,8,11,18.5,6,8,11,18.第第1年年第第

3、2年年第第3年年第第4年年第第5年年购买费购买费1111121213维维修修费费5681118第第1年年第第2年年第第3年年第第4年年第第5年年购买费购买费1111121213维修费维修费5681118点点vi表示表示第第i 年年年年初购进一初购进一台新设备台新设备,虚设一个虚设一个点点v6表示表示第第5 5年年年年底底.弧上的数字表示弧上的数字表示一一台设备的购买费与台设备的购买费与维修费之和维修费之和.59=11+5+6+8+11+1841=11+5+6+8+1130=11+5+6+823=12+5+616=11+522=11+5+6 这样上述设备更新问题就变为：求这样上述设备更新问题就变

4、为：求v1到到v6的最短路问题的最短路问题.问题问题3(3(选址问题选址问题)现准备现准备在在 n 个个居民点居民点v1,v2,vn中设置一中设置一银行银行.问设在哪个点问设在哪个点,可使最大服务距离最小可使最大服务距离最小?若若设置两个银行设置两个银行,问设在哪两个点问设在哪两个点?问题问题4(4(关键路径问题关键路径问题)一项工程任务一项工程任务,大到建造一座大坝大到建造一座大坝,一座体育中心一座体育中心,小至组装一台机床小至组装一台机床,一架电视机一架电视机,都要包括许多工序都要包括许多工序.这这些工序相互约束些工序相互约束,只有在某些工序完成之后只有在某些工序完成之后,下一道工序下一道

5、工序才能开始才能开始.即它们之间存在完成的先后次序关系即它们之间存在完成的先后次序关系,一般认一般认为这些关系是预知的为这些关系是预知的,而且也能够预计完成每道工序所而且也能够预计完成每道工序所需要的时间需要的时间.这时工程领导人员迫切希望了解最少需要多这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目少时间才能够完成整个工程项目,影响工程进度影响工程进度的要害工序是哪几道？的要害工序是哪几道？6.1.1 6.1.1 图论的基本概念图论的基本概念 图论中的图论中的“图图”并不是通常意义下的几何图并不是通常意义下的几何图形或物体的形状图形或物体的形状图,而是以一种抽象的形式来表而

6、是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统达一些确定的事物之间的联系的一个数学系统.定义定义1 一个有序二元组一个有序二元组(V,E)称为一个称为一个图图,记为记为G=(V,E),其中其中 V称为称为G的顶点集的顶点集,V,其元素称为其元素称为顶点顶点或或结点结点,简称简称点点;E称为称为G的边集的边集,其元素称为其元素称为边边,它联结它联结V 中的两个点中的两个点,如果这两个点是无序的如果这两个点是无序的,则称该边则称该边为为无向边无向边,否则否则,称为称为有向边有向边.有向边常称为有向边常称为弧弧.如果如果V=v1,v2,vn是有限非空点集是有限非空点集,则则称称G为为

7、有限图有限图或或n阶图阶图.如果如果E的每一条边都是无向边的每一条边都是无向边,则称则称G为为无向无向图图(如图如图1)1);如果如果E的每一条边都是有向边的每一条边都是有向边(即即弧弧),则称则称G为为有向图有向图(如图如图2)2);否则否则,称称G为为混合图混合图.图图1 1图图2 2 教材教材上将有向上将有向图记为图记为D=(V,A)并且常记并且常记V=v1,v2,vn,|V|=n;E=e1,e2,em(ek=vivj),|E|=m.称点称点vi,vj为边为边vivj的的端点端点.在有向图中在有向图中,称点称点vi,vj分别为边分别为边vivj的的始点始点和和终点终点.对于一个图对于一个

8、图G=(V,E),人们常用图形来表示人们常用图形来表示它它,称其为称其为图解图解.凡是有向边凡是有向边,在图解上都用箭在图解上都用箭头标明其方向头标明其方向.例如例如,设设V=v1,v2,v3,v4,E=v1v2,v1v3,v1v4,v2v3,v2v4,v3v4,则则G=(V,E)是一个有是一个有4个顶点和个顶点和6条边的图条边的图,G的图解如下图所示的图解如下图所示.一个图会有许多外形不同的图解一个图会有许多外形不同的图解,下面两个下面两个图表示同一个图图表示同一个图G=(V,E)的图解的图解.其中其中V=v1,v2,v3,v4,E=v1v2,v1v3,v1v4,v2v3,v2v4,v3v4

9、.今后将不计较这种外形上的差别今后将不计较这种外形上的差别,而用一个容而用一个容易理解的、确定的图解去表示一个图易理解的、确定的图解去表示一个图.我们今后只讨论我们今后只讨论有限简单图有限简单图：(1)(1)顶点个数是有限的顶点个数是有限的;(2)(2)任意一条边有且只有两个不同的端点任意一条边有且只有两个不同的端点;(3)(3)若是无向图若是无向图,则任意两个顶点最多只有则任意两个顶点最多只有一条边与之相联结一条边与之相联结;(4)(4)若是有向图若是有向图,则任意两个顶点最多只有则任意两个顶点最多只有两条弧与之相联结两条弧与之相联结.当两个顶点有两条弧与之相当两个顶点有两条弧与之相联结时，

10、这两条弧的方向相反联结时，这两条弧的方向相反.如果某个有限图不满足如果某个有限图不满足(2)(3)(4),(2)(3)(4),可在某条可在某条边边(弧弧)上增设顶点使之满足上增设顶点使之满足.定义定义2 若将图若将图G的每一条边的每一条边e都对应一个实数都对应一个实数F(e),则称则称F(e)为该边的为该边的权权,并称图并称图G为为赋权图赋权图(网网络络),记为记为G=(V,E,F).“权权”可根据实际需要可根据实际需要赋予不同的含义，如距离、时间、费用等赋予不同的含义，如距离、时间、费用等.定义定义3 设设G=(V,E)为无向图为无向图,v0,v1,vkV,且且 1ik,vi-1viE,则称

11、则称v0 v1 vk为连接为连接v0 和vk的一条的一条链链.若若G=(V,E)为有向图为有向图,则称链则称链 v0v1vk是一是一条以条以v0为始点为始点vk为终点的为终点的路路.始点和终点相同的始点和终点相同的链或路链或路称为称为圈圈或或回路回路.定义定义4 任意两点之间至少有一条链的图称为任意两点之间至少有一条链的图称为连通图连通图.定义定义5 连通而无圈的图称为连通而无圈的图称为树树,常用常用T表示树表示树.树有以下显而易见的性质：树有以下显而易见的性质：(1)(1)树中任意两顶点间有且仅有一条路树中任意两顶点间有且仅有一条路;(2)(2)在树中任意两个不相邻的顶点间添上一在树中任意两

12、个不相邻的顶点间添上一条边，就得到一个圈条边，就得到一个圈;(3)(3)在树中去掉任意一条边，图就不连通在树中去掉任意一条边，图就不连通;(4)(4)|V|=|E|+1.子图与生成树子图与生成树(支撑树支撑树)设图设图G=(V,E)和和图图G=(V,E),如果如果V V,E E，则称则称G是是G 的一个的一个子子图图.如果如果V=V,E E，则称则称G是是G 的一个的一个生成生成(支撑支撑)子子图图.如果如果G 的一个生成子的一个生成子图图G=(V,E)是树，是树，则则称称G是是G 的一颗的一颗生成生成树树(支撑树支撑树).).例例 一摆渡人欲将一只狼一摆渡人欲将一只狼,一头羊一头羊,一篮菜从

13、一篮菜从河西渡过河到河东河西渡过河到河东.由于船小由于船小,一次只能带一物过一次只能带一物过河，并且狼与羊河，并且狼与羊,羊与菜不能独处羊与菜不能独处.给出渡河方法给出渡河方法.解解：用：用四维四维0-10-1向量表示向量表示(人人,狼狼,羊羊,菜菜)在河在河西岸的状态西岸的状态(在河西岸则分量取在河西岸则分量取1,1,否则取否则取0),0),共有共有24=16 种状态种状态.在河东岸的状态类似记作在河东岸的状态类似记作.由题设由题设,状态状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的是不允许的,从从而对应状态而对应状态(1,0,0,1),(1,1,0,0),(1,0

14、,0,0)也也是不允许的是不允许的.以可以可允许的允许的10个个状态状态向量作为顶点向量作为顶点,将可能互将可能互相转移的状态用线段连接起来构成一个图相转移的状态用线段连接起来构成一个图.根据此图便可找到根据此图便可找到渡河方法渡河方法.(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0)(0,0,0,0)(0,0,0,1)(0,0,1,0)(0,1,0,0)(0,1,0,1)(0,1,0,1)(0,1,0,0)(0,0,1,0)(0,0,0,1)(0,0,0,0)(1,0,1,0)(1,0,1,1)(1,1,0,1)(1,1,1,0)(1,1,1,1)河

15、西河西=(=(人人,狼狼,羊羊,菜菜)河东河东=(=(人人,狼狼,羊羊,菜菜)将将10个顶点分别记为个顶点分别记为A1,A2,A10,则则渡河渡河问题化为在该图中求一条从问题化为在该图中求一条从A1到到A10的的路路.从图中易得到两条从图中易得到两条路路：A1 A6 A3 A7 A2 A8 A5 A10;A1 A6 A3 A9 A4 A8 A5 A10.图的矩阵表示图的矩阵表示 任意一个任意一个有限简单图有限简单图G的都可用一个实数矩的都可用一个实数矩阵阵A=(aij)nn 来表示来表示，其中，其中n阶为阶为G的顶点数的顶点数.当当G=(V,E)的边的边(弧弧)没有赋权没有赋权时，定义时，定义

16、当当G=(V,E,F)的边的边(弧弧)有赋权有赋权时，定义时，定义 当当vivj E,若求图若求图G的最短路时的最短路时,定义定义aii=0,aij=+(i j);若求图若求图G的最长路时的最长路时,则定义则定义aii=+,aij=0(i j).6.1.2 最短路与最小生成树最短路与最小生成树 定义定义1 设设P(u,v)是赋权图是赋权图G=(V,E,F)中，从点中，从点u到到v的路的路.用用E(P)表示路表示路P(u,v)中全部边中全部边(弧弧)的集合的集合,记记则称则称F(P)为路为路P(u,v)的的权权或或长度长度(距离距离).定义定义2 若若P0(u,v)是是G 中连接中连接u,v的路

17、的路,且且对任意在对任意在G 中连接中连接u,v的路的路P(u,v)都有都有F(P0)F(P),则称则称P0(u,v)是是G 中连接中连接u,v的的最短路最短路.重要性质：重要性质：若若v0 v1 vm 是是图图G中从中从v0到到vm的最短路的最短路,则则 1km,v0v1 vk 必为必为G中从中从v0到到vk的最短路的最短路.即：最短路是一条路即：最短路是一条路,且最短路的任一段也且最短路的任一段也是最短路是最短路.求非负赋权图求非负赋权图G中某一点到其它各点最短路中某一点到其它各点最短路,一般用一般用Dijkstra标号算法标号算法;求赋权图上任意两点间求赋权图上任意两点间的最短路，一般用

18、的最短路，一般用Floyd算法算法.Dijkstra标号算法标号算法仅适用于非负赋权图仅适用于非负赋权图.由于由于Dijkstra标号算法较为复杂标号算法较为复杂,以下只介绍以下只介绍Floyd算法算法.求赋权图中任意两点的最短路的求赋权图中任意两点的最短路的Floyd算法：算法：设设A=(aij)nn为赋权图为赋权图G=(V,E,F)的权矩阵的权矩阵,dij表示从表示从vi到到vj点的距离点的距离,rij表示从表示从vi到到vj点的最点的最短路中一个点的编号短路中一个点的编号.赋初值赋初值.对所有对所有i,j,dij=aij,rij=j.k=1.转转向向.更新更新dij,rij.对所有对所有

19、i,j,若若dik+dk jdij,则则令令dij=dik+dkj,rij=k,转向转向;终止判断终止判断.若若dii0或或k=n终止，最短路线终止，最短路线可由可由rij得到得到;否则令否则令k=k+1,转向转向.dii 0 表明表明 G 中存在一条含有顶点中存在一条含有顶点 vi 的负回的负回路路;k=n终止后若有终止后若有dij=+表明表明G非连通非连通.例例1 1 求下图中任意两点间的最短路求下图中任意两点间的最短路.221118675394368v1v2v3v4v5v6v7v8 解解：用：用Floyd算法算法,首先写出其首先写出其(对称的对称的)权矩权矩阵阵A=(aij)88，然后利

20、用计算机编程计算然后利用计算机编程计算.1 2 3 4 5 6 7 81 2 3 4 5 6 7 81 1 0 2 8 1 0 2 8 1 2 2 2 0 6 1 2 0 6 1 3 3 8 6 0 7 5 1 2 8 6 0 7 5 1 2 4 4 1 7 0 9 1 7 0 9 5 5 1 5 0 3 8 1 5 0 3 86 6 1 3 0 4 6 1 3 0 4 67 7 2 9 4 0 3 2 9 4 0 38 8 8 6 3 0 8 6 3 0 求赋权图中任意两点的最短路求赋权图中任意两点的最短路Floyd算法的算法的MATLAB程序：程序：A=0281InfInfInfInf20

21、6Inf1InfInfInf8607512Inf1Inf70InfInf9InfInf15Inf03Inf8InfInf1Inf3046InfInf29Inf403InfInfInfInf8630;%用用Inf表示表示n=8;D=A;R=;%赋初值赋初值for i=1:n for j=1:n R(i,j)=j;%赋初值赋初值 endendfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);%更新更新 dij R(i,j)=k;%更新更新 rij end end end k%显示迭代步数显示迭代步数 D

22、%显示路长显示路长 R%显示路径显示路径end for i=1:n%含有负权时 if(D(i,i)0)break%存在负回路 end end if(in|D(n,n)0)break%终止 end计算结果计算结果221118675394368v1v2v3v4v5v6v7v80 2 7 1 3 6 9 110 2 7 1 3 6 9 112 0 5 3 1 4 7 92 0 5 3 1 4 7 97 5 0 7 4 1 2 57 5 0 7 4 1 2 51 3 7 0 4 7 9 121 3 7 0 4 7 9 123 1 4 4 0 3 6 83 1 4 4 0 3 6 86 4 1 7 3

23、0 3 66 4 1 7 3 0 3 69 7 2 9 6 3 0 39 7 2 9 6 3 0 311 9 5 12 8 6 3 011 9 5 12 8 6 3 0最小生成树最小生成树 由树的定义不难知道由树的定义不难知道,任意一个连通的任意一个连通的p,q 图图(p个顶点个顶点q条边条边)G适当去掉适当去掉q-p+1条边后条边后,都都可以变成树可以变成树,这棵树称为图这棵树称为图G的的生成树生成树.设设T是图是图G的一棵生成树的一棵生成树,用用F(T)表示树表示树T中中所有边的权数之和所有边的权数之和,F(T)称为称为树树T的权的权.一个连通图一个连通图G的生成树一般不止一棵的生成树一般

24、不止一棵,图图 G的所有生成树中权数最小的生成树称为图的所有生成树中权数最小的生成树称为图 G 的的最最小生成树小生成树，简称，简称最小树最小树.求最小生成树问题有很广泛的实际应用求最小生成树问题有很广泛的实际应用.例例如如,把把n个乡镇用高压电缆连接起来建立一个电网个乡镇用高压电缆连接起来建立一个电网,使所用的电缆长度之和最短使所用的电缆长度之和最短,即费用最小即费用最小,就是就是一个求最小生成树问题一个求最小生成树问题.求连通图求连通图G的最小生成树的最小生成树T的近似算法有破圈的近似算法有破圈法与法与Kruskal避圈法避圈法.(1)(1)破圈法：先任取一个圈，从圈中去掉一破圈法：先任取

25、一个圈，从圈中去掉一条权数最大的边，若在同一圈中权数最大的边不条权数最大的边，若在同一圈中权数最大的边不止一条止一条,则任选其中一条边去掉则任选其中一条边去掉(不同的选择可能不同的选择可能会导致权数不同的结果会导致权数不同的结果).).重复上述步骤重复上述步骤,直至没直至没有圈为止有圈为止.(2)2)Kruskal 避避圈法：将图圈法：将图G中的边按权从中的边按权从小到大逐条考察小到大逐条考察,按不构成圈的原则加入到按不构成圈的原则加入到T 中中(若有选择时若有选择时,不同的选择可能会导致权数不同的不同的选择可能会导致权数不同的结果结果),),直到直到 q(T)=p(G)-1为止，即为止，即T

26、 的边数的边数=G的顶点数的顶点数-1为止为止.例如下图例如下图,p(G)=8.其最小生成树用其最小生成树用Kruskal 避圈法如下避圈法如下：221118675394368v1v2v3v4v5v6v7v8依次将权数为依次将权数为1，2，3的边加入的边加入到到T 中即可中即可.F(T)=3+4+6=13类似地，可类似地，可定义连通图定义连通图G 的最大生的最大生成树成树.选址问题选址问题 现准备现准备在在 n 个个居民点居民点v1,v2,vn中设置一中设置一银行银行.问设在哪个点问设在哪个点,可使最大服务距离最小可使最大服务距离最小?若若设置两个银行设置两个银行,问设在哪两个点问设在哪两个点

27、?模型假设模型假设 假设各假设各个个居民点都有条件设置银居民点都有条件设置银行行,并有路相连并有路相连,且路长已知且路长已知.模型建立与求解模型建立与求解 用用Floyd算法求出任意两算法求出任意两个个居民点居民点vi,vj 之间的最短距离之间的最短距离,并用并用dij 表示表示.设置一个银行设置一个银行,银行设银行设在在 vi 点点的最大服务的最大服务距离为距离为求求k,使使 即若设置一个银行即若设置一个银行,则银行设在则银行设在 vk 点点,可使最可使最大服务距离最小大服务距离最小.设置两个银行设置两个银行,假设银行设假设银行设在在vs,vt 点点使使最大服务距离最小最大服务距离最小.记记

28、则则s,t 满足：满足：进一步进一步,若设置多个银行呢？若设置多个银行呢？6.2 网络流问题网络流问题 定义定义1 1 设设D=(V,A)为有向图为有向图,在在V中指定一点中指定一点称为称为发点发点(源，记为源，记为vs),),和另一点称为和另一点称为收点收点(汇汇,记记为为vt),),其余点叫做中间点其余点叫做中间点.对每一条弧对每一条弧vivjA,对对应一个非负实数应一个非负实数wij,称为它的称为它的容量容量.这样的这样的D称为称为容量网络容量网络,简称简称网络网络,记作记作D=(V,A,W).定义定义2 2 网络网络D=(V,A,W)中任一条弧中任一条弧vivj有流有流量量 fij,称

29、集合称集合 f=fij 为网络为网络D上的一个上的一个流流.满足下述条件的流满足下述条件的流 f 称为称为可行流可行流：(限制条件限制条件)对每一条对每一条弧弧vivj,有有0 fij wij;(平衡条件平衡条件)对于中间点对于中间点vk有有fik=fkj ,即中间点即中间点vk的输入的输入量量=输出输出量量.下图表示一个网络下图表示一个网络(8,6)(7,3)(6,1)(4,2)(3,3)(5,4)(6,2)(10,5)(5,4)v2v1v3v4vsvt 弧旁括号中的两个数字弧旁括号中的两个数字(wij,fij)，第一个数第一个数字字wij表示该弧的最大容量表示该弧的最大容量,第二个数字第二

30、个数字fij表示通过表示通过该弧的流量该弧的流量.如弧如弧vsv1上上(8,6)表示弧表示弧vsv1的最大容量为的最大容量为8,通过弧通过弧vsv1的流量为的流量为6.从图中容易看出流从图中容易看出流 f 满足可行流的两个条件满足可行流的两个条件.如果如果 f 是可行流是可行流,则对收、发点则对收、发点vt、vs有有fsi=fjt=Wf,即从即从vs点发出的物质总量点发出的物质总量=vt点输入的量点输入的量.Wf 称为称为网络流网络流 f 的总流量的总流量.上述概念可以这样来理解上述概念可以这样来理解,如如D是一个运输网是一个运输网络络,则发点则发点vs表示发送站表示发送站,收点收点vt表示接

31、收站表示接收站,中间中间点点vk表示中间转运站表示中间转运站,可行流可行流 fij 表示某条运输线上表示某条运输线上通过的运输量通过的运输量,容量容量wij表示某条运输线能承担的最表示某条运输线能承担的最大运输量大运输量,Wf 表示运输总量表示运输总量.可行流总是存在的可行流总是存在的.比如所有边的流量比如所有边的流量 fij=0就是一个可行流就是一个可行流(称为零流称为零流).).在实际问题中在实际问题中,一个网络一般会出现下面两一个网络一般会出现下面两种情况：种情况：发点和收点都不止一个发点和收点都不止一个.解决的方法是再虚设一个发点解决的方法是再虚设一个发点vs和一个收点和一个收点vt,

32、发点发点vs到所有原发点边的容量都设为无穷大到所有原发点边的容量都设为无穷大,所有原收点到收点所有原收点到收点vt 边边的容量都设为无穷大的容量都设为无穷大.网络中除了边有容量外网络中除了边有容量外,点也有容量点也有容量.解决的方法是将所有有容量的点分成两个点解决的方法是将所有有容量的点分成两个点,如点如点v有容量有容量wv,将点将点v分成两个点分成两个点v和和v,令令w(vv)=wv.6.2.2 最大流问题最大流问题 所谓所谓最大流问题最大流问题就是在网络就是在网络D=(V,A,W)中中,寻找流量最大的可行流寻找流量最大的可行流.求最大可行流的数学模求最大可行流的数学模型如下：型如下：显然，

33、最大流问题是一个典型而又特殊的线显然，最大流问题是一个典型而又特殊的线性规划问题，自然可用单纯性法求解性规划问题，自然可用单纯性法求解.但利用图但利用图的特点，我们介绍一种直观简便的求解方法的特点，我们介绍一种直观简便的求解方法.1.1.增广链增广链 设网络设网络D=(V,A,W)中中,有一可行流有一可行流 f=fij,按每条弧上流量的多少，可将弧分为四种类按每条弧上流量的多少，可将弧分为四种类型：型：饱和弧饱和弧 (fij=wij);非非饱和弧饱和弧 (fij 0).(8,6)(7,3)(6,1)(4,2)(3,3)(5,4)(6,2)(10,5)(5,4)v2v1v3v4vsvt例如，例如

34、，v1v4是是饱和弧，其他都是饱和弧，其他都是非非饱和弧饱和弧.若若 为网络为网络D中从中从vs到到vt的一条链的一条链(这里链是指这里链是指链中既没有相同的弧又没有相同的顶点链中既没有相同的弧又没有相同的顶点),定义定义链的方向是从链的方向是从vs 到到vt,弧的方向与链的方向相同称弧的方向与链的方向相同称为正向弧为正向弧,正向弧的全体记为正向弧的全体记为 +;弧的方向与链弧的方向与链的方向相反称为反向弧的方向相反称为反向弧,反向弧的全体记为反向弧的全体记为 .定义定义3 设设 f 是一个可行流是一个可行流,是从是从vs到到vt一条一条链链.如果满足：如果满足：当当vivj +时时,0,0f

35、ijwij,即即 +中的每中的每一条弧都非饱和弧一条弧都非饱和弧;当当vivj 时时,0fij wij,即即 中的每中的每一条弧都非零流弧一条弧都非零流弧.则则称称 为从为从vs到到vt的关于的关于 f 的的可增广链可增广链.(8,6)(7,3)(6,1)(4,2)(3,3)(5,4)(6,2)(10,5)(5,4)v2v1v3v4vsvt 在链在链vsv2v1v4v3vt中，中，+=vsv2,v1v4,v3vt,-=v2v1,v4v3.1=vsv2v1v3vt 是一条增广链是一条增广链，2=vsv2v1v4vt 却不是增广链却不是增广链.不难理解，如果不难理解，如果 是一条增广链，那么是一条

36、增广链，那么在在 上上可以增加一定的流量可以增加一定的流量.2.2.截集截集 定义定义4 若将若将网络网络D=(V,A,W)的的点集点集V被剖被剖分为两个非空集合分为两个非空集合VS,VSc,使使vs VS,vt VSc,且且VSVSc=,VSVSc=V.则把弧集则把弧集(VS,VSc)=vivj|vivjA,viVS,vjVSc 称为称为D的的截集截集或或割集割集.截集截集(VS,VSc)中所有弧的容量之和中所有弧的容量之和,称为这称为这个截集的截量个截集的截量,记为记为W(VS,VSc).显然显然,若把一截集的弧从网络中去掉若把一截集的弧从网络中去掉,则从则从vs到到vt便不再相通便不再相

37、通,所以截集是从所以截集是从vs到到vt的必经之路的必经之路.定理定理1 设设 f 为网络为网络D=(V,A,W)的任一可行的任一可行流流,(VS,VSc)是分割是分割vs,vt 的任一截集的任一截集,则有则有Wf W(VS,VSc).若有可行流若有可行流 f 和截集和截集(VS,VSc),使得使得Wf=W(VS,VSc),则则 f 一定是一定是D的最大流的最大流,而而(VS,VSc)必定是必定是D中中所有截集中容量最小的一个所有截集中容量最小的一个,即最小截集即最小截集.定理定理2 (最大流最大流 最小截量定理最小截量定理)任一个任一个网络网络D中中,从从vs到到vt的最大流的流量等于分割的

38、最大流的流量等于分割vs,vt的最小截集的截量的最小截集的截量.推论推论 可行可行流流 f 是是最大流的充要条件是不存在最大流的充要条件是不存在从从vs到到vt的的(关于关于f 的的)可增广链可增广链.可增广链可增广链 的实际意义是的实际意义是:沿着这条链从沿着这条链从vs到到vt输送的流输送的流,还有潜力可挖还有潜力可挖,只需按照下述的调整只需按照下述的调整方法：方法：=min ij|vivj ,定义流定义流 g=gij 为为令令调整后的流调整后的流g,在各点仍满足平衡条件及容量限制在各点仍满足平衡条件及容量限制条件条件,即仍为可行流即仍为可行流,且有且有Wg=Wf+.寻求最大流的方法寻求最

39、大流的方法 从一个可行流开始从一个可行流开始,寻求关于这个可行流的寻求关于这个可行流的可增广链可增广链,若存在若存在,则可以经过调整则可以经过调整,得到一个得到一个新的可行流新的可行流,其流量比原来的可行流要大其流量比原来的可行流要大.重复重复这个过程这个过程,直到不存在关于该流的可增广链时就直到不存在关于该流的可增广链时就得到了最大流得到了最大流.下面给出从一个可行流下面给出从一个可行流 f 开始开始,求最大流的求最大流的Ford-Fulkerson标号算法的基本步骤：标号算法的基本步骤：标号过程标号过程 给发点给发点vs以标号以标号(+,+),s=+.选择一个已标号的点选择一个已标号的点x

40、,对于对于x的所有未给的所有未给标号的邻接点标号的邻接点y,按下列规则处理：按下列规则处理：当当yxA,且且fyx 0时时,令令 y=min fyx,x,并给并给 y 以标号以标号(x ,y).重复重复直到收点直到收点vt被标号或不再有点可标被标号或不再有点可标号时为止号时为止.若若vt得到标号得到标号,说明存在一条可增广链说明存在一条可增广链,转转调整过程调整过程;若若vt未得到标号未得到标号,标号过程已无法进行时标号过程已无法进行时,说说明明f 已经是最大流已经是最大流.当当xyA,且且fxywxy时时,令令 y=min wxy fxy,x,并给并给 y 以标号以标号(x+,y).调整过程

41、调整过程 决定调整量决定调整量 =u,其中其中u=vt.调整流调整流 f 若若u点标号为点标号为(v+,u),则以则以fvu+代替代替fvu;若若u点标号为点标号为(v ,u),则以则以 fvu 代替代替fvu.若若v=vs,则去掉所有标号转则去掉所有标号转重新标号重新标号;否则令否则令u=v,转转.算法终止后算法终止后,令已有标号的点集为令已有标号的点集为VS,则截则截集集(VS,VSc)为最小截集为最小截集,从而从而Wf=W(VS,VSc).例例1 求下图所示网络的最大流求下图所示网络的最大流.(8,3)(7,7)(3,3)(2,0)(6,6)(8,4)(3,0)(7,6)(10,4)v1

42、v2v4v3vsvt 解解 可行流可行流 f 已由上图给出已由上图给出.标号过程：先给标号过程：先给vs标以标以(+,+).检查检查vs的未标号的邻接点的未标号的邻接点v1,v2,点点v1不满足不满足标号的条件标号的条件.v2点满足点满足vsv2A,且且 fs2=3ws2=8,令令 v2=min8 3,+=5,给给v2以标号以标号(vs+,5).(8,3)(7,7)(3,3)(2,0)(6,6)(8,4)(3,0)(7,6)(10,4)v1v2v4v3vsvt(vs+,5)(+,+)检查检查v2的的未标号的邻接点未标号的邻接点v1,v3,点点v3不满足不满足标号的条件标号的条件.v1点满足点满

43、足v1v2A,且且 f12=30,令令 v1=min3,v2=min3,5=3,给给v1以标号以标号(v2,3).(8,3)(7,7)(3,3)(2,0)(6,6)(8,4)(3,0)(7,6)(10,4)v1v2v4v3vsvt(vs+,5)(+,+)(v2 ,3)检查检查v1的未标号的邻接点的未标号的邻接点v3,v4,点点v3不满足不满足标号的条件标号的条件.v4点满足点满足v1v4A,且且 f14=4w14=8,令令 v4=minw14 f14,v1=min4,3=3,给给v4以标号以标号(v1+,3).检查检查v4的未标号的邻接点的未标号的邻接点v3,vt,点点v3不满足不满足标号的条

44、件标号的条件.vt点满足点满足v4vtA,且且 f4t=4w4t=10,令令 vt=minw4t f4t,v4=min6,3=3,给给vt以标号以标号(v4+,3).(8,3)(7,7)(3,3)(2,0)(6,6)(8,4)(3,0)(7,6)(10,4)v1v2v4v3vsvt(vs+,5)(+,+)(v2 ,3)(v1+,3)(8,3)(7,7)(3,3)(2,0)(6,6)(8,4)(3,0)(7,6)(10,4)v1v2v4v3vsvt(vs+,5)(+,+)(v2 ,3)(v1+,3)(v4+,3)此时此时,vt得到标号得到标号,说明存在一条可增广链说明存在一条可增广链,由由vt反

45、向追踪得可增广链反向追踪得可增广链 =vsv2v1v4vt,其中其中 +=vsv2,v1v4,v4vt,-=v1v2.转转调整过程调整过程.(8,3)(7,7)(3,3)(2,0)(6,6)(8,4)(3,0)(7,6)(10,4)v1v2v4v3vsvt(vs+,5)(+,+)(v2 ,3)(v1+,3)(v4+,3)调整过程调整过程 调整量调整量 =vt=3,由由u=vt 反向追踪依次调整反向追踪依次调整流流f 如下：如下：f4t=4+3=7;f14=4+3=7;f21=3 3=0;fs2=3+3=6.去掉所有标号转去掉所有标号转重新标号重新标号(8,6)(7,7)(3,0)(2,0)(6

46、,6)(8,7)(3,0)(7,6)(10,7)v1v2v4v3vsvt 先给先给vs标以标以(+,+).检查检查vs的未标号的邻接点的未标号的邻接点v1,v2,点点v1不满足不满足标号的条件标号的条件.v2点满足点满足vsv2A,且且 fs2=6ws2=8,令令 v2=min8 6,+=2,给给v2以标号以标号(vs+,2).(8,6)(7,7)(3,0)(2,0)(6,6)(8,7)(3,0)(7,6)(10,7)v1v2v4v3vsvt(vs+,2)(+,+)检查检查v2的的未标号的邻接点未标号的邻接点v1,v3,点点v1,v3都都不满足标号的条件不满足标号的条件.标号过程已无法进行时标

47、号过程已无法进行时,且且vt未得到标号未得到标号,说明说明f 已经是最大流已经是最大流.Wf=fs1+fs2=f3t+f4t=6+7=13.(8,6)(7,7)(3,0)(2,0)(6,6)(8,7)(3,0)(7,6)(10,7)v1v2v4v3vsvt(vs+,2)(+,+)用标号法在得到最大流的同时用标号法在得到最大流的同时,可得到一可得到一个最小个最小截集截集.如上图所示如上图所示,标号点集合为标号点集合为VS=vs,v2,未标号点集合为未标号点集合为截集截集VSc=v1,v3,v4,vt,此时此时截集截集(VS,VSc)=vsv1,v2v3,截截量量W(VS,VSc)=ws1+w23

48、=7+6=13,与最大流的流量与最大流的流量Wf 相等相等.(8,6)(7,7)(3,0)(2,0)(6,6)(8,7)(3,0)(7,6)(10,7)v1v2v4v3vsvt(vs+,2)(+,+)最小截集最小截集(VS,VSc)=vsv1,v2v3.由此也可以体会到最小截集的意义由此也可以体会到最小截集的意义,网络从网络从发点到收点和各通路中发点到收点和各通路中,由容量决定其通过能力由容量决定其通过能力,最小截集则是这些路中的咽喉部分最小截集则是这些路中的咽喉部分,或者叫瓶口或者叫瓶口,其容量最小其容量最小,它决定了整个网络的最大通过能力它决定了整个网络的最大通过能力,要提高整个网络的运输

49、能力要提高整个网络的运输能力,必须首先改造这个必须首先改造这个咽喉部分的通过能力咽喉部分的通过能力.6.3最小费用流问题最小费用流问题 这里我们要进一步探讨不仅要使网络上的流这里我们要进一步探讨不仅要使网络上的流达到最大达到最大,或者达到要求的预定值或者达到要求的预定值,而且还要使运而且还要使运输流的总费用是最小的输流的总费用是最小的,这就是最小费用流问题这就是最小费用流问题.最小费用流问题的一般提法：最小费用流问题的一般提法：已知网络已知网络D=(V,A,W),每条边每条边vivjA 除了除了已给容量已给容量wij外外,还给出了单位流量的费用还给出了单位流量的费用bij(0).).所谓最小费

50、用流问题就是求一个总流量已知所谓最小费用流问题就是求一个总流量已知的可行流的可行流 f=f ij 使得总费用使得总费用最小最小.特别地特别地,当要求当要求 f 为最大流时为最大流时,此问题即为此问题即为最最小费用最大流问题小费用最大流问题.设网络设网络D=(V,A,W),取初始可行流取初始可行流 f 为零流为零流,求解最小费用流问题的迭代步骤求解最小费用流问题的迭代步骤：构造有向赋权图构造有向赋权图(费用有向图费用有向图)Df=(V,Af,F),对于任意的对于任意的vivjA,Af,F 的定义如下：的定义如下：当当 fij=0时时,vivjAf,F(vivj)=bij;当当 fij=wij时时