图论动画-最小全局切割算法.ppt

1、15.082 和 6.855J,最小全局切割动画,2,初始化,饱和结点1发出的弧.,更新剩余网络,3,初始化,2,4,5,3,6,1,计算到结点2的距离,判定可进入弧,我们将再也不会从结点1推进或者推进到结点1内.,4,推进/重标号,2,4,5,3,6,1,选择一活动结点,1,Carry out 推进/重标号,1,3,2,5,6,4,1,1,3,4,6,5,1,6,4,1,3,3,2,5,推进/重标号,2,4,5,3,6,1,选择一活动结点,1,重标号. 不存在可进入弧.,1,3,2,5,6,4,1,1,6,4,6,5,1,6,4,1,3,2,6,推进/重标号,2,4,5,6,1,选择一活动结

2、点,1,从结点3 推进.,1,3,2,5,6,4,1,1,6,4,6,5,1,6,4,1,3,2,3,1,1,7,推进/重标号,2,4,5,6,1,选择一活动结点,1,重标号结点 3. 规则: 没有空层允许.,1,3,2,5,6,4,1,6,4,6,5,2,6,4,1,3,2,3,1,1,8,间隙,令 t 表示当前漏结点. 令 dmax 是除了源结点外的结点的最大距离标号. 空层是有值 k 且 d(t) k dmax 以至于没有结点j 是 d(j) = k. 如果我们把d(3)增加到 7, 我们创建了一个间隙.在这种情况下, 我们把d(j) 增加到 dmax + 1.,9,推进/重标号,2,4

3、,5,6,1,重标号结点 3 ，因此没有创建空层.,1,1,3,2,5,6,4,1,6,4,6,5,2,6,4,1,3,2,3,1,1,10,切割层,0,5,4,3,2,1,2,4,5,6,1,切割层 是仅有一个结点需要重标号的 层.,1,1,3,2,5,6,4,1,6,4,6,5,2,6,4,1,2,1,1,3,在剩余网络中，没有从切割层的结点到下方结点的路径.,11,切割-层 rule,总是选择在最低切割-层下方的活动结点. 如果每个活动结点是在或高于切割层, 那么停止，得到最大预流/ 最小切割.,12,推进/重标号,0,5,4,3,2,1,2,4,5,6,1,在最小切割层之下选择一活动结

4、点.,1,1,3,2,5,6,4,1,6,4,6,5,2,6,4,1,2,1,1,3,从结点 4 推进.,4,13,推进/重标号,0,5,4,3,2,1,2,4,5,6,1,在最小切割层之下选择一活动结点.,1,3,2,5,6,4,1,6,3,6,5,2,6,5,1,2,1,3,从结点 6 推进.,2,6,14,推进/重标号,0,5,4,3,2,1,2,4,5,6,1,在最小切割层之下选择一活动结点.,1,3,2,5,6,4,1,6,3,4,5,2,8,5,1,2,1,3,从结点 5 推进.,2,5,15,推进/重标号,0,5,4,3,2,1,2,4,5,6,1,在最小切割层之下选择一活动结点

5、.,1,3,2,5,6,4,2,6,3,4,5,2,8,5,2,1,3,重标号结点 5，如果它将不创建空层.,1,5,16,寻找首个切割结束,0,5,4,3,2,1,2,4,5,6,1,在最低切割层下不存在活动结点.,1,3,2,5,6,4,2,6,3,4,5,2,8,5,2,1,3,最大预流和最小切割已经被发现.,1,令T 是能到达漏结点所有结点.,17,结束寻找第一个切割,0,5,4,3,2,1,2,4,5,6,1,这是第一个最小切割.,3,1,3,2,5,6,4,1,1,1,5,3,4,6,18,开始第二个切割,0,5,4,3,2,1,2,4,5,6,1,在最低层选择新的漏结点,1,3,

6、2,5,6,4,2,6,3,4,5,2,8,5,2,1,3,使 结点 2 成为源结点,1,饱和从 结点 2出来的弧.,2,19,Beginning of the second 切割,0,5,4,3,2,1,2,4,5,6,1,我们将不再从结点 2推进或 推进到结点 2.,1,3,2,5,6,4,3,4,5,2,8,5,2,7,3,没有必要物理上合并结点 1和 2.,5,2,20,推进/重标号,0,5,4,3,2,1,2,4,5,6,1,选择一活动结点,1,3,2,5,6,4,3,4,5,2,8,5,2,7,3,重标号结点 3，如果它没有创建空层.,5,2,3,21,推进/重标号,0,5,4,3

7、,2,1,2,4,5,6,1,层 4 变成了一切割层,1,3,2,5,6,4,3,4,5,2,8,5,2,7,3,在切割层下，没有活动结点.,5,2,第二个切割已经发现.,令T 是所有能到达漏结点的结点,22,推进/重标号,0,5,4,3,2,1,2,4,5,6,1,这是第二次切割.,3,1,3,2,5,6,4,1,1,1,5,3,4,6,23,开始第三次切割,0,5,4,3,2,1,2,4,5,6,1,让结点 5 是源结点,1,3,2,5,6,4,3,4,5,2,8,5,2,7,3,结点 6 变成新的漏结点,5,2,饱和从结点 5发出的弧.,24,开始第3次切割,0,5,4,3,2,1,2,

8、4,5,6,1,层3 仍然是切割层,1,3,2,5,6,4,3,5,2,5,2,7,3,在切割层下，仍然没有活动结点结点.,5,2,我们已经发现了第3 个切割,令 T 是所有能从漏结点到达的结点.,25,第3 切割,0,5,4,3,2,1,2,4,5,6,1,上面的切割是最好的切割，1, 2, 5 在一边，结点 6 在另一边.,3,1,3,2,5,6,4,1,1,1,5,3,4,6,26,开始第4个切割,0,5,4,3,2,1,2,4,5,6,1,结点 6 变成一源结点,1,3,2,5,6,4,3,5,2,5,2,7,3,结点4 变成下一个源结点,5,2,饱和从结点6 发出的弧,27,我们已经找到第4和第5切割,0,5,4,3,2,1,2,4,5,6,1,1,3,2,5,6,4,5,2,9,3,5,2,在网络中仅有的弧是从源结点出来的弧