最小割的一些思考研究.ppt

网络流的一些思考 基本概念 二分图 网络流：肯定是有向的带流量(容量)的图 最大流 最小割： 二分图 二分图的概念 二分图的判断 二分图的匹配（匈牙利算法）（最大流） 二分图的应用 二分图绝大多数可以用网络流来写，不过有例外。 noi2009那道题 网络流 流量很重要 dfs的回溯很厉害 最小费用最大流 spfa来判断是否有增广路。 两个ppt 最小割 胡伯涛的论文 以下内容只是对论文的理解。 最小割的概念 1.到底什么是割：原始点集为V，选出一些点集S使得s∈S，T=V-S，t∈T，则S到T的边为S到T割，记做[S,T]。 2.什么是最小割：图中所有的割中，边权值和最小的割为最小割！ 3.割的容量容量和流量计算的区别：割[S,T]的容量为∑(边(u,v)的容量和)，其中u∈S,∈T。也就是说割的容量不计算反向的边！！而流量为正向的和反向的代数和。 4.最大流-最小割定理：最大流的值为最小割的容量！（反证法） 例题：巡逻。 怎样求割 求完最大流后，在残留网络中从source开始dfs，被染色的为S，未被染色的为T，则边集[S,T]为割。 /f?kz=793195439 雷了！ 固定模型的最小割问题构图方法及举例 常见类型 网络流关键割边 最大权闭合图 无向图点连通度(无向图最小点割集) 二分图的最小点权覆盖集算法 二分图的最大点权独立集算法 网络流关键割边 定义：关键割边就是增加某条边的容量,可以使得网络的最大流增加。 ????算法描述：首先对这个网络图跑一遍dinic（最大流），得到残余网络。再分别从s和t对残余网络进行dfs。对于一条边(a,b)如果从s可以到达a并且从t可以到达b则该边为关键割边。 注意，满流的边不一定是关键割边。具体反例见胡波涛论文第8页。 一些割的性质 1.割[S,T]，流量只能从S流向T，不能从T流向S！ （在最大流后找割dfs时其实就满足这个性质，假设T中一个点v流向S中的一个点u，那么u到v有负流量，则u到v的残留网络严格大于0。 ） 2.最大流后，割边一定满流。减小某一割边后，网络流减小。 3.如下图，从s沿着残余流量dfs，得到点集S；同理沿着t反向dfs，得到点集T；剩下的是M。分界线cut1和cut2是其中一割，边自然为割边。然而在M中还存有割边（一定存有！！否则M就没用了！） 一些割的性质 退化一下：如下图所示，S和T有相邻部分边集E1，S和M重合边集相邻部分边集E2，M和T相邻边集部分E3，那么直接升高E1中某条边的容量，会使整体容量直接增高！反之：而如果增大S和M相邻的割边或者M和T相邻的割边，网络流不直接增大，因为M中还存有割边限制 。 继续退化：如果M==空集，cut1和cut2重合（变为cut），则网络中割唯一。可以通过 if ( |S|+|T|==总点数) 来判断 例题 poj 3204 一个由n个点，m条边构成的有向图，每条边都有一定的流量。现在求存在多少条边，在增加这些边的流量后从0点到n-1的总流量会增加。 usaco4.4.2 /mengyun1993/blog/item/c30d193c9f6cda.html usaco 5.4.5 拆点 ?例题：zoj 2532?有n个城市，m个中继站，一个总站--0点。有L条有向线路连接这些点，每条线路都有各自的容量。现在所有的城市要向总站发送信号。求增加哪条边的容量可以使得总信号流量增加。 ????同上面那道题基本相同，在加边时注意增加一个标号即可。 ??? ????例题：zoj 2587?给出一个网络图和源汇点，判断这个图的最小割是否唯一。 ????之前做到的题目都是求最小割的大小是多少，这里最小割的唯一性的该如何判断呢。其实这个问题的解决思路和求网络流的关键割边很相似，都是在dinic后再分别从源汇点对这个残余网络进行dfs。如果无法访问到所有的点则说明该图的最小割并不唯一。 （我的想法是，如果一个点无法被遍历到，那么他肯定是被夹在两个(或多个)满流的边之间，导致dfs无法到达该点，那么对于这两条满流的边，把任何一个放在割中都可构成最小割，所以推出最小割不唯一） 最大权闭合图 ?定义：在一个有向图中，有边(u,v)，如果选择了u，必须选择v，这样选出的图叫做闭合图。某些点有权值，则选出的权值最大的闭合图，叫做最大权闭合图。 右图中的闭合图有空集,{5},{2,5},{4,5},{2,4,5},{3,4,5},{1,2,3,4,5},{1,2,4,5}。最大权闭合图为{3,4,5}。权值之和为4。 算法描述 算法描述：在原图的基础上增加源点s和汇点t，将原图中的每条有向边替换为容量为正无穷的有向边，s向图中的所有正权点连接有