《ORnab图论》PPT课件.ppt

(vs , 4) (v1 , 3) (vs , 10) (v1 , 1) vs v1 vt v5 v4 v3 v2 （4, 0） （10, 0） （3, 3） （3, 0） （3, 0） （4, 0） （1, 0） （2, 0） （5, 3） （4, 0） （7, 0） （8, 3） (v2 , 2) (0 , +?) (v5 , 2) vs v1 vt v5 v4 v3 v2 （4, 2） （10, 0） （3, 3） （3, 2） （3, 0） （4, 0） （1, 0） （2, 0） （5, 5） （4, 0） （7, 0） （8, 5） (vs , 2) (v3 , 3) (vs , 10) (v2 , 3) vs v1 vt v5 v4 v3 v2 （4, 2） （10, 0） （3, 3） （3, 2） （3, 0） （4, 0） （1, 0） （2, 0） （5, 5） （4, 0） （7, 0） （8, 5） (v3, 4) (0 , +?) (v4 , 3) vs v1 vt v5 v4 v3 v2 （4, 2） （10, 3） （3, 3） （3, 2） （3, 3） （4, 0） （1, 0） （2, 0） （5, 5） （4, 3） （7, 3） （8, 5） vs v1 vt v5 v4 v3 v2 （4, 2） （10, 3） （3, 3） （3, 2） （3, 3） （4, 0） （1, 0） （2, 0） （5, 5） （4, 3） （7, 3） （8, 5） vs v1 vt v5 v4 v3 v2 （4, 2） （10, 6） （3, 3） （3, 2） （3, 3） （4, 3） （1, 0） （2, 0） （5, 5） （4, 3） （7, 3） （8, 8） (0 , +?) (vs , 2) (vs , 10) (v3, 4) (v5, 2) (v5, 3) 图5.19是联结某个起始地vs和目的地vt的交通运 输网，每一条弧vi 旁边的权cij表示这段运输线的最大 通过能力，货物经过交通岗从vs运送到vt.要求指定一 个运输方案，使得从vs到vt的货运量最大，这个问题 就是寻求网络系统的最大流问题。 问题描述 连通网络 G(V, A) 有 m 个节点, n条弧, 弧 eij 上的流 量上界为 cij, 求从起始节点 vs 到终点 vt 的最大流量。 图5.19 vt v3 v2 v1 v4 vs 17 3 5 10 8 6 11 4 5 3 Cij 二 基本概念 定义5.5 设一个赋权有向图D=（V,A）,在V 中 指定一个发点vs和一个收点vt ,其它的点叫做中间点。 对于D中的每一个弧（vi ,vj）∈A,都有一个权叫做弧 的容量。我们把这样的图 D 叫做一个网络系统， 简称网络，记做D=（V，A，C）（三元组表示）。 网络D上的流，是指定义在弧集合A上的一个函 数f ={f(vi ,vj)}={fjj} , f(vi ,vj)=fij叫做弧(vi ,vj)上的流量。 例如图6.19 就是一个网络。每一个弧旁边的 权就是对应的容量（最大通过能力）cij . 图6.20表示的就是这个网络上的一个流（运输 方案），每一个弧上的流量fij 就是运输量。例如 fs1= 5 , fs2= 3 , f13= 2 等等。 对于实际的网络系统上的流，有几个显著的特 点：(1)发点的总流出量和收点的总流入量必相等。 (2)每一个中间点的流入量与流出量的代数和等于 零。(3)每一个弧上的流量不能超过它的最大通过 能力（即容量）于是有： vt 图5.20 v3 v2 v1 v4 vs （17,2） (5 ,2) (10,5) （8 ,3) (6 , 3) (11, 6) (4,1） (5 , 1) （3,2） fij (3,3) 定义6.6 网络上的一个流f 叫做可行流，如果f 满足以下条件 （1）容量条件：对于每一个弧（vi ,vj）∈A,有 0 ? fij ? cij . （2）平衡条件： 对于发点vs,有 对于收点vt,有 对于中间点，有 任意一个网络上的可行流总是存在的。例如零 流v( f )=0,就是满足以上条件的可行流。 网络系统中最大流问题就是在给定的网络上寻 求一个可行流 f ,其流量 v(f ) 达到最大值。 设流f ={fij}是网络D上的一个可行流。我们把D 中 fij=cij 的弧叫做饱和弧，fijcij 的弧叫做非饱和弧， 其中发点的总流量（或收点的总流量） v ( f )叫做 这个可行流的流量。 fij0 的弧为非零流弧，fij=0 的弧叫做零流弧 .