定义4设N是一个网络,其发点为S,收点为 SsV,S=V-S,使得S∈S,t∈S,(S,S)表示 点在S中,终点在S中的弧集。则称(S,S)为网络N 的截集; 称C(S,S)=Σ<>∈s5Cn为截集(S,S)的容量,简 i∈S,j∈S) 称截量; 具有最小容量的截集称为最小截集。 202l/12/10 重庆邮电大学 理学院
2021/12/10 重庆邮电大学 理学院 11
如图41.3所示网络N,每条边上标的前后两个数分别表示该边的容量和当 过该边的流量,该网络流N的流F是一个可行流,其流量V(F)=10。若取 S={s,V2},则(S,S)={<.v4<vv4<V2V4<V2t习是网络的一个截集 其截量为: C(S,S)=C(<,v4>)+C(<,v4>)+C(<v2yv4>)+C(<n2,t>)=7+5+2+5=19 19,5 8.6 5,5 2,2 10.5 9,7 41.3截集及容量 2021/12/10 重庆邮电大学 理学 12 院
如图 4.1.3 所示网络 N ，每条边上标的前后两个数分别表示该边的容量和当前流 过该边的流量，该网络流 N 的流 F 是一个可行流,其流量 V( ) 10 F = 。若取 { , , } 1 2 S = s v v ，则 4 1 4 2 4 2 ( , ) { , , , , , , , } S S s v v v v v v t = 是网络的一个截集， 其截量为： ( , ) ( , ) ( , ) ( , ) ( , ) 7 5 2 5 19 C S S = C s v4 +C v1 v4 +C v2 v4 +C v2 t = + + + = 4.1.3 截集及容量 2021/12/10 重庆邮电大学 理学 院 12
定理2设F是网络N=<N,E,C>的流,(S,S) 网络N的截集,则(S,S)的容量大于或等于F的值 即V(F≤C(S,S)。 021/12/10 重庆邮电大学 理学院
2021/12/10 重庆邮电大学 理学院 13
定理3设F是网络N=<N,E,C>的流,(S,S是 络N的截集. (1)若C(S,S)=V(F),则流F最大且截集(S,S)最小 (2)V)=C(S,S当且仅当"=c/l∈S∈S Fij=0,i∈S,j∈S 021/12/10 重庆邮电大学 理学院 14
2021/12/10 重庆邮电大学 理学院 14
如图414所示网络N,每条边上标的前后两个数分别 示该边的容量和当前流过该边的流量,该网络流N的流 是一个可行流,其流量V(F=10。若取S={S,v1,v4}, 则(S,S)是网络的一个截集,其截量为 C(S,S)=C(<v1,v2>)+C(<v4,v3>)=10 此时,流的值和截集的容量都为10,所以,流量最大且 截集最小。 5,5 76 62 10.3 5.5 图414最小截集 021/12/10 重庆邮电大学 理学院 15
图 4.1.4 最小截集 10,3 5,1 7,6 5,4 9,7 5,5 6,2 5,5 2021/12/10 重庆邮电大学 理学院 15