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

《图论动画-最小全局切割算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、3116推进/重标号05432124561选择一活动结点1重标号结点3.规则:没有空层允许.132564164652641323117间隙令t表示当前漏结点.令dmax是除了源结点外的结点的最大距离标号.空层是有值k且d(t)

3、网络中，没有从切割层的结点到下方结点的路径.10切割-层rule总是选择在最低切割-层下方的活动结点.如果每个活动结点是在或高于切割层,那么停止，得到最大预流/最小切割.11推进/重标号05432124561在最小切割层之下选择一活动结点.11325641646526412113从结点4推进.412推进/重标号05432124561在最小切割层之下选择一活动结点.132564163652651213从结点6推进.2613推进/重标号05432124561在最小切割层之下选择一活动结点.132564163452851213从结点5推进.2514推进/重标号05432124561在最小切割层

4、之下选择一活动结点.13256426345285213重标号结点5，如果它将不创建空层.1515寻找首个切割结束05432124561在最低切割层下不存在活动结点.13256426345285213最大预流和最小切割已经被发现.1令T是能到达漏结点所有结点.16结束寻找第一个切割05432124561这是第一个最小切割.3132564111534617开始第二个切割05432124561在最低层选择新的漏结点13256426345285213使结点2成为源结点1饱和从结点2出来的弧.25518Beginningofthesecond切割05432124561我们将不再从结点2推进或推进到

5、结点2.132564345285273没有必要物理上合并结点1和2.5219推进/重标号05432124561选择一活动结点132564345285273重标号结点3，如果它没有创建空层.52320推进/重标号05432124561层4变成了一切割层132564345285273在切割层下，没有活动结点.52第二个切割已经发现.令T是所有能到达漏结点的结点21推进/重标号05432124561这是第二次切割.3132564111534622开始第三次切割05432124561让结点5是源结点132564345285273结点6变成新的漏结点52饱和从结点5发出的弧.556623开始第3次

6、切割05432124561层3仍然是切割层1325643525273在切割层下，仍然没有活动结点结点.52我们已经发现了第3个切割令T是所有能从漏结点到达的结点.24第3切割05432124561上面的切割是最好的切割，1,2,5在一边，结点6在另一边.3132564111534625开始第4个切割05432124561结点6变成一源结点1325643525273结点4变成下一个源结点52饱和从结点6发出的弧664426我们已经找到第4和第5切割05432124561132564529352在网络中仅有的弧是从源结点出来的弧.我们能停止算法以及识别剩余的切割.27这是切割4和513256

7、411153461325641115346切割4切割528全局最小切割是切割数20543212456131325641115346算法结束时，结点1在源边，得到最小切割.29