最大闭合权图[精选].ppt

最大闭合权图 一些符号和定义 最大权闭合图：在一个图中，我们选取一些点构成集合，记为V，且集合中的出边(即集合中的点的向外连出的弧)，所指向的终点(弧头)也在V中，则我们称V为闭合图。最大权闭合图即在所有闭合图中，集合中点的权值之和最大的V，我们称V为最大权闭合图。 割：使得从源点到汇点的路集为空集时，一些弧的集合 简单割：割集的每条边都与S或T关联。 最小割：图中所有的割中，边权值和最小的割。 解决方法 建图:构造一个源点S，汇点T。我们将S与所有权值为正的点连一条容量为其权值的边，将所有权值为负的点与T连一条容量为其权值的绝对值的边，原来的边将其容量定为正无穷。 把最大闭合权图变成了最小割 再把最小割转换成了最大流 相关证明 1.最小割为简单割 2.闭合图是简单割 3.简单割是闭合图 4.证明最小割所产生的两个集合中，其源点S所在集合(除去S)为最大权闭合图。 //到此为止，最大闭合权图即是最小割 5.最小割是最大流(最小割最大流定理) //到此为止，最大闭合权图即是最大流 最小割为简单割 因为除S和T之外的点间的边的容量是正无穷，最小割的容量不可能为正无穷。所以，得证。 闭合图是简单割 利用反证法 如果闭合图不是简单割。那么说明有一条边是容量为正无穷的边，则说明闭合图中有一条出边的终点不在闭合图中，矛盾。 所以，得证。 简单割为闭合图 因为简单割不含正无穷的边，所以不含有连向另一个集合（除T）的点，所以其出边的终点都在简单割中，满足闭合图定义。所以，得证。 证明最小割所产生的两个割集中，其源点s所在集合（除去S）为最大闭合权图（说实话，这里我也没太明白） 首先我们记一个简单割的容量为C,且S所在集合为N，T所在集合为M。 则C=M中所有权值为正的点的权值(即S与M中点相连的边的容量)+N中所有权值为负的点权值的绝对值(即N中点与T中点相连边的容量)。记(C=x1+y1);(很好理解，不理解画一个图或想象一下就明白了)。 我们记N这个闭合图的权值和为W。 则W=N中权值为正的点的权值-N中权值为负的点的权值的绝对值。记(W=x2-y2); 则W+C=x1+y1+x2-y2。 因为明显y1=y2，所以W+C=x1+x2; x1为M中所有权值为正的点的权值，x2为N中权值为正的点的权值。 所以x1+x2=所有权值为正的点的权值之和(记为TOT). 所以我们得到W+C=TOT.整理一下W=TOT-C. 到这里我们就得到了闭合图的权值与简单割的容量的关系。 ?因为TOT为定值，所以我们欲使W最大，即C最小，即此时这个简单割为最小割，此时闭合图为其源点S所在集合(除去S)。得证。 到此为止，最大闭合权图即是最小割 证明最小割就是最大流（最小割最大流定理） 从s运送到t的物品必然通过跨越S和T的边，所以从S到T的净流量等于|f|=f（S,T）= =c(S,T) 这里的割（S,T）是任意取得，所以得到了一个重要的结论：对于任意s-t流f和任意s-t割（S,T），有|f| c（S,T）。 下面来看残量网络中没有增广路的情形。 既然不存在增广路，在残量网络中s和t并不连通。当BFS没有找到任何s-t道路时，把以标号的节点（a[u]0的结点u）集合看成S，另T=V-S，则残量网络中的S和T分离，因此在原图中跨越S和T所有弧均满载（这样的边才不会存在于残量网络中），且没有从T回到S的流量，因此|f| c（S,T）成立。 证明最小割就是最大流（最小割最大流定理） 前面说过，对于任意的f和（S,T），都有|f|= c（S,T）。而我们又找到了一组让等号成立的f和（S,T），这样，我们同时证明了增广路定理和最小割最大流定理：在增广路算法结束时，f是s-t的最大流，（S,T）是s-t的最小割。