运筹学11图与网络1

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第十一章 图与网络规划,11.1 图与网络的基本概念,11.2 树及最小树问题,11.3 最短路问题,11.4 网络最大流问题,11.5 最小费用最大流问题,9/23/2024,1,11.1 图与网络的基本概念,图的概念,所谓图，就是顶点和边的集合，点的集合记为,V,，边的集合记为E，则图可以表示为：,G,（,V,，,E,），点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存在，每条边都有两个端点。,在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，则两个图相同。,9/23/2024,2,图的表示,e,1,e,2,e,3,e,4,e,5,v,2,v,3,v,1,v,4,v,5,v,6,e,6,e,7,e,8,e,9,9/23/2024,3,点与边,顶点数,集合V中元素的个数，记作,p(G),。,边数,集合E中元素的个数，记作,q(G),。,若,e=u,vE,，则称,u,和,v,为,e,的,端点,，而称,e,为,u,和,v,的,关联边,，也称,u,，,v,与边,e,相,关联,。,例如图中的图,G,，,p,(,G,)=6，,q,(,G,)=9，,v,1,，v,2,是,e,1,和,e,2,的端点，,e,1,和,e,2,都是,v,1,和,v,2,的关联边。,e,1,e,2,e,3,e,4,e,5,v,2,v,3,v,1,v,4,v,5,v,6,e,6,e,7,e,8,e,9,9/23/2024,4,点边关系,若点,u,和,v,与同一条边相关联，则,u,和,v,为,相邻点,；若两条边,e,i,和,e,j,有同一个端点，则称,e,i,与,e,j,为,相邻边,。,例如在图中,v,1,和,v,2,为相邻点，,v,1,和,v,5,不相邻；,e,1,与,e,5,为相邻边，,e,1,和,e,7,不相邻。,e,1,e,2,e,3,e,4,e,5,v,2,v,3,v,1,v,4,v,5,v,6,e,6,e,7,e,8,e,9,9/23/2024,5,简单图,若一条边的两个端点是同一个顶点，则称该边为,环,；又若两上端点之间有多于一条边，则称为,多重边,或,平行边,。,例如图的,e,8,为环，,e,1,，e,2,为两重边，,e,4,，e,5,也是两重边。,含有多重边的图称作,多重图,。,无环也无多重边的图称作,简单图,。,e,1,e,2,e,3,e,4,e,5,v,2,v,3,v,1,v,4,v,5,v,6,e,6,e,7,e,8,e,9,9/23/2024,6,图的次,次,点,v,作为边的端点的次数，记作,d(v),，如图中，,d(v,1,),=5,d(v,4,),=6等,端点次为奇数的点称作,奇点,；次为偶数的点称作,偶点,。,次为1的点称为,悬挂点,，与悬挂点连接的边称作,悬挂边,；,次为0的点称为,孤立点,。,图中的点v,5,即为悬挂点，边e,9,即为悬挂边，而点v,6,则是弧立点。,e,1,e,2,e,3,e,4,e,5,v,2,v,3,v,1,v,4,v,5,v,6,e,6,e,7,e,8,e,9,9/23/2024,7,定理,若图,G,中所有点都是孤立点，则称图,G,为,空图,。,定理1,所有顶点的次的和，等于所有边数的2倍。即,e,1,e,2,e,3,e,4,e,5,v,2,v,3,v,1,v,4,v,5,v,6,e,6,e,7,e,8,e,9,9/23/2024,8,定理2,在任一图中，奇点的个数必为偶数。,设,V,1,和,V,2,分别是图,G,中次数为奇数和偶数的顶点集合。由定理1有,e,1,e,2,e,3,e,4,e,5,v,2,v,3,v,1,v,4,v,5,v,6,e,6,e,7,e,8,e,9,9/23/2024,9,链,由两两相邻的点及其相关联的边构成的点边序列称为,链,。,v,0,称为链的,起点,，,v,n,称为链的,终点,。,若,v,0,v,n,则称该链为,开链,，反之称为,闭链,或,回路,。,e,1,e,2,e,3,e,4,e,5,v,2,v,3,v,1,v,4,v,5,v,6,e,6,e,7,e,8,e,9,9/23/2024,10,简单链,若链中所含的边均不相同，则称为,简单链,；若点均不相同，则称为,初等链,或,通路,。,除起点和终点外点均不相同的闭链，称为,初等回路,或称为,圈,。,例如图中,e,1,e,2,e,3,e,4,e,5,v,2,v,3,v,1,v,4,v,5,v,6,e,6,e,7,e,8,e,9,是一条链，且是开链，也是简单链，但不是初等链，因为,v,1,出现两次。,9/23/2024,11,圈,若链中所含的边均不相同，则称为,简单链,；若点均不相同，则称为,初等链,或,通路,。除起点和终点外点均不相同的闭链，称为,初等回路,或称为,圈,。,例如图中,e,1,e,2,e,3,e,4,e,5,v,2,v,3,v,1,v,4,v,5,v,6,e,6,e,7,e,8,e,9,是一个圈。,9/23/2024,12,连通性,若一个图,G,的任意两点之间均至少有一条通路（初等链）连接起来，则称这个图,G,是一个,连通图,，否则称作,不连通图,。,例如图中，,v,1,和,v,6,之间没有通路，因此它不是连通图，而如果去掉,v,6,，则构成一个连通图。,e,1,e,2,e,3,e,4,e,5,v,2,v,3,v,1,v,4,v,5,v,6,e,6,e,7,e,8,e,9,9/23/2024,13,连通的意义,连通是一个很重要的概念，如果一个问题所对应的图是一个不连通图，则该问题一定可以分解成互不相关的子问题来加以研究，即可以把不连通图分解成连通的子图来研究。,e,1,e,2,e,3,e,4,e,5,v,2,v,3,v,1,v,4,v,5,v,6,e,6,e,7,e,8,e,9,9/23/2024,14,子图,子图的定义 设，,G,1,=(,V,1,E,1,),G,2,=(,V,2,E,2,)，如果,V,1,V,2,，又,E,1,E,2,，则称,G,1,是,G,2,的,子图,。,e,1,e,2,e,3,e,4,e,5,v,2,v,3,v,1,v,4,v,5,v,6,e,6,e,7,e,8,e,9,e,1,e,2,e,3,e,4,e,5,v,2,v,3,v,1,必须指出，并不是从图,G,2,中任选一些顶点和边在一起就组成,G,2,的子图,G,1,，而只有在,G,2,中的一条边以及连接该边的两个端点均选入,G,1,时，,G,1,才是,G,2,的子图。,9/23/2024,15,特殊子图,当,G,1,中不包含,G,2,中所有的顶点和边，则称,G,1,是,G,2,的,真子图,。,部分图 若,V,1,=V,2,，,E,1,E,2,，则称,G,1,为,G,2,的一个,部分图,。,若,V,1,V,2,，,E,1,= ,u,v, |,u,V,1,vV,1,，则称,G,1,是,G,2,中 由,V,1,导出的,导出子图,。,e,1,e,2,e,3,e,4,e,5,v,2,v,3,v,1,v,4,v,5,v,6,e,6,e,7,e,8,e,9,e,1,e,2,e,3,e,4,e,5,v,2,v,3,v,1,9/23/2024,16,有向图,在有些图中，边是没有方向的，即,u,v,=,v,u,，这种图称为,无向图,。,而有些关系是不对称的，例如父子关系、上下级关系、加工工序的先后顺序等都具有单向性，用图来表示这些关系时，得到的边是具有方向的，用带箭头的线来表示，称为,弧,。,从顶点,u,指向,的弧,a,，记作,a,=(,u,v,),(,u,v,)(,v,u,)，其中,u,称为,a,的起点，v称为a的终点，这样的图称为,有向图,。仍以,V,表示点的集合，以,A,表示弧的集合，则有向图表示为,D,（,V，A,）,9/23/2024,17,有向图例,e,1,e,2,e,3,e,4,e,5,v,2,v,3,v,1,v,4,v,5,v,6,e,6,e,7,e,8,e,9,9/23/2024,18,有向图的链路,有向图中，在不考虑边的方向时，也可以相同地定义,链,，若有向图,D,（,V，A,）中，,P,是一个从,u,到,v,的链，且对,P,中每一条弧而言，在序列中位于该弧前面的点恰好是其起点，而位于该弧后面的点恰好是其终点，这个链,P,就称为是,D,中从,u,到,v,的一条,路,。,当路的起点与终点相同，即,u=v,时，称作一条,回路,。,顶点全不相同的路称为,初等路,。,除起点和终点外点均不相同的回路称为,初等回路,。,e,1,e,2,e,3,e,4,e,5,v,2,v,3,v,1,v,4,v,5,v,6,e,6,e,7,e,8,e,9,9/23/2024,19,11.2 树及最小树问题,一个没有圈的图称为一个,无圈图,或称为,林,。,一个连通的无圈图则称为,树,，一个林的每个连通子图都是一个树。,定理,以下关于树的六种不同描述是等价的：,无圈连通图。,无圈，,q=p-1,。,连通，,q=p-1,。,无圈，但若任意增加一条边，则可得到一个且仅一个圈。,连通，但若任意舍弃一条边，图便不连通。,每一对顶点之间有一条且仅有一条链。,9/23/2024,20,部分树,若,T,是图,G,（,V，E,）的部分图，且,T,是树，则称T为,G,的,部分树,。,若,T,是图,G,的部分树，则从,G,中去掉T中所有的边，所得到的子图称为,G,中的,T,的,余树,，也称为,G,的一个余树。,余树不一定是树！,一个没有圈的图称为一个,无圈图,或称为,林,。,一个连通的无圈图则称为,树,，一个林的每个连通子图都是一个树。,9/23/2024,21,网络概念,图只能用来研究事物之间有没有某种关系，而不能研究这种关系的强弱程度。,网络,赋权的图,权,程度的度量，数量描述。,v,1,1,3,9,5,3,8,3,6,2,v,6,v,5,v,3,v,4,v,2,9/23/2024,22,网络最短树问题,最短树问题,的一般提法是：选取网络中的部分图，使得网络连通，且使总权数最短。,在实际应用中，经常碰到需要求一个赋权连通图的最短树的问题。例如，用节点表示城市，用边表示可以在两个城市之间架设光缆，边上的权表示光缆的长度，试求应如何架设光缆，才能使任意两城市之间均由光缆相通，且使光缆的总长度最短。,求最短树的方法，依据的是树的特点，即无圈和连通，加上最短的要求，方法主要有两种：一种称为,破圈法,，一种称为,生长法,9/23/2024,23,网络最短树-破圈法原理,破圈法原理,如果网络图中无圈并且,q=p-1,，则已经是树；,如果网络图中有圈，则截去该圈中权数最大的边；这样，并不影响网络图的连通性，且能使边数减少一个；,经过一定次数的截边，网络图中将再也没有圈，成为无圈图；,如果此时的网络满足,q=p-1,，则已经是树；,由于每次截去的边在圈中具有最大的权数，因此获得的树也是最短的树。,9/23/2024,24,v,1,1,3,9,5,3,8,3,6,2,v,6,v,5,v,3,v,4,v,2,破圈法,步骤,在网络图中寻找一个圈，若已经无圈则转。,在圈中选取权数最大的边，从网络图中截去该边，对新的网络，转。,若,q=p-1,，则已找到最短树，否则网络图不连通，无最短树。,方法示例：,例 对图中的网络，用破圈法求最短树。,9/23/2024,25,网络最短树-生长法原理,生长法原理,类似于自然界中植物生长的过程，结合就近生长和避免构成圈的要求，逐步生长直到所有的点都已经被包含。,如果原网络不连通，则在生长过程中会出现某些点不能被生长，则结束。,避圈的原理是已经被包含在生长过的树中的点不再被生长。,由于在每次生长时都采用就近生长的方法，生成的树一定是最短树。,9/23/2024,26,v,1,1,3,9,5,3,8,3,6,2,v,6,v,5,v,3,v,4,v,2,生长法步骤,从图上任选一点,i,，令,若这样的边不存在，则原图没有最短部分树。,令,若,S=V,，则已找到最短树，否则，,从,S,k,中的各点到,S,k,中各点的边中选权数最小的,边，设为,i,，,j,，则,9/23/2024,27,生长法示例,取,S,=,v,1, 则,S,到其余点的距离在距离矩阵中第一行,9/23/2024,28,v,1,1,3,9,5,3,8,3,6,2,v,6,v,5,v,3,v,4,v,2,9/23/2024,29,9/23/2024,30,9/23/2024,31,v,1,1,3,9,5,3,8,3,6,2,v,6,v,5,v,3,v,4,v,2,9/23/2024,32,11.3 最短路问题,最短路问题的一般提法是：欲寻找网络中从起点,1,到终点,n,的最短路线，即寻求连接这两点的边的总长度为最小的通路，最短路线中的网络大都是有向网络，也可以是无向网络。,9,7,5,7,8,4,5,6,4,6,5,4,7,s,a,b,c,d,e,f,t,9/23/2024,33,最短路问题的狄克斯拉算法,把,V,分成两个集合,令,计算,求,若,v,k,=v,n,则已经求得,v,n,到,v,1,的最短路线，否则继续计算,使用条件,l,ij,0,9/23/2024,34,算法解释,若以,P(v,i,),记,v,1,到,v,i,的最短距离，则根据动态规划原理应有,第一步 取,P,(,v,1,)0，而,T,(,v,j,)则是对,P,(,v,j,)所取的初值；,v,1,1,3,9,5,3,8,3,6,2,v,6,v,5,v,3,v,4,v,2,9/23/2024,35,第二步 利用,P,(,v,i,)已知，据上式对,T,(,v,j,)进行修正；,v,1,1,3,9,5,3,8,3,6,2,v,6,v,5,v,3,v,4,v,2,9/23/2024,36,第三步 对,T,(,v,j,)求,v,1,1,3,9,5,3,8,3,6,2,v,6,v,5,v,3,v,4,v,2,9/23/2024,37,k,=2, 不是最优，继续,v,1,1,3,9,5,3,8,3,6,2,v,6,v,5,v,3,v,4,v,2,9/23/2024,38,在所有的,T,(,v,j,)中确定最小的,v,1,1,3,9,5,3,8,3,6,2,v,6,v,5,v,3,v,4,v,2,9/23/2024,39,k,=3, 不是最优，继续,v,1,1,3,9,5,3,8,3,6,2,v,6,v,5,v,3,v,4,v,2,9/23/2024,40,k,=5, 不是最优，继续,v,1,1,3,9,5,3,8,3,6,2,v,6,v,5,v,3,v,4,v,2,9/23/2024,41,k,=6=,n, 已经是最优。如果希望计算,v,1,到,v,4,的最短距离，继续,v,1,1,3,9,5,3,8,3,6,2,v,6,v,5,v,3,v,4,v,2,9/23/2024,42,表格实现,v,1,1,3,9,5,3,8,3,6,2,v,6,v,5,v,3,v,4,v,2,9/23/2024,43,v,j,v,1,v,2,v,3,v,4,v,5,v,6,初始值,T,(,v,j,),0,9/23/2024,44,福德算法,适用于有负权，但无负回路的有向或无向网络，设,d,j,(k),为从,1,到,j,的边数不超过k的路线中距离最短的。,算法依据的思想是动态规划最优性原理，在此处形成递推公式：,其算法步骤如下：,令,计算,若对所有,j,则最优，否则把,k,的值加1，继续计算。,若,k,=,n,-1，则说明存在负回路，最短路线不存在。,9/23/2024,45,福德算法示例,v,1,1,3,9,5,3,8,3,6,2,v,6,v,5,v,3,v,4,v,2,9/23/2024,46,v,1,1,3,9,5,3,8,3,6,2,v,6,v,5,v,3,v,4,v,2,9/23/2024,47,v,1,1,3,9,5,3,8,3,6,2,v,6,v,5,v,3,v,4,v,2,0,2,5,(2),10,(2),9,(3),9/23/2024,48,v,1,1,3,9,5,3,8,3,6,2,v,6,v,5,v,3,v,4,v,2,6,2,0,0,2,5,(2),10,(2),9,(3),10,(5),8,(3),10,5,2,0,9/23/2024,49,例,求：5年内，哪些年初购置新设备，使5年内的总费用最小。,解：（1）分析：可行的购置方案（更新计划）是很多的，,如： 1） 每年购置一台新的，则对应的费用为：,11+11+12+12+13 +5+5+5+5+5 = 84,2 )第一年购置新的，一直用到第五年年底，则总费用为：,11+5+6+8+11+18 = 59,显然不同的方案对应不同的费用。,第i年度,1 2 3 4 5,购置费,11 11 12 12 13,设备役龄,0-1 1-2 2-3 3-4 4-5,维修费用,5 6 8 11 18,9/23/2024,50,（2）方法：将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。,求解步骤：,1）画赋权有向图：,设 V,i,表示第i年初，(V,i,V,j,)表示第i 年初购买新设备用到第j年初（j-1年底），而W,i j,表示相应费用，则5年的一个更新计划相当于从V,1,到V,6,的一条路。,2）求解 （标号法）,9/23/2024,51,W,12,=11+5=16,W,13,=11+5+6=22,W,14,=11+5+6+8=30,W,15,=11+5+6+8+11=41,W,16,=11+5+6+8+11+18=59,W,23,=11+5=16 W,24,=11+5+6=22,W,25,=11+5+6+8=30 W,26,=11+5+6+8+11=41,W,45,=12+5=17,W,46,=12+5+6=23,W,56,=13+5=18,W,34,=12+5=17,W,35,=12+5+6=23,W,36,=12+5+6+8=31,9/23/2024,52,11.4 网络最大流问题,所谓最大流问题就是在一定的条件下，要求流过网络的物流、能量流或信息流等流量为最大的问题，在最大流问题中一般有如下规定：,网络有一个起点,s,和一个终点,t,网络是有向网络，即流有方向性。,在网络各条弧上都有一个权，表示允许流过的最大流量。若以,b,ij,表示由,i,到,j,的弧上允许流过的最大流量，以,x,ij,表示实际流过该弧的流量，则,0,x,ij,b,ij,网络中，除起点,s,和终点,t,之外的任何顶点，流入量总和应该等于流出量的总和。,9/23/2024,53,最大流问题的数学模型,v,s,10,11,6,5,4,7,3,9,15,v,t,v,5,v,3,v,4,v,2,9/23/2024,54,最大流-最小割集定理,最大流最小割集定理揭示了最小割集（网络中的瓶颈）容量与最大流量的关系，也提供了一个求最大流的方法。,网络,割集容量,最小割集,所有割集中容量最小的一个割集。,流过网络的最大流量等于最小割集的容量,割集,9/23/2024,55,v,s,10,11,6,5,4,7,3,9,15,v,t,v,5,v,3,v,4,v,2,29,(,v,s,v,2,),(,v,3,v,2,) (,v,3,v,4,),(,v,3,v,5,),v,2,v,4,v,5,v,t,v,s,v,3,.,20,(,v,s,v,3,),(,v,2,v,4,) (,v,2,v,5,),v,3,v,4,v,5,v,t,v,s,v,2,24,(,v,s,v,2,),(,v,s,v,3,),v,2,v,3,v,4,v,5,v,t,v,s,容量,割集,S,S,9/23/2024,56,福德富克逊方法原理,算法的原理,首先,依据最大流问题的要求,为网络分配一个可行流。,所谓可行流,是指所有弧上流量满足容量限制,所有中间点满足平衡条件的流；,若这一可行流的流量就是最大流量，则问题已经解决；,若不是最大流量，则增加流量获得流量更大的可行流。,网络中的最大流量,f,max,值大小是由网络中最狭窄处瓶颈的容量所决定的。,9/23/2024,57,福德富克逊方法流图,9/23/2024,58,福德富克逊方法讨论,若弧(,v,i,v,j,)上的流量满足,x,ij,=b,ij,，则称该弧为,饱和弧,，否则称为,非饱和弧,。,若弧(,v,i,v,j,)上的流量,x,ij,=0。则称该弧为,零流弧,，否则称为,非零流弧,。,一条从,s,到,t,的初等链是由,s,开始的点、边序列，其中没有相同的点，也不考虑弧的方向。,把这条链中的,s,到,t,方向相同的弧称为,正向弧,。,把这条链中的,s,到,t,方向相反的弧称为,逆向弧,。,在上述的可行流中，从,s,到,t,的某个初等链满足：,其上的正向弧均为非饱和弧。,其上的逆向弧均为非零流弧。,则称该链为一条,流量增广链,。,9/23/2024,59,流量增广链,: 从,s,到,t,的某个初等链满足, 其上的正向弧均为非饱和弧。, 其上的逆向弧均为非零流弧。,结论：若在可行流中，存在从,s,到,t,的增广链，则该可行流不是最大流，其流量可以增加；否则若不存在从,s,到,t,的增广链，则该可行流是最大流。,增广链的性质：,V,s,到增广链上任一点也有增广链;,增广链上任一点到,V,t,也有增广链;,9/23/2024,60,福德富克逊方法步骤,为网络分配初始流,x,ij,标在图中弧旁的( )内,寻求增广链，若不存在，则已最优, 否则,在增广链上调整流量，产生新的可行流。,重复、两步，直到最优。,9/23/2024,61,寻求增广链的方法,寻求流量增广链的方法，是依据增广链的性质而产生的，其基本思路类似于最短树问题的生长法。,从,s,开始，逐个检查每个点,i,，看是否存在从,s,到,i,的增广链。,如果存在从,s,到,i,的增广链，,而（,V,i,V,j,）非饱和或（,V,j,V,i,）非零流，,则存在从,V,1,到,V,j,的增广链。,9/23/2024,62,福德富克逊方法示例,为网络分配初始流,x,ij,标在图中弧旁的( )内,v,s,10,11,5,6,4,7,3,9,15,v,t,v,5,v,3,v,4,v,2,(4),(9),(3),(1),(5),(7),(5),(8),9/23/2024,63,寻求增广链,从,s,开始，赋上标记（,，,），表示,s,是源点，能够得到任意多的量。,s,称为已标记的点。也表示增广链可以从,V,1,延伸到,V,1,v,s,10,11,5,6,4,7,3,9,15,v,t,v,5,v,3,v,4,v,2,(4),(9),(3),(1),(5),(7),(5),(8),-, ,9/23/2024,64,如果,v,i,是已经标记的点,v,j,是未标记的点,则当(,v,i,v,j,)是非饱和弧时,v,j,可以标记: ,v,i,+,e,j,e,j,=,min,e,i, b,ij,-x,ij,当(,v,j,v,i,)是非零流弧时,v,j,可以标记: ,v,i,-,e,j,e,j,=,min,e,i, x,ji,如果,v,t,可以标记,则找到增广链, 否则继续.,如果对于一切未标记的点, 均不能再标记, 则已经是最优.,9/23/2024,65,如图,v,1,是已经标记的点, 其它点是未标记的点,(,v,1,v,2,)是非饱和弧,v,2,可以标记: ,v,1,+,e,2,e,2,=,min,e,1,b,12,-x,12,(,v,1,v,3,)是饱和弧, 目前,v,3,和其它点暂时不能标记，即暂时没有从,v,1,到,v,3,或其它点的增广链。,v,s,10,11,5,6,4,7,3,9,15,v,t,v,5,v,3,v,4,v,2,(4),(9),(3),(1),(5),(7),(5),(8),-, ,v,s,+, 11,9/23/2024,66,如图,v,2,是已经标记的点,v,3,是未标记的点,(,v,3,v,2,)是非零流弧,v,3,可以标记: ,v,2,-,e,3,e,3,=,min,e,2, x,32,=,min,11,3,-, ,v,s,+, 11,v,2,-, 3,v,2,+, 4,v,3,+, 3,v,5,+, 4,v,s,11,5,4,3,15,v,t,v,5,v,3,v,4,v,2,(4),(9),(1),(5),(7),(5),(8),10,7,9,(3),6,9/23/2024,67,v,t,已经标记, 找到流量增广链。,v,s,10,11,5,6,4,7,3,9,15,v,t,v,5,v,3,v,4,v,2,(4),(9),(3),(1),(5),(7),(5),(8),-, ,v,s,+, 11,v,2,-, 3,v,2,+, 4,v,3,+, 3,v,5,+, 4,正向流流量增加,e,t,，逆向流流量减少,e,t,调整后流量,f,=17,9/23/2024,68,v,s,10,11,5,4,3,15,v,t,v,5,v,3,v,4,v,2,(8),(9),(3),(1),(5),(7),(9),(8),(4),9,6,7,-, ,v,s,+, 7,v,2,-, 3,v,3,+, 1,v,3,+, 3,v,4,+, 3,v,t,已经标记, 找到流量增广链。,9/23/2024,69,正向流流量增加,e,t,=3，逆向流流量减少,e,t,调整后流量,f,=20,v,s,10,11,5,4,3,15,v,t,v,5,v,3,v,4,v,2,(11),(9),(4),(5),(7),(9),(11),(4),9,6,7,9/23/2024,70,v,s,v,2,已经标记，其余点不能标记，已经最优,最大流量,f,max,=20,v,s,10,11,5,4,3,15,v,t,v,5,v,3,v,4,v,2,(11),(9),(4),(5),(7),(9),(11),(4),9,6,7,-, ,v,s,+, 4,9/23/2024,71,11.5 最小费用最大流问题,定义,已知网络G =(V，E，C，,d),，,f,是G上的一个可行流， 为一条从,v,s,到,v,t,的增广链， 称为链的费用。,若,*,是从,v,s,到,v,t,的增广链中费用最小的增广链，则称,*,是最小费用增广链。,结论,：如果可行流,f,在流量为W(,f,)的所有可行流中的费用最小，并且,*,是关于,f,的所有增广链中的费用最小的增广链，那么沿增广链,*,调整可行流,f,，得到的新可行流,f,*,也是流量为W(,f,*,)的所有可行流中的最小费用流。当,f,*,是最大流时，就是最小费用最大流。,9/23/2024,72,寻找关于,f,的最小费用增广链：,构造一个关于,f,的赋权有向图L(,f,) ，其顶点是原网络,G,的顶点，而将,G,中的每一条弧 (,v,i, v,j,)变成两个相反方向的弧（,v,i,，,v,j,）和(,v,j,v,i,)，并且定义图中弧的权,l,ij,为：,1.当 ，令,2.当（,v,j,，,v,i,）为原来网络G中（,v,i,，,v,j,）的反向弧，令,在网络,G,中寻找关于,f,的最小费用增广链等价于在L(,f,)中寻求从,v,s,到,v,t,的最短路。,9/23/2024,73,步骤：,（1）取零流为初始可行流 ，,f,(0) =0。,（2）一般地，如果在第k-1步得到最小费用流,f,(,k,-1),，则构造图 L(,f,(,k,-1),)。,（3）在L(,f,(,k,-1),)中，寻求从,v,s,到,v,t,的最短路。若不存在最短路，则,f,(,k,-1),就是最小费用最大流；否则转(4)。,（4）如果存在最短路，则在可行流,f,(,k,1),的图中得到与此最短路相对应的增广链，在增广链上，对,f,(,k,1),进行调整，调整量为：,9/23/2024,74,令,得到新可行流,f,(,k,),。对,f,(,k,),重复上面步骤，返回（2）。,例 求网络的最小费用最大流，弧旁权是（,b,ij, c,ij,）,(3 ,2),v,s,v,2,v,1,v,t,v,3,(1 ,4),(6 ,7),(4 ,8),(1 ,6),(2 ,5),(2 ,3),9/23/2024,75,3,v,s,v,2,v,1,v,t,v,3,1,6,4,1,2,2,(1) L(f,(0),),(3 ,2),v,s,v,2,v,1,v,t,v,3,(1 ,4),(6 ,7),(4 ,8),(1 ,6),(2 ,5),(2 ,3),0,v,s,v,2,v,1,v,t,v,3,3,0,0,3,3,3,(2) f,( 1),1,=3,W(f,(1),)=3,1,(3)L(f,(1),),2,3,v,s,v,2,v,1,v,t,v,3,1,6,4,1,2,1,2,9/23/2024,76,1,v,s,v,2,v,1,v,t,v,3,4,0,0,3,4,3,(4 ) f,( 2),2,=1,W(f,(2),)=4,(3 ,2),v,s,v,2,v,1,v,t,v,3,(1 ,4),(6 ,7),(4 ,8),(1 ,6),(2 ,5),(2 ,3),(5) L(f,(2),),3,v,s,v,2,v,1,v,t,v,3,1,4,1,2,2,2,3,1,6,1,v,s,v,2,v,1,v,t,v,3,4,0,1,4,5,3,(6 ) f,( 3),3,=1,W(f,(3),)=5,9/23/2024,77,(7) L(f,(3),),v,s,v,2,v,1,v,t,v,3,3,1,4,1,-2,2,3,1,6,1,v,s,v,2,v,1,v,t,v,3,4,3,4,4,5,0,(8 ) f,( 4),4,=3,W(f,(4),)=8,0,v,s,v,2,v,1,v,t,v,3,4,4,5,5,5,0,5,=1,W(f,(5),)=9,(10 )f,( 5),1,-2,3,1,v,s,v,2,v,1,v,t,v,3,3,4,1,2,6,(9) L( f,( 4),),-4,-6,9/23/2024,78,3,1,2,1,4,(11)L( f,( 5),),1,2,6,4,v,s,v,2,v,1,v,t,v,3,6,0,v,s,v,2,v,1,v,t,v,3,4,4,5,5,5,0,C (f,(5),)=63,W(f,(5),)=9,9/23/2024,79,第十一章习题,1、2、4、8,9/23/2024,80,