运筹七图与网络理论.pptVIP

vs vt v4 v2 v3 v1 (15,4) (9,9) (3,3) (5,1) (6,5) (7,7) (10,5) (11,8) (4,0) (0,+∞) （2）检查与vs相邻的顶点v1，v2，因为(vs,v1)?E，并且fs1=4cs1=15，所以v1可以获得标号(vs,δ1)，其中δ1 =min{+∞, 15-4}=11。因为(vs,v2)?E，但fs2=cs2，所以v2不能标号。 (vs,11) vs vt v4 v2 v3 v1 (15,4) (9,9) (3,3) (5,1) (6,5) (7,7) (10,5) (11,8) (4,0) (0,+∞) （3）检查与v1相邻且没有标号的顶点v2，v3， v4，因为(v2,v1)?E，并且f210，所以v2可以获得标号(v1,δ2)，其中δ2 =min{δ1, f21}=min{9,3}=3。因为(v1,v4)?E，并且f14=0c14=4，所以v4可以获得标号(v1,δ4)，其中δ4 =min{9, 4-0}=4。因为(v1,v3)?E，但f13=c13，所以v3不能标号。 (vs,11) (v1,3) (v1,4) vs vt v4 v2 v3 v1 (15,4) (9,9) (3,3) (5,1) (6,5) (7,7) (10,5) (11,8) (4,0) (0,+∞) （4）检查与v2相邻且没有标号的顶点v3， 因为(v2,v3)?E，并且f23=1c23=5，所以v3可以获得标号(v2,δ3)，其中δ3 min{δ2, c23-f23 }=min{3,5-1}=3 。 (vs,11) (v1,3) (v1,4) (v2,3) vs vt v4 v2 v3 v1 (15,4) (9,9) (3,3) (5,1) (6,5) (7,7) (10,5) (11,8) (4,0) (0,+∞) (vs,11) (v1,3) (v1,4) (v2,3) （5）由于与v3相邻且没有标号的顶点为vt，并且vt也与已标号的顶点v4相邻，所以vt既可以以v3为基础获得标号(v3,δt)，也可以以v4为基础获得标号 (v4,δt’)。但为减少迭代次数，应选择δ1与δt’两者较大的给vt标号。因为δt= min{δ3, c3t-f3t}=min {3,3}=3, δt’ = min{δ4, c4t-f4t}= min {4,5}=4，所以vt的标号应取（v4,4）。 (v4,4) vs vt v4 v2 v3 v1 (15,4) (9,9) (3,3) (5,1) (6,5) (7,7) (10,5) (11,8) (4,0) (0,+∞) (vs,11) (v1,3) (v1,4) (v2,3) (v4,4) （II）调整过程 由于vt的第一个标号为v4，得到顶点v4，由v4的第一个标号为v1，得到顶点v1，由v1的第一个标号为vs，得到顶点vs ，由此得到关于可行流f的增广链μ={vs, v1, v4 , vt}，其中(vs,v1),(v1,v4) ,(v4,vt)为前向边。 vs vt v4 v2 v3 v1 (15,8) (9,9) (3,3) (5,1) (6,5) (7,7) (10,9) (11,8) (4,4) (0,+∞) (vs,11) (v1,3) (v1,4) (v2,3) (v4,4) （II）调整过程 由于δt=4，所以调整量为4，即增广链μ上的前向边流量加4。 vs vt v4 v2 v3 v1 (15,8) (9,9) (3,3) (5,1) (6,5) (7,7) (10,9) (11,8) (4,4) (0,+∞) 重新开始标号过程， （I）标号过程 （1）首先给发点vs标以(0,+∞). vs vt v4 v2 v3 v1 (15,8) (9,9) (3,3) (5,1) (6,5) (7,7) (10,9) (11,8) (4,4) (0,+∞) (vs,7) （2）检查与vs相邻的顶点v1，v2，因为(vs,v1)?E，并且fs1=8cs1=15，所以v1可以获得标号(vs,δ1)，其中δ1 =min{+∞, 15-8}=7。因为(vs,v2)?E，但fs2=cs2，所以v2不能标号。 vs vt v4 v2 v3 v1 (15,8) (9,9) (3,3) (5,1) (6,5) (7,7) (10,9) (11,8) (4,4) (0,+∞) (vs,9) (v1,3) （3）检查与v1相邻且没有标号的顶点v2，v3， v4，因为(v2,v1)?E，并且f210，所以v2可以获得标号(v1,δ2)，其中δ2 =min{δ1, f