网络流问题

网络流问题一网络及网络流基本概念网络实例：铁路网、公路网、通信网、运输网等。实际的网络系统中都存在着流量和最大流问题。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。定义1网络：N=(V,E,c,X,Y)（1）G=(V,E)为有向图；（2）c为E上的非负函数，称为容量函数，c(e)称为边e的容量；（3）X与Y是V的两个非空不相交子集，分别称为收点集和发点集，I=V\(X∪Y)称为G的中间点集。X和Y的元素（顶点）分别被称为发点（源）以及收点（汇），I的元素（顶点）称为中间点。多源多汇网络、单源单汇网络多源多汇网络可转化为单源单汇网络。vtv3v2v1v4vs17,43,15,210,68,46,211,64,15,33,3每一个弧旁边的两个数字中前一个表示容量（最大通过能力），后一个表示目前的实际流量。实际问题通常要求指定一个运输方案，使得从vs到vt的货运量最大，这是寻求网络系统的最大流问题。例定义2设N为一个网络，f是E上的非负函数，如果满足（1）容量约束：0≤f(e)≤c(e),e∈E；（2）守恒条件：其中N+(v)表示v的所有出弧的集，N-(v)表示v的所有入弧的集。则称f是网络N上的一个(可行)流，f(e)是边e的流量。,,)()()()(IvefefvNevNe显然，任意一个网络至少存在一个流，如零流(f(e)=0,e∈I))()()(ANeefAf)()()(ANeefAf设，引入记号VA（集A的流出量）（集A的流入量）则守恒条件可是写成Ivvfvf),()(中间点v的流出量=流入量)()(AfAf定义3设f是网络N的一个流，则称为流出A的净流量，称为流入A的净流量。)()(AfAf引理设f是网络N的一个流，则即流出发点集X的净流量等于流入收点集Y的净流量。)()()()(YfYfXfXf定义4设f是网络N的一个流，则f的流的价值valf定义为即流的价值是发点的流出量，也是收点的流入量。)()(valXfXff定义1设N=(V,E,c,s,t)是一个网络，f是一个流，若不存在流f’，使得valf’valf则称f是N的最大流。二.最大流问题若则称网络N的一个割，而),(,,,AVAAtAsVA)(),(ANAA)},(|)({),(capAAeecAA即A的出弧的集称割的容量，而N的割中容量最小的割称为N的最小割。),(AA即A出弧的总容量最大流与最小割的关系定理1设f是网络N的流，是一个割，则),(AA).,(capval)2(),()(val)1(AAfAfAff定理2设f是流，K是割，若valf=capK，则f是最大流，K是最小割。定理3网络N的最大流的价值等与最小割的容量。增广链及最大流算法定义2设流f是网络N上的一个流。称N中f(e)=c(e)的弧e叫做f的饱和弧；f(e)c(e)的的弧e叫做f的非饱和弧；f(e)0的弧e为f的正弧；f(e)=0的弧e叫做f的零弧。定义3设P是网络N中从发点νs和收点vt的一条初等链(点、边不重复的有向路)，定义链的方向是从vs到vt，于是链P上的弧被分为两类：一是弧的方向与链的方向相同，叫做正向弧，正向弧的集合记做P+。二是弧的方向与链的方向相反，叫做反向弧，反向弧的集合记做P-。设，其中)(min)()(elPlPEePeefPeefecel),(),()()(若l(P)=0，则称链P为f-饱和链；若l(P)0，则称链P为f-非饱和链。定义4设f是一个流，P是s到t的一条链，若P满足下面两条件，则称P为关于流f的一条增广链：(1)．在弧e∈P+上，有0≤f(e)c(e)，即P+中的每一条弧是非饱和弧。(2)．在弧e∈P+上，有0f(e)≤c(e)，即P-中的每一条弧是非零弧。性质：一条f-增广链就是一条从发点s到收点t的f-非饱和链。在网络中存在一条增广链，表明f不是最大流。定理4f是最大流的充要条件是N不含f-增广链。其中)(min)()(elPlPEePeefPeefecel),(),()()(对于f-非饱和链，可以作如下的改进以增加流量：其它),(),()(),()()('efPePlefPePlefef对流f经上述改进后可得到一个新的流f’，有valf’=valf+l(P)，称之为基于P的改进流。最大流算法的基本思想判别网络N中当前给定的流f(初始时，可取f为零流)是否存在增广链，若没有，则该流f为最大流；否则，求出f的改进流f’，把f’看成f，再进行上述判断和改进，直到找到最大流为止。最大流算法——标号法标号过程实质上是寻找增广链并记录增广链可调整的流量值的过程，标号的对象是网络中的顶点。每个标号点的标号包含两部分：第一个标号表示这个标号是从那一点得到的，以便将来找出增广链；第二个标号是为了用来确定增广链上的调整量。首次标号前，对任意的弧e∈E，置f(e)=0。标号过程开始：1.先给发点s标号（s+，∞）。令δs=∞；2.若点x已标号，则对于与x相邻的点y，标号方法如下：a.如(x,y)∈E，当f(x,y)=c(x,y)时，y为不可标号点；当f(x,y)c(x,y)时，y为可标号点，此时计算δy=min{c(x,y)-f(x,y),δx}给y标号(x+,δy)。b.如(y,x)∈E，当f(x,y)=0时，y为不可标号点；当f(x,y)0时，y为可标号点，此时计算δy=min{f(x,y),δx}给y标号(x-,δy)。3.若重复进行2直至收点t被标号，说明增广链已找到，转入4，(进入调整流量的过程)；若不存在可标号的点，此时流f已是最大流了，程序停止；以下为增流过程：4.令u=t；5.若u的标号为(v+,δu)，则令f(v,u)=f(v,u)+δt若u的标号为(v-,δu)，则令f(v,u)=f(v,u)–δt6.若v≠s,令u=v，转5；若v=s，去掉除发点s外的所有点的标号，转2(开始下一轮寻找增广链的过程)；),(SS说明：算法终止时，若令已标号的点的集为S，则割即为最小割，从而最大流的流量为.),cap(valAAf例：各边的数字表示(C(e),f(e))，求最大流，最小割。V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,1）（2,2）（5,3）（1,1）（1,1）Vt(C(e),f(e))V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,2）（2,2）（5,3）（1,0）Vt(0，+∞)(vs,3)（1,0）结论：在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。三.最小费流问题可行流的一般概念网络N=(V,E,b,c,s,t)可行流的不一定存在。可行流的一般概念网络N=(V,E,b,c,s,t)可行流的不一定存在。求最大可行流的算法(P228)求初始可行流构造(P229)最小费用流的提法给定网络N=(V,E,b,c,s,t)和经过网络的流量f，求流在网络上的最佳分布，使总费用最小。最小费用流的数学模型：Ejijifjiw),(),(),(min其中f应该满足约束：Eji),(titsisiijfjifjj,,,0,),(),(其中w(i,j)表示(i,j)边的单位流费用；c(i,j)表示(i,j)边的容量；f(i,j)表示(i,j)边的流量；λ=valf.注：1.若valf为最大流，则问题为最小费用最大流问题(通常简称最小费用流问题)；2.valf大于最大流，则问题无解。最小费用流问题的算法(P230)