第4节 网络最大流问题.ppt

网络最大流问题—问题的提出 网络中存在流量限制时，求解一条线路使得从起点与终点之间可通过的流量最大。 标号法的思路 网络最大流问题—标号法 1.标号过程 给vs标上(0，+∞)，这时vs是标号而未检查点，其余为未标号点。 若在弧(vi，vj)上，fijcij，则给vj标(vi，l(vj))， 其中 若在弧(vj，vi)上，fji0，则给vj标(-vi，l(vj))， 其中 于是vi成为标号而已检查过的点，重复上述步骤， 一旦vt被标号，表明得到一条从vs到vt的增广链，转入 2.调整过程 如果所有标号已检查过，而标号不能进行下去，则算法结束，这时可行流为最大流。 网络最大流问题—标号法 1.标号过程 2.调整过程 作 业 P271， 8.14 (4) 重复（2）,（3），依次进行的结局可能为 vt已标号，得到一条增广链u(反向追踪)，转（5）； vt未标号,且无法再标号,此时的流为最大流,此时的截集为最小截。 v2 Vs v1 v4 v3 Vt （3,3） （5,1） （1,1） （2,2） （1,1） （5,3） （2,1） （4,3） [0, +∞] [vs, 4] [-v1, 1] [v2 , 1] （3,0） [v4 , 1] v2 Vs v1 v4 v3 Vt （3,3） （5,1） （1,1） （2,2） （1,1） （5,3） （2,1） （4,3） [0, +∞] [vs, 4] [-v1, 1] [v2, 1] （3,0） [-v2, 1] [v4 , 1] (5) 调整。取 ，令 ，得新流 ,转(1)。 v2 Vs v1 v4 v3 Vt （3,3） （5,1） （1,1） （2,2） （1,1） （5,3） （2,1） （4,3） [0, +∞] [vs, 4] [-v1, 1] [-v2, 1] （3,0） [-v2, 1] [v4, 1] v2 Vs v1 v4 v3 Vt （3,3） （5,2） （1,0） （2,2） （1,1） （5,4） （2,1） （4,4） （3,0） 调整 v2 Vs v1 v4 v3 Vt （3,3） （5,2） （1,0） （2,2） （1,1） （5,4） （2,1） （4,4） （3,0） [0 ,+∞] [vs, 3] v2 Vs v1 v4 v3 Vt （3,3） （5,2） （1,0） （2,2） （1,1） （5,4） （2,1） （4,4） （3,0） [0, +∞] [vs , 3] 此时标号无法进行，当前流为最大流，最大流量为5；最小截为{(vs,v2), (v1,v3)}，截量为：5 * * 公路系统中的车辆流 §4 网络最大流问题 控制系统中的信息流 供水系统中的水流 金融系统中的现金流 问题背景 v1 v2 v3 v4 v5 v6 10 8 4 6 5 3 5 3 11 17 例：上图为V1到V6的一交通网，权表示相应运输线的最大通过能力，制定一方案，使从V1运到V6的运输产品数量最多。 设有网络D=(V, A, C)，其中C={cij}， cij为弧(vi,vj)上的容量，现在D上要通过一个流f={fij}， fij为弧(vi,vj)上的流量。 问题：如何安排fij，可使网络D上的总流量最大？ v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 1 2 2 1 3 3 6 2 一、一般提法： 二、最大流问题的模型 max v=v（f） 容量约束 平衡约束 s.t. v2 Vs v3 v4 v5 Vt 8 10 4 17 5 5 3 11 6 3 5 3 1 2 2 1 3 3 6 2 注：满足两约束条件的流f称为可行流，v(f)称为该可行流的流量 试分析下图是否是可行流? v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 1 2 1 1 3 3 6 2 三、基本概念与定理 1. 弧按流量分为 饱和弧 fij=cij 非饱和弧 fijcij 零流弧 fij=0 非零流弧 fij≠0 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 1 2 2 1 3 3 6 2 2. 增广链 f为一可行流，u为vs至vt的链，令u+={正向弧}， u-={反向弧}。若u+中弧皆非饱和，且u-中弧皆非零，则称u为关于f的一条增广链。 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 1 2 2 1 3 3 6 2 2. 增广链 f为一可行流，u为vs至vt的链，令u