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

null15.082 和 6.855J 15.082 和 6.855J 最小全局切割动画初始化初始化饱和结点1发出的弧.更新剩余网络初始化初始化245361计算到结点2的距离判定可进入弧我们将再也不会从结点1推进或者推进到结点1内.推进/重标号推进/重标号245361选择一活动结点1Carry out 推进/重标号1325641134651641332推进/重标号推进/重标号245361选择一活动结点1重标号. 不存在可进入弧.132564116465164132推进/重标号推进/重标号24561选择一活动结点1从结点3 推进.132564116465164132311推进/重标号推进/重标号24561选择一活动结点1重标号结点 3. : 没有空层允许.13256416465264132311间隙间隙令 t 表示当前漏结点. 令 dmax 是除了源结点外的结点的最大距离标号. 空层是有值 k 且 d(t) < k < dmax 以至于没有结点j 是 d(j) = k. 如果我们把d(3)增加到 7, 我们创建了一个间隙.在这种情况下, 我们把d(j) 增加到 dmax + 1.推进/重标号推进/重标号24561重标号结点 3 ，因此没有创建空层.113256416465264132311切割层切割层05432124561切割层 是仅有一个结点需要重标号的 层. 11325641646526412113在剩余网络中，没有从切割层的结点到下方结点的路径.切割-层 rule切割-层 rule总是选择在最低切割-层下方的活动结点. 如果每个活动结点是在或高于切割层, 那么停止，得到最大预流/ 最小切割.推进/重标号推进/重标号05432124561在最小切割层之下选择一活动结点.11325641646526412113从结点 4 推进.4推进/重标号推进/重标号05432124561在最小切割层之下选择一活动结点.132564163652651213从结点 6 推进.26推进/重标号推进/重标号05432124561在最小切割层之下选择一活动结点.132564163452851213从结点 5 推进.25推进/重标号推进/重标号05432124561在最小切割层之下选择一活动结点.13256426345285213重标号结点 5，如果它将不创建空层.15寻找首个切割结束寻找首个切割结束05432124561在最低切割层下不存在活动结点.13256426345285213最大预流和最小切割已经被发现.1令T 是能到达漏结点所有结点.结束寻找第一个切割结束寻找第一个切割05432124561这是第一个最小切割.31325641115346开始第二个切割开始第二个切割05432124561在最低层选择新的漏结点13256426345285213使 结点 2 成为源结点1饱和从 结点 2出来的弧.2Beginning of the second 切割Beginning of the second 切割05432124561我们将不再从结点 2推进或 推进到结点 2. 132564345285273没有必要物理上合并结点 1和 2.52推进/重标号推进/重标号05432124561选择一活动结点132564345285273重标号结点 3，如果它没有创建空层.523推进/重标号推进/重标号05432124561层 4 变成了一切割层132564345285273在切割层下，没有活动结点. 52第二个切割已经发现. 令T 是所有能到达漏结点的结点推进/重标号推进/重标号05432124561这是第二次切割.31325641115346开始第三次切割开始第三次切割05432124561让结点 5 是源结点132564345285273结点 6 变成新的漏结点52饱和从结点 5发出的弧.开始第3次切割开始第3次切割05432124561层3 仍然是切割层1325643525273在切割层下，仍然没有活动结点结点.52我们已经发现了第3 个切割令 T 是所有能从漏结点到达的结点.第3 切割第3 切割05432124561上面的切割是最好的切割，1, 2, 5 在一边，结点 6 在另一边.31325641115346开始第4个切割开始第4个切割05432124561结点 6 变成一源结点1325643525273结点4 变成下一个源结点52饱和从结点6 发出的弧我们已经找到第4和第5切割我们已经找到第4和第5切割05432124561132564529352在网络中仅有的弧是从源结点出来的弧.我们能停止算法以及识别剩余的切割.这是切割4和5这是切割4和513256411153461325641115346切割 4切割 5全局最小切割是切割数 2全局最小切割是切割数 2算法结束时，结点1在源边，得到最小切割.