最大流 最小割.ppt

《最大流 最小割.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最大流最小割定理割的定义割是网络中定点的一个划分，它把网络中的所有顶点划分成两个顶点集合S和T，其中源点s∈S,汇点t∈T。记为CUT(S,T).右图中：顶点集S={1,2,3},T={4,5}构成一个割。框外是容量，框内是流量s-t图1.一个源点和一个汇点2.有向边，是从i到j的3.每一条边都有一个非负的权值4.容量cap(i,j)等于零，说明不存在边s-t切割的代价1.S,T的容量是所有容量函数的总和2.最小割是S-T切割中所有可能的S-T切割的能量最小的割跨越S-T切割的流值是所有f(i,j)-f(j,i)的值注意：源点和汇点不能属于同一个顶点集合。顶点集S={1,3,5}和T

2、={2,4}不能构成一个割如果一条弧的两个顶点分别属于顶点集S和T（一个顶点在S,另一个在T），这条弧称为割CUT(S.T)的一条割边。从S指向T的割边是正向割边。从T指向S的割边是逆向割边。割CUT（S,T）中所有正向割边的容量和，称为割CUT（S,T）的容量。不同割的容量不同。最小割，就是指所有割中权重之和最小的一个割。网络流和割的关系定理一：如果f是网络中的一个流，CUT(S,T)是任意一个割，那么f的值等于正向割边的流量与负向割边的流量之差。推论一：如果f是网络中的一个流，CUT(S,T)是一个割，那么f的值不超过割CUT(S,T)的容量。推论二：网络中的最大流不超过任何割的容量。定理

3、二：在网络中，如果f是一个流，CUT(S,T)是一个割，且f的值等于割CUT(S,T)的容量，那么f是一个最大流，CUT(S,T)是一个最小割。最大流最小割定理在任何网络中，最大流的值等于最小割的容量。结论一：最大流时，最小割cut(S,T)中，正向割边的流量=容量，逆向割边的流量为0。结论二：在最小割cut(S,T)中:1.源点s属于S2.如果i属于S，结点j满足：有弧,并且c[i,j]>f[i,j],或者有弧,并且f[i,j]>0,那么j属于S。//否则不是最小割。即，从s出发能找到的含有残留的点组成集合S，其余的点组成集合T。形象的比喻：水流管道的最大流量由最细的管子

4、容量决定。网络的最大流量由最小割决定。