运筹学 Operations Research f(s)=f(s\s)=∑f(s,v (S,")∈(s,s) ()=f(V,1)=∑ (v,D)∈(t},t) 可行流( feasible flow): (1)va∈A,有0≤f(a)≤c(a) (2)f(s)=f(t);vv∈l,有f(s)=f(t) 流值( flow value):vakf)=f*(s)=f() 2021/2/20 6
2021/2/20 6 运 筹 学 Operations Research + = = ( , ) ( , \{ }) ( ) ( , \{ }) ( , ) s v s V s j j f s f s V s f s v − = = ( , ) ( \{ }, ) ( ) ( \{ }, ) ( , ) v t V t t j j f t f V t t f v t 可行流（feasible flow）： (1)a A，有0 f (a) c(a) (2) f (s) f (t) v I f (s) f (t) + − + − = ； ，有 = 流值（flow value）： val( f ) f (s) f (t) + − = =
运筹学 Operations Research 零流( zero flow):弧的流量都是0的流. 显然,零流是一个可行流,且流值为0 最大流( maximum flow):流值最大的可行流 最大流问题:在网络中找一个最大流 弧的分类: 1)按流量和容量的大小关系分: 饱和弧( saturated arc):f(a)=c(a) 不饱和弧( unsaturated arc):f(a)<c(a 2021/2/20 7
2021/2/20 7 运 筹 学 Operations Research 零流（zero flow）：弧的流量都是0的流. 显然，零流是一个可行流，且流值为0. 最大流（maximum flow）：流值最大的可行流. 最大流问题：在网络中找一个最大流. 弧的分类： （1）按流量和容量的大小关系分： 饱和弧（saturated arc）： 不饱和弧（unsaturated arc）： f (a) = c(a) f (a) c(a)
运筹学 Operations Research (2)按流量和0的大小关系分: 零弧( zero arc):f(a)=0 非零弧( nonzero arc, positive arc):f(a)>0 (3)按流量和有向路的关系分: 设是一条有向(s,t)-路,其方向为s→t 8o>0>0>≤0>t 前(正)向弧( forward arc):与P的方向一致的弧 后(反)向弧( forward arc):与P的方向相反的弧 2021/2/20 8
2021/2/20 8 运 筹 学 Operations Research （2）按流量和0的大小关系分： 零弧（zero arc）： 非零弧（nonzero arc，positive arc）： f (a) = 0 f (a) 0 （3）按流量和有向路的关系分： 设P是一条有向(s，t)-路，其方向为s→ t. 前（正）向弧（forward arc）：与P的方向一致的弧 后（反）向弧（forward arc）：与P的方向相反的弧
运筹学 Operations Research 可增广路( augmenting path):前向弧均为不饱和弧,后 向弧均为非零弧的路. Th1设是任一可行流,(S,S)是任一割,则 (1)val(O)≤c(S,S) (2)nal(f)=c(S,S)分(S,S)中的前向弧均为饱和弧, 后向弧均为零弧囗 Cor(1)若为最大流(S,S)为最小割,则vl()≤c(S,S) 2)最大流和最小割必存在 (3)若val(f)=c(S,S),则为最大流S,S)为最小割■ 2021/2/20
2021/2/20 9 运 筹 学 Operations Research 可增广路（augmenting path）：前向弧均为不饱和弧，后 向弧均为非零弧的路. . (2) ( ) ( , ) ( , ) (1) ( ) ( , ) 1 ( , ) 后向弧均为零弧 中的前向弧均为饱和弧， 设 是任一可行流， 是任一割，则 val f c S S S S val f c S S Th f S S = ▌ (3) ( ) ( , ) ( , ) . (2) . (1) ( , ) ( ) ( , ). 若 ，则 为最大流， 为最小割 最大流和最小割必存在 若 为最大流， 为最小割，则 val f c S S f S S Cor f S S val f c S S = ▌