第九讲 图及网络分析.ppt

13 (11) 9 (9) 4 (0) 5 (5) 6(6) 5 (5) 5 (4) 5 (4) 4 (4) 4 (3) 9 (9) 10 (7) 截集1 截集2 最小截量为：9+6+5=20 70（70） 70（50） 130（100） 150（130） 150（150） 50（20） 50（50） 120（30） 100（100） ∞ （120 ） ∞ （230 ） ∞ （150 ） ∞ （200 ） 第五节 最小费用最大流问题 定义8.17 已知网络D =（V,A，C，d），f是D上的一个可行流， 为一条从vs到vt的增广链， 称为链的费用。 若 * 是从vs到vt的增广链中费用最小的增广链，则称 * 是最小费用增广链。 结论：如果可行流 f在流量为v(f )的所有可行流中的费用最小，并且 *是关于f 的所有增广链中的费用最小的增广链，那么沿增广链 *调整可行流f，得到的新可行流f *也是流量为v(f*)的所有可行流中的最小费用流。当f * 是最大流时，就是最小费用最大流。 寻找关于f 的最小费用增广链： 构造一个关于f 的赋权有向图w(f ) ，其顶点是原网络D的顶点，而将D中的每一条弧 ( vi, vj )变成两个相反方向的弧（vi， vj）和(vj , vi)，并且定义图中弧的权wij为： 1.当 ，令 2.当（vj，vi）为原来网络D中（vi， vj）的反向弧，令 在网络D中寻找关于f 的最小费用增广链等价于在w(f )中寻求从vs 到vt 的最短路。 步骤： （1）取零流为初始可行流 ，f (0) ={0}。 （2）一般地，如果在第k-1步得到最小费用流 f (k-1)，则构造图 L( f (k-1) )。 （3）在L( f (k-1) )中，寻求从vs到vt的最短路。若不存在最短路，则f (k-1)就是最小费用最大流；否则转(4)。 （4）如果存在最短路，则在可行流f (k－1)的图中得到与此最短路相对应的增广链，在增广链上，对f (k－1)进行调整，调整量为： 令 得到新可行流f (k) 。对f (k)重复上面步骤，返回（2）。 例8.11 求网络的最小费用最大流，弧旁权是（bij , cij） (3 ,2) vs v2 v1 vt v3 (1 ,4) (6 ,7) (4 ,8) (1 ,6) (2 ,5) (2 ,3) 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 v(f(1))=3 －1 (3) w(f (1)) －2 3 vs v2 v1 vt v3 1 6 4 1 2 －1 －2 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 (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 3 －1 2 －1 4 (11) w( f ( 5)) 1 2 6 －4 vs v2 v1 vt v3 －6 第六节 中国邮递员问题 一、 欧拉回路与道路 定义8.18 连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。 具有欧拉回路的图称为欧拉图。 定理