最小费用最大流问题.pptVIP

最小费用最大流问题最大流问题最小费用最大流问题最大流问题引例基本概念最大流算法算例Back引例假设某个公路网的每条公路只允许单向行驶，这样的公路网称为单行公路网．为了保证畅通，交通部门对每条公路在单位时间内通过的车辆数目要作一个限制．问单位时间内最多能有多少辆车从甲地出发经过该公路网到达乙地？网络与流增广链网络与流一个有向图称为一个网络．其中，为图的所有顶点集；为弧集；为各弧上容量集在中指定了两点，分别称为发点和收点，其余的点叫中间点．定义弧集合上的一个函数为网络的一个流,并称为弧上的流量，简记为可行流与最大流一个流称为一个可行流,如果满足以下条件:容量限制条件:对平衡条件:对中间点:流出量=流入量,即对于发点对于收点式中称为这个可行流的流量,即发点的净输出量(或收点的净输入量)最大流问题:、给定一个可行流称、若是网络中联结发点和收点的一条链,定义链的方向是从到,则链上的弧被分为两类:一类是弧的方向与链的方向一致,称为前向弧,前向弧的全体记为另一类弧与链的方向相反,称为后向弧,后向弧的全体记为、设f是一个可行流,是从到的一条链,称为一条增广链,如果增广链、设把始点在,终点在中的所有弧构成的集合,记为、给定网络若点集被剖分为两个非空集合01使则弧集称为分离和的截集.、截集中所有弧的容量之和称为此截集的容量,记为即02截集定理1可行流f是最大流不存在关于f的增广链.定理2任一个网络中,从到的最大流的流量等于分离的最小截集的容量.12求最大流的标号法(Ford,Fulkerson)1、标号过程开始:先给标上此时是标号而未检查的点,其余都是未标号点.一般地,取一个标号而未检查的点,对一切未标号点:(1)若在弧上则给标号,这里.此时,点成为标号而未检查的点.(2)若在弧上则给标号这里.此时,点成为标号而未检查的点.于是成为标号且已检查过的点.重复上述步骤,一旦被标上号,表明得到一条从到的增广链,转入调整过程.若所有标号都已经检查过,而标号过程进行不下去时,则算法结束,此时的可行流就是最大流.、调整过程Back寻找以为终点的增广链----(反向追踪法):调整量流的调整令去掉所有的标号,对新的可行流重新进入标号过程.算例用标号法求右下图所示网络的最大流.弧旁的数是解:(一)标号过程1、首先给标上2、检查在弧上不满足标号条件;在弧上则的标号为.其中,在弧上则的标号为.其中,在弧上则