定义6.4.2给定网络D=(VA,C)。若对于每一条弧(，V)∈A,有一个数f,则称f={∫}为D 的流。 定义6.4.3给定网络D=(V,A,C),∫={∫}为D的流。若f满足： (1)容量限制条件：对每条弧(，y)∈A,有0≤∫≤C: (2)平衡条件： 对于每个中间点y,(≠s,):∑=∑f元 j(v)EA j)EA 对于发点y,:f)=∑，-∑f j)EA (v,)e4 对于收点：-)=∑，-∑ j(VV)EA J(V )EA 则称∫={f}是D的可行流，并且称(0为∫的流量。 例如，书P269图10-24。 对于网络D=(V,A,C),可行流总是存在的，例如f={f=0}(称为零流)，记作0，其流量为(=0。 设∫={f}为D=(V,A,C)的可行流。若∫=C,则称弧（化，'）为饱和弧，否则称为非饱和弧。若 ∫=0，则称弧(，y)为零弧，否则称为非零弧。 定义6.4.4给定网络D=(V,A,C),∫={f}为D的可行流。(0是D的所有可行流中流量最大的可 行流，则称∫={}为D的最大流。 数学模型： max v(f) s1.0≤f≤cg,(,",)eA ∑-∑f。=0,i≠s,1 j试，)EA j(vj)EA ，-∑je) j)EA (,,EA ∑f-∑fn=-f) j)EA F(Y,)E4 2.增广链 设4是网络D=(VA,C)中联结”，与y,的链，定义4的方向是从V,到y,则链上的弧有两类： 前向弧：弧的方向与链的方向一致，前向弧的全体记作： 反向弧：弧的方向与链的方向相反，反向弧的全体记作！。 例如，书P269图10-24 对4=(，2，，4，，V6),={,2),(2,),(,4),(,6)}，={,4)}。 定义6.4.5设4是网络D=(V,A,C)中联结y,与y,的链，和4分别是前向弧的全体和反向弧的全 体。若 f<C,(y,y)∈，f>0,(y,y)∈ 99 定义 6.4.2 给定网络 D=(V,A,C)。若对于每一条弧(, ) i j vv A ∈ ，有一个数 ij f ，则称 { }ij f = f 为 D 的流。 定义 6.4.3 给定网络 D=(V,A,C)， { }ij f = f 为 D 的流。若 f 满足： （1） 容量限制条件：对每条弧(, ) i j vv A ∈ ，有0 ij ij ≤ f ≤ c ； （2） 平衡条件： 对于每个中间点 ( ,) i v i st ≠ ： :( , ) :( , ) i j ji ij ji jvv A jv v A f f ∈ ∈ ∑ ∑ = 对于发点 s v ： :( , ) :( , ) ( ) s j js sj js jvv A jv v A vf f f ∈ ∈ = − ∑ ∑ 对于收点 t v ： :( , ) :( , ) ( ) t j jt tj jt jvv A jv v A vf f f ∈ ∈ −= − ∑ ∑ 则称 { }ij f = f 是 D 的可行流，并且称 v(f)为 f 的流量。 例如，书 P269 图 10-24。 对于网络 D=(V,A,C)，可行流总是存在的，例如 { 0} ij f f = = （称为零流），记作 f=0，其流量为 v(f)=0。 设 { }ij f = f 为 D=(V,A,C)的可行流。若 ij ij f = c ，则称弧(, ) i j v v 为饱和弧，否则称为非饱和弧。若 0 ij f = ，则称弧(, ) i j v v 为零弧，否则称为非零弧。 定义 6.4.4 给定网络 D=(V,A,C)， { }ij f = f 为 D 的可行流。v(f)是 D 的所有可行流中流量最大的可 行流，则称 { }ij f = f 为 D 的最大流。 数学模型： :( , ) :( , ) :( , ) :( , ) :( , ) :( , ) max ( ) . . 0 , ( , ) 0, , ( ) ( ) i j ji s j js t j jt ij ij i j ij ji jvv A jv v A sj js jvv A jv v A tj jt jvv A jv v A v f st f c v v A f f i st f f vf f f vf ∈ ∈ ∈ ∈ ∈ ∈ ≤≤∀ ∈ − = ∀≠ − = − =− ∑ ∑ ∑ ∑ ∑ ∑ 2．增广链 设 μ 是网络 D=(V,A,C)中联结 s v 与 t v 的链，定义 μ 的方向是从 s v 到 t v ，则链上的弧有两类： 前向弧：弧的方向与链的方向一致，前向弧的全体记作 μ+ ； 反向弧：弧的方向与链的方向相反，反向弧的全体记作 μ− 。 例如，书 P269 图 10-24 对 123456 μ = (, , , , , ) vvvvvv ， 12 23 34 56 μ {( , ),( , ),( , ),( , )} vv vv vv vv + = ， 5 4 μ {( , )} v v − = 。 定义 6.4.5 设 μ 是网络 D=(V,A,C)中联结 s v 与 t v 的链，μ+ 和 μ− 分别是前向弧的全体和反向弧的全 体。若 ,(, ) ij ij i j f c vv μ+ <∀ ∈ ， 0, ( , ) ij i j f vv μ− >∀ ∈