、最大流问题 最大流问题就是在容量网络D中,求一个可行流仁{f},使其流量v(f) 达到最大。其数学模型为 maxv OsJn≤cn(v,")∈A 满足 vO) i ∑-∑/=|01≠.1 vo) i=t 显然,最大流问题是个特殊的LP问题可用单纯形法或表上作业法求 解,但利用它与图的紧密关系,能更为直观简便地求解。 三、求网络最大流的有关概念与原理 1增广链。设D=(VAC冲中,有一可行流f={f},按每条弧上流量的多 少,可将弧分四种类型 饱和弧(即fiwi) 非饱和弧(即fiwi) 零流弧(即fi=0) 非零流弧(即f>0) 如图13中,(v1,V4)是饱和弧,又是非零流弧,其它各弧均为非饱和弧, 也是非零流弧。 设μ是中D中从v别vt的一条链,沿此方向,从上各弧可分为两类: 正向弧(与链的方向一致的弧),其集合记为μ+ 反向弧(与链的方向相反的弧),其集合记为μ 如图13,在μ={v1,V2,v3,vv}中,μ+={(wsv2)(v1,v4)(v3,V)}, μ={(V2,v1),(v4,v3)} 对于可行流f,μ是一条从v到vt的链,若μ中的每弧均为非饱和弧 μ中的每弧均为非零流弧,是称链μ是关于f的增广链。 2截集(割集) 若将D=VAW)的V为两部分Vs和V,使vs∈Vsv∈V,且35 二、最大流问题 最大流问题就是在容量网络 D 中，求一个可行流 f={fij}，使其流量 v(f) 达到最大。其数学模型为 maxv(f) 满足            − =  = − =      v f i t O i s t v f i s f f O f c v v A ij ji ij ij i j ( ) , ( ) ( , ) 显然，最大流问题是个特殊的 LP 问题可用单纯形法或表上作业法求 解，但利用它与图的紧密关系，能更为直观简便地求解。 三、求网络最大流的有关概念与原理 1.增广链。设 D=(V,A,C)中，有一可行流 f={fij}，按每条弧上流量的多 少，可将弧分四种类型： 饱和弧(即 fij=wij) 非饱和弧(即 fij<wij) 零流弧(即 fij=0) 非零流弧(即 fij>0) 如图 13 中，(v1,v4)是饱和弧，又是非零流弧，其它各弧均为非饱和弧， 也是非零流弧。 设是中 D 中从 vs 别 vt 的一条链，沿此方向，从上各弧可分为两类： 正向弧（与链的方向一致的弧），其集合记为 + 反向弧（与链的方向相反的弧），其集合记为 - 如图 13，在={v1,v2,v3,v4,vt}中， +={(vs,v2),(v1,v4),(v3,vt)},  -={(v2,v1),(v4,v3)} 对于可行流 f, 是一条从 vs 到 vt 的链，若 +中的每弧均为非饱和弧，  -中的每弧均为非零流弧，是称链是关于 f 的增广链。 2.截集（割集） 若 将 D=(V,A,W) 的 V 为 两 部 分 Vs 和 Vs , 使 vsVs,vt Vs , 且