则称4是（关于D的增广链。 例如，书P269图10-244=(1,2，y3,V4,V,6)为增广链。 定理6.4.1若可行流f为最大流，则D中不存在关于f的增广链。 证明：否则，设4是关于∫的增广链，令 0=min-人i. (E 则0>0。令f'=(f,4,),即 f+0,(vv,)Eu f写=f-6,(,y)∈业 , (,y)E4 则f是可行流，并且v(f")=(f)+日>v(f),与f为最大流矛盾。因此，D中不存在关于f的增广链。 4.截集和集量 定义6.4.6设S,TcV,SUT=V,S∩T=0,v,∈S,y,∈T,则 (S,T)={,y)∈A|y,eS,y,∈T} 称为（分离V,y,的）截集。 显然，若把某一截集的弧从网络中删去，则就不存在V,到y,的路。所以，直观上说，截集是从y,到 y,的必经之道。 定义6.4.7设(S,T)为（分离y,,的）截集，则 cS,T)=∑cg (vE(S.T) 称为截集(S,T)的截量。 可证明：对任一可行流f和任一截集(S,T),有v()≤c(S,T)。 若存在可行流∫和截集(S,T),使v(f)=c(S,T),则∫为最大流，而(S,T)是D的所有截集中截 量最小的截集，称为最小截集。 定理6.4.2设f为D的可行流，若D中不存在关于f的增广链，则∫为最大流。 证明：只要找到截集(S,T),使v(f)=c(S,T)即可。利用下面方法构造S: 令v,∈S: 若，∈S,<C,则令，∈S: 若y∈S,fm>0,则令v,∈S。 因为不存在关于∫的增广链，故y,S。令T=V八S,则(S,T)为截集，并且 cm,(,y)∈(S,T) (,y,)e(T,S) 由此知v(f)=c(S,T)。因此，f为最大流。 最大流量最小截量定理：任一网络D中，从V,到y,的最大流的流量等于分离y,y,的最小截集的截 1010 则称 μ 是（关于 f）的增广链。 例如，书 P269 图 10-24 123456 μ = (, , , , , ) vvvvvv 为增广链。 定理 6.4.1 若可行流 f 为最大流，则 D 中不存在关于 f 的增广链。 证明：否则，设 μ 是关于 f 的增广链，令 (, ) (, ) min{ min ( ), min } ij ij ij ij ij vv vv cf f μ μ θ + − ∈ ∈ = − 则θ > 0。令 f f ′ = (,,) μ θ ，即 , ( , ) , ( , ) , ( , ) ij i j ij ij i j ij i j f vv f f vv f vv θ μ θ μ μ + − ⎧ + ∈ ⎪⎪ ′ =− ∈ ⎨ ⎪ ∉ ⎪⎩ 则 f ‘ 是可行流，并且vf vf vf ( ) () () ′ = +> θ ，与 f 为最大流矛盾。因此，D 中不存在关于 f 的增广链。 4． 截集和集量 定义 6.4.6 设 ST V , ⊂ ， STV ∪ = ， S T ∩ = ∅ ， , s t v Sv T ∈ ∈ ，则 ( , ) {( , ) | , } ij i j ST v v Av Sv T = ∈ ∈∈ 称为（分离 ,s t v v 的）截集。 显然，若把某一截集的弧从网络中删去，则就不存在 s v 到 t v 的路。所以，直观上说，截集是从 s v 到 t v 的必经之道。 定义 6.4.7 设(, ) S T 为（分离 ,s t v v 的）截集，则 ( , )(, ) (, ) i j ij v v ST cST c ∈ = ∑ 称为截集(, ) S T 的截量。 可证明：对任一可行流 f 和任一截集(, ) S T ，有v f cST () (, ) ≤ 。 若存在可行流 f 和截集(, ) S T ，使v f cST () (, ) = ，则 f 为最大流，而(, ) S T 是 D 的所有截集中截 量最小的截集，称为最小截集。 定理 6.4.2 设 f 为 D 的可行流，若 D 中不存在关于 f 的增广链，则 f 为最大流。 证明：只要找到截集(, ) S T ，使v f cST () (, ) = 即可。利用下面方法构造 S ： 令 s v S ∈ ； 若 i v S ∈ ， ij ij f < c ，则令 j v S ∈ ； 若 i v S ∈ ， 0 ji f > ，则令 j v S ∈ 。 因为不存在关于 f * 的增广链，故 t v S ∉ 。令T VS = \ ，则(, ) S T 为截集，并且 , ( , ) ( , ) 0, ( , ) ( , ) ij i j ij i j c v v ST f vv TS ⎧⎪ ∈ = ⎨ ⎪ ∈ ⎩ 由此知v f cST () (, ) = 。因此，f 为最大流。 最大流量最小截量定理：任一网络 D 中，从 s v 到 t v 的最大流的流量等于分离 ,s t v v 的最小截集的截