P（Y）—P（X）= A（X，Y）
且 F（X，Y）〈C（X，Y）
令 R为所有弧的集合，该集合中的弧（X，Y）有
P（Y）—P（X）=A（X，Y）
且0〈F（X，Y）
令N为不在IUR内的所有弧的集合（只有在I与R中的弧才考虑改变流量，既只能在满足式（7-19）的弧上改变流量）。
第三步 改变流量。按照第二步中定义的I，R，N，执行最大流算法。在下述良种情况之一发生时，算法终止：1、从S已经运送总数为V的单位流量至T时，2、从S至T已不可能再运送更多的流，情况1发生时，最终流就是从S运送V单位流量至T的最小费用流。发生情况2时，检查现有的流是否为从S至T的最大流（检查方法；验证用流的增值算法最后着色后产生的截是否饱和）。如果是最大流，此时最终流就是最小费用流，则算法终止。如果不是最大流，转到第四步。
第四步：改变顶点数值。考虑流的增值算法所做的最后着色。对每一个未着色顶点X的顶点数值加1，既P（X）←P（X）+1，转第二步 EG12
用算法求如图最小费用流。
开始时，所有顶点数值都是0，除S外的所有顶点都未着色。执行算法的结果如下 迭代次数 0 1 2 3 P（S） P（A） P（B） P（T） 着 色 弧 0 0 0 0 0 1 1 1 0 1 2 2 0 1 2 3 着色顶点 S 无 （S，A） S，A （S，A），（A，B） S，A，B （S， ）（A，B）（B，T） S，A，B，T 顶点T已着色。从S 至T沿着链（S，A），（A，B），（B，T）可以运送2个单位流量。因
此，F（S，A）=2。F（A，B）=2，F（B，T）=2。将上面已着色的弧和顶点曲调着色，重复上述过程，结果如下 迭代次数 3 4 5 P（S） P（A） P（B） P（T） 着 色 弧 0 0 0 0 0 2 3 4 0 3 3 5 着色顶点 S 无 （S，B），（A，B） S，A，B （S，B ）（A，B）（A，T） S，A，B，T 顶点T已着色。从S至T沿着链（S，B），（A，B），（A，T）可以运送1个单位流量。因此，F（S，A）=2，F（S，B）= 1。F（A，B）=1，F（A，T）=1，F（B，T）=2。对弧和顶点再抹去上面的着色，重复上述过程，结果如下 迭代次数 5 P（S） P（A） P（B） P（T） 着 色 弧 0 2 3 5 无 着色顶点 S 因为从已着色顶点至未着色顶点的弧（既（S，A）和（S，B））已经饱和，所以从S至T不能再运送追加的单位流量。因此，现有的3个单位的流就是具有最小费用的最大流。
下面修改算法，使其能适应非整数的弧的费用。
当弧的费用为非整数时，从S至T的流的增值路的总费用不一定是整数，因而，算法必须检验不是整数的P值。算法应该检验那些P的值？应该给顶点数值以多大增量呢？
设算法对P=P（T）的某些值已执行过。某些弧有一个顶点已着色，而另一个顶点未着色，必须考虑以下两种情况：
1、 如果X已着色，Y未着色，则仅当（X，Y）∈I，且P（Y）可以改变， 使 P（Y）—P（X）= A（X，Y）时，弧（X，Y）是可供选择的着色弧。如果 （X，Y）∈I，则有
P（Y）—P（X）≤A（X，Y）
因而，在弧（X，Y）可以着色之前，P（Y）必须增加A（X，Y）—P（Y）+P（X）个单位，令δ（X，Y）= A（X，Y）—P（Y）+P（X）
2、如果 Y已着色，X 未着色，则仅当 （X，Y）∈R 且P（X）可以改变使P（Y）-P（X）=A（X，Y）时，弧（X，Y） 是可供选择的着色弧。如果（X，Y）∈R 则有 P（Y）-P（X）≥A（X，Y）
因而，在弧（X，Y）可以着色之前，P（X） 必须增加 P（Y）-P（X）-A（X，Y）个单位，令δ（X，Y）=P（Y）-P（X）- A（X，Y）。 如果弧不适于1、2两种情况，则令
δ=MIN（X，Y）{δ（X，Y）}>0 （7-20）
因此，如果每个未着色顶点X的对应数值 P（X） 增加 δ ，则至少有另一条弧可以着色，并且可能找到一条新的流的增值链。所以 P（T） 的值将增加 δ 。同样地，为保证至少有另一条弧可以着色，需要有最小的增量，确定这个增量，就可以算出以后各个顶点数值的增量。如果δ=∞ ，则没有另外的弧可以着色。此时，现有的流就是最大流。 算法有下列三个缺点：
1、 算法必须从0流开始，并且按每个单位逐一增加到最大流。
2、 如果在算法终止后，发现使用了错误的弧的费用或容量，此时没有简单的方法可以不久
算法的错误结果
3、 在一条弧的流上不允许有非0下界，而且不允许有负的弧费用
第四讲 有向图的先深搜索与强连通性
图的常用表示方法：图（最直观），邻接表（矩阵）[有向，无向] 森林：由若干棵树构成。
利用邻接表，我们可以用无向图的先深搜索算法找出有向图G（V，E）的一个有向生成森林。
输入：用邻接表L（v）表示的图G=（V，E） 输出：树边集合T和后向边集合B。 方法：假设开始时所有的顶点标记为“新”，对顶点v邻接的边（v,w）使用递归过程search（v）第一次搜索到w,则将边（v，w）放入T中，同时将顶点改标记为“旧”。 Begin 1.T?@
2. for V中的所有v do 把v标记为“新”
3．While在v中有一标记“新”的顶点v do search（v） end
procedure search(v) begin 1.标记v为“旧”
2．For w标记“新” then
begin 4。将（v，w）放入T search（w） end
end
举7-23例：
V1 V2
V1
V3
V2 V5 V6
V5 V4
V3 V4 V7
V7 V8
用先深方法搜索后的结果
V6
对有向图进行先深搜索时，其弧分为四类：1树弧2前向弧3后向弧4横向弧 强连通的有向图的定义：给定有向图G=（V，E），划分V为等价类Vi使顶点v与w
V8 等价，当切仅当从v到w，而且从w到v都存在一条路径。设Ei是头和尾均在Vi中的弧集，则Gi=（Vi，Ei）称为G的强连通成分。
可以看到在7—23中有3个强连通成分，因此它不是强连通的有向图。
为了寻找根，定义函数LOWLINK如下：LOWLINK（v）=MIN（{v}并{w|有一条从v的一个子孙到w的横向弧或后向弧，且包含w的强连通成分的根是v的一个祖先}）
顶点v是有向图G的强连通成分的根当且仅当LOWLINK（v） =v。 procedure SEARCHC(v): begin
1. 标记v为“旧”
2. DFNUMBER（v）?COUNT 3. COUNT? COUNT+1
4. LOWLINK(v)?DFNUMBER(v) 5. v推入STACK
6. for L（v）中的每个顶点w do 7. if w标记“新” then 8. begin
9. SEARCHC（w）
10. LOWLINK（v）? MIN(LOWLINK(V),LOWLINK(W)) 11. end 12. else
13. if DFNUMBER(W) 19. 由 STACK 的顶退x 20. print x 21. end 22. until x= v 23. print “强连通成分结束” 24. end 25. end 算法：求有向图的强连通成分。 输入：有向图G=（V，E） 输出：G的强连通成分的表格。 Begin COUNT?1 FOR v 中所有的v do v标记“新” 置STACK初值为空 while存在一个标记“新”的顶点v do SEARCHC（V） end 用7—23例说明这段程序。 LOWLINK（1）=1=LOWLINK（2）=LOWLINK（3） LOWLINK（4）=3 LOWLINK（5）= 4 定理7—5 算法7-12在一个有n个顶点和e条弧的有向图G上，在O （MAX（n,e））时间内正确的找出G 的强连通成分。
相关推荐：
loading