可行流中矿=cj的弧叫做饱和弧，矿<c的弧叫做非饱和弧。矿>0的弧为非零流弧，前=0的弧叫 做零流那 3、容量网络G,若为网络中从vs到的一条链，给定向为从vs卧t,上的弧凡与方向相同的称为 前向弧，凡与方向相反的称为后向弧，其集合分别用+和-表示。 f是一个可行流，如果满捉下式： 则称为从vst的关于升的一条增广链 推论可行流是最大流的充分必要条件是不存在从vs到的关于升的一条可增广链。 (二)求最大流的标号法 标号过程： 1.给发点vs标号(0，+∞)， 2.取一个已标号的点i,对于vi一切未标号的邻接点按下列规则处理， (1)如果边，且>0，那么给i标号引-vi,,其中：j=min(你)： (2)如果边 (v,y,)∈E ，且<cj,那么给y标号+vi,,其中：j=min(cj-孤，： 3,重复步骤彩，直1被标号或标号过程无法进行下去，则标号结束。苟被标号，则存在一条增厂 链，转调整过程，若未被标号，而标号过程无法进行下去，这时的可行流就是最大流。 调整过程 2.去掉所有标号，回到第一步，对问行流重新标号。 6.5最小费用最大流问题 在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考 虑费用的问题。例收如一个铁路系统的运输网络流，既要考虑网络流的货运量最大，又要考虑总费用 最小。最小费用最大流问题就是要解决这一类问题。 定义已知网络G=N,E,C,d)，f是G上的一个可行流，为一条从vs的增广链，称为链的 芳用。 若是从Vs的增广链中费用最小的增广链，则称*是最小费用增广链。 结论：如果可行流在流量W)的所有可行流中的费用最小，并且·是关开的所有增广链中的费 用最小的增广链，那么沿增广链*调整可行流剂，得到的新可行流*也是流量为W什的所有可行流中 的最小费用流。当断*是最大流时，就是最小费用最大流。 寻找关于升的最小费用增广链： 1，其顶点是原网络G的顶点，而将G中的每一条弧（ⅵ，）变成两 当i,)E,令 当，v川为原网络G中ⅵi,)的反向弧，令 在网络G中寻找关于开的最小费用增广链等价于在L(什)中寻求从vs的最短路 步骤： (1)取零流为初始可行流，f(0)=0。 (2)一般地，如果在第孰-1步得到最小费用流f(k-1),则构造图L(f(k-1) 可行流中 fij＝cij 的弧叫做饱和弧，fij＜cij的弧叫做非饱和弧。fij＞0 的弧为非零流弧，fij＝0 的弧叫 做零流弧。 3、容量网络G，若 为网络中从vs到vt的一条链，给 定向为从vs到vt， 上的弧凡与 方向相同的称为 前向弧，凡与 方向相反的称为后向弧，其集合分别用 + 和 - 表示。 f 是一个可行流，如果满足下式： 则称 为从vs到vt 的关于f 的一条增广链。 推论 可行流f 是最大流的充分必要条件是不存在从vs到vt 的关于f 的一条可增广链。 （二） 求最大流的标号法 标号过程： 1． 给发点vs 标号（0，+∞）。 2． 取一个已标号的点vi，对于vi一切未标号的邻接点vj 按下列规则处理： （1）如果边 ，且 fji > 0，那么给vj 标号(-vi, j), 其中：j = min(fji, i)； ，且fji < cij ，那么给vj 标号(+vi, j)，其中：j = min(cij-fji, i)； 3．重复步骤2，直到vt被标号或标号过程无法进行下去，则标号结束。若vt被标号，则存在一条增广 链，转调整过程；若vt未被标号，而标号过程无法进行下去，这时的可行流就是最大流。 调整过程： 设 令 2．去掉所有标号，回到第一步，对可行流重新标号。 6.5 最小费用最大流问题 在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考 虑费用的问题。例如一个铁路系统的运输网络流，既要考虑网络流的货运量最大，又要考虑总费用 最小。最小费用最大流问题就是要解决这一类问题。 定义 已知网络G =（V，E，C，d），f是G上的一个可行流， 为一条从vs到vt的增广链， 称为链的 费用。 若*是从vs到vt的增广链中费用最小的增广链，则称 * 是最小费用增广链。 结论：如果可行流 f在流量为W(f )的所有可行流中的费用最小，并且 *是关于f 的所有增广链中的费 用最小的增广链，那么沿增广链 *调整可行流f，得到的新可行流f *也是流量为W(f*)的所有可行流中 的最小费用流。当f * 是最大流时，就是最小费用最大流。 寻找关于f 的最小费用增广链： 构造一个关于f 的赋权有向图L(f ) ，其顶点是原网络G的顶点，而将G中的每一条弧 ( vi , vj )变成两 个相反方向的弧( vi , vj )和(vj , vi)，并且定义图中弧的权lij为： 当( vi , vj )E，令 当(vj , vi)为原网络G中( vi , vj )的反向弧，令 在网络G中寻找关于f 的最小费用增广链等价于在L(f )中寻求从vs 到vt 的最短路。 步骤： （1）取零流为初始可行流，f (0) ={0}。 （2）一般地，如果在第k-1步得到最小费用流 f (k-1)，则构造图 L( f (k-1) )。 （2）如果边