第6章 图与网络优化(2012使用版).ppt

*/71 练习：某河流中有四个岛屿，从两岸至各岛屿及各岛屿之间的桥梁编号如下图。在一次敌对的军事行动中，问至少炸断几座及哪几座桥梁，才能完全切断两岸的交通联系。 D C A B E F 1 2 3 4 5 6 7 8 9 10 11 12 13 End */71 6.5 最小费用最大流问题 定义 已知网络D =（V，A，C，d），f是D上的一个可行流， 为一条从vs到vt的增广链，称 为这条增广链的费用。 对网络D＝（V，A，C），每一个弧（vi，vj）上给一个单位流量的费用（di，dj）≥0，记为dij。 最小费用最大流问题：求一个最大流f，使流的总输送费用 取最小值。 若 * 是从vs到vt的增广链中费用最小的增广链，则称 *是最小费用增广链。 */71 结论： 如果可行流 f在流量为v(f )的所有可行流中的费用最小，并且 μ *是关于f 的所有增广链中的费用最小的增广链，那么沿增广链 μ *调整可行流f，得到的新可行流f *也是流量为v(f*)的所有可行流中的最小费用流。当f * 是最大流时，就是最小费用最大流。 如何寻找这样的初始可行流。 （零流） 关键： 寻找最小费用增广链 转化： 求从vs到vt的最短路 同向 反向 两个 方向 */71 寻找关于f 的最小费用增广链： 构造一个关于f 的赋权有向图W(f ) ，其顶点是原网络G的顶点，而将G中的每一条弧 ( vi, vj )变成两个相反方向的弧（vi， vj）和(vj , vi)，并且定义图中弧的权lij为： 1.当 ，令 2.当（vj，vi）为原来网络G中（vi， vj）的反向弧，令 在网络G中寻找关于f 的最小费用增广链等价于在W(f )中寻求从vs 到vt 的最短路。 权为＋∞的弧可以从W（f）中略去。 */71 步骤： （1）取零流为初始可行流 ，f (0) ={0}。 （2）一般地，如果在第k-1步得到最小费用流 f (k-1)，则构造图 W( f (k-1) )。 （3）在W( f (k-1) )中，寻求从vs到vt的最短路。若不存在最短路，则f (k-1)就是最小费用最大流；否则转(4)。 （4）如果存在最短路，则在可行流f (k－1)的图中得到与此最短路相对应的增广链，在增广链上，对f (k－1)进行调整，调整量为： */71 令 得到新可行流f (k) 。对f (k)重复上面步骤，返回（2）。 例 求网络的最小费用最大流，弧旁权是（bij , cij）。 (3 ,2) vs v2 v1 vt v3 (1 ,4) (6 ,7) (4 ,8) (1 ,6) (2 ,5) (2 ,3) */71 3 vs v2 v1 vt v3 1 6 4 1 2 2 (1) W(f (0)) (3 ,2) vs v2 v1 vt v3 (1 ,4) (6 ,7) (4 ,8) (1 ,6) (2 ,5) (2 ,3) 0 vs v2 v1 vt v3 3 0 0 3 3 3 (2) f ( 1) ?1=3 L(f(1))=3 －1 (3) W(f (1)) －2 3 vs v2 v1 vt v3 1 6 4 1 2 －1 －2 */71 1 vs v2 v1 vt v3 4 0 0 3 4 3 (4 ) f ( 2) ?2=1 v(f(2))=4 (3 ,2) vs v2 v1 vt v3 (1 ,4) (6 ,7) (4 ,8) (1 ,6) (2 ,5) (2 ,3) (5) W(f (2)) －3 vs v2 v1 vt v3 －1 4 1 2 －2 －2 3 －1 6 6 1 vs v2 v1 vt v3 4 0 1 4 5 3 (6 ) f ( 3) ?3=1 v(f(3))=5 */71 (7) W(f (3)) vs v2 v1 vt v3 －3 －1 4 1 -2 －2 3 －1 6 1 vs v2 v1 vt v3 4 3 4 4 5 0 (8 ) f ( 4) ?4=3 v(f(4))=8 0 vs v2 v1 vt v3 4 4 5 5 5 0 ?5=1 v(f(5))=9 (10 )f ( 5) －1 -2 3 －1 vs v2 v1 vt v3 －3 4 1 2 6 (9) W( f ( 4)) -4 -6 */71 3 －1 2 －1 4 (11)W( f ( 5)) 1 2 6 －4 vs v2 v1