教程：最大流-最小割定理.ppt

《教程：最大流-最小割定理.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最大流最小割定理网络流之二一、割的有关概念和定量1、割的定义：割（CUT）是网络中顶点的一个划分，它把网络中的所有顶点划分成两个顶点集合S和T，其中源点s∈S，汇点t∈T。记为CUT（S,T）。如右图：源点：s=1；汇点：t=5。框外是容量，框内是流量12435642345412124352331st1）、顶点集合S={1，2，3}和T={4，5}构成一个割。12435642345412124352331st12435642345412124352331st2）、顶点集合S={1，3}，T={2，4，5}构成一个割。12

2、435642345412124352331st3）、顶点集合S={1，3，5}，T={2，4}不能构成一个割。？◆如果一条弧的两个顶点分别属于顶点集S和T（一个顶点在S，另一个在T），那么这条弧称为割CUT（S,T）的一条割边。◆从S指向T的割边是正向割边；◆从T指向S的割边是逆向割边。如：顶点集合S={1，3}，T={2，4，5}构成一个割。12435642345412124352331st正向割边：12;35逆向割边：23◆割CUT（S,T）中所有正向割边的容量和称为割CUT（S,T）的容量。不同割的容量不同。

3、12435642345412124352331st容量为：3+4=712435642345412124352331st割的容量：4+4=8割的正向流量：4+2=6逆向割的流量：12、网络流与割的关系：12435642345412124352331st网络流量：51234割正逆161250350450割的流量定理一：如果f是网络中的一个流，CUT（S,T）是任意一个割，那么f的值等于正向割边的流量与负向割边的流量之差。证明：设X和Y是网络中的两个顶点集合，用f（X,Y）表示从X中的一个顶点指向Y的一个顶点的所有弧（弧尾在X

4、中，弧头在Y中：XY）的流量和.只需证明：f=f(S,T)-f(T,S)即可。如果X∩Y=，那么：f(X,(Y1∪Y2))=f(X,Y1)+f(X,Y2)f((X1∪X2),Y)=f(X1,Y)+f(X2,Y)成立。下列结论成立：根据网络流的特点：如果V既不是源点也不是汇点，那么：f({V},S∪T)-f(S∪T,{V})=0;任何一个点，流入的与流出的量相等。如果V是源，那么：f({V},S∪T)-f(S∪T,{V})=f对于S中的所有点V都有上述关系式，相加得到：f(S,S∪T)-f(S∪T,S)=f又因为：f(S

5、,S∪T)-f(S∪T,S)=(f(S,S)+f(S,T))-(f(S,S)+f(T,S))=f(S,T)-f(T,S)所以：f=f(S,T)-f(T,S)定理得证推论1：如果f是网络中的一个流，CUT（S,T）是一个割，那么f的值不超过割CUT（S,T）的容量。f=f(S,T)-f(T,S)<=f(S,T)<=割CUT（S,T）的容量推论2：网络中的最大流不超过任何割的容量定量2：在任何网络中，如果f是一个流，CUT（S,T）是一个割，且f的值等于割CUT（S,T）的容量，那么f是一个最大流，CUT（S,T）是一个最小

6、割（容量最小的割）。令割CUT（S,T）的容量为C，所以流f的流量也为C。假设另外的任意流f1，流量为c1，根据流量不超过割的容量，则c1<=c,所以f是最大流。假设另外的任意割CUT（S1,T1），容量为c1，根据流量不超过割的容量，所以有c1>=c,故，CUT（S,T）是最小割。证明：定量3：最大流最小割定量：在任何的网络中，最大流的值等于最小割的容量。12435642345212124354234522211122最大流：7S={1,2,3},T={4,5}Cut(S,T)是最小割，容量＝３＋４＝７结论1：最大流时

7、，最小割cut（S，T）中，正向割边的流量=容量，逆向割边的流量为0。否则还可以增广。结论2：在最小割中cut（S，T）中：①源点s∈S。②如果i∈S，结点j满足：有弧,并且c[I,j]>f[I,j]或者有弧并且f[j,i]>0,那么j∈S。//否则不是最小割即从s出发能找到的含有残留的点组成集合S。其余的点组成集合T。怎样求集合S？数组b[i]记录增广路径上结点i的前驱结点。初始值b[]=-1，b[1]=0；假设1是源点。如果b[i]〉-1（有前驱，能从源点1找到的点），那么，i∈S。怎样求正向割边

8、和逆向割边？水流管道的最大流量由最细的管子容量决定的二、最大流最小割定量的应用1、太空飞行计划问题【问题描述：】W教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1，E2，…，Em}，和进行这些实验需要使用的全部仪器的集合I={I1，I