最小割问题PPT课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,.,*,最小割问题,060320072,高波,1,.,2,.,3,.,算法分析,在这个问题的解决中，关键是利用了网络的最大流等于最小割的权这一性质。下面是相关的证明和分析：,设f是一个最大流，流量为F，定义顶点集V的子集S如下：,源点s属于S；,若i点属于S，且边(i,j)是非饱和边，则j点属于S；,若j点属于S，且边(i,j)是非零流边，则i点属于S。,令T=V-S，只要证明cut(S,T)是最小割。,4,.,算法分析,首先证明汇点t不属于S，如若不然，则存在一条连接S中的点的从源点到汇点的通路，由S的定义，这条路是可增广路,这与f是最大流矛盾。因此存在割集cut(S,T)，由S的定义,对于割集cut(S,T)中的,边,显然有,f(i,j)=a(i,j),(iS，jT),0,(jS,iT),5,.,算法分析,所以，割集cut(S,T)的权值a(S,T)等于流量F。而且，显然有：网络的任一割集的权值不小于最大流。可知cut(S,T)是最小割。,基于以上分析，只要再确定网络的源和汇，就可以很容易的解出此题。取各顶点中流出的权值最大的顶点为源s,取各顶点中流入的权值最大的顶点为汇t即可。,6,.,结束,谢谢,7,.,