二分图匹配与网络流问题ppt课件.ppt

《二分图匹配与网络流问题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二分图匹配与网络流问题长沙市第一中学曹利国主要内容二分图的定义二分图的判定(BFS)网络流二分图的最大匹配二分图的若干定义二分图无向图中，把所有顶点划分到两个点集中，并使得每条边都是连接这两个点集的边匹配由图中不相邻的边组成的集合最大匹配图中匹配数最多的匹配完全匹配匹配边的端点为所有图中顶点二分图的判定判定一个无向图能否构成二分图算法：BFS，复杂度O(M)我们从任一点开始，令其在二分图左边，然后开始BFS，每次搜到的点放对面即可，直至所有点放完或出现矛盾正确性：对于每个连通量而言，一个点如果确定，其他点均确定，而这个点放左，放右实际上是对称的方案例题1NOIP2010，第三题关押

2、罪犯将N个人分成两组，其中M对人有Ci的不和谐值，如果有不和谐值为Ci的两人在同一组，那么就会有Ci的不和谐值。要求找出一个分组方案，使得最大不和谐值最小。N<=20000M<=100000例题解答直接做不好下手由于要求最大值最小，即一个上界，所以我们可以二分这个上界那么我们就能确定哪些人不能在一组(不和谐值大于上界的)我们新建一张图，把不能在一组的人之间连边，此时我们只需判断这个图能否构成二分图即可。复杂度O(MlogM)，实现简单例题2HNOI2010Planar给定一个图，此图有一个包含所有顶点的环（可以认为1-2-3-..-N-1）判断此图是否为平面图平面图若能将无向图G画

3、在平面上，使得任意两条边不相交（可以在端点重合），则为平面图T组数据T<=100N<=200M<=10000例题解答平面图的判定不好做考虑问题特殊性1，每条边其实有两种画法，在里面或在外面2，每条边在里面或外面可能会与其他边在里面或外面矛盾（如蓝色与绿色矛盾）例题解答我们把每条边在里面，在外面这两种选择看成两个点，那么一共有2M个点用O(M^2)的时间判断每两个点是否矛盾如果矛盾就连条边(保证自己选了，则矛盾的都不选，或自己不选，矛盾的必选)我们把每条边在里面与在外面连条边(保证两个选择只选一个)那么如果这个图能构成二分图，则原问题能够成平面图例题解答但是O(M^2)的判断太慢考虑到

4、平面图的性质：边数与点数同阶（在本题中可以3*N-6条边作为上限，如果超过则直接判非平面图）所以复杂度为O(N^2*T)网络流现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？4248473621STV1V2V3V4公路运输图基本概念这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。若有向图G=(V,E)满足下列条件：有且仅有一个顶点S，它的入度为零，这个顶点S便称为源点。有且仅有一个顶点T，它的出度为零这个顶点T便称为汇点。每一条弧都有非

5、负数，叫做该边的容量。边(vi,vj)的容量用cij表示。则称之为网络流图，记为G=(V,E,C)可行流对于网络流图G，每一条弧(i,j)都给定一个非负数fij，这一组数满足下列三条件时称为这网络的可行流，用f表示它。1.流量限制每一条弧(i,j)有fij≤Cij2.流量平衡除源点S和汇点T以外的所有的点vi，恒有：∑j(fij)=∑k(fjk)该等式说明中间点vi的流量守恒，输入与输出量相等。3.对于源点S和汇点T有，∑i(fSi)=∑j(fjT)=V(f)该等式说明源点流出量等于汇点流入量等于网络流流量残量网络与增广轨残量网络G’=(V,E,C),其中V,E与原网络G相同，C为G

6、中的容量-当前流量（即剩余可流量）增广轨就是一条S-T的不包含可流量为0的边的路径许多最大流算法都是通过不断找增广轨进行增广从而得到最大流定理：当前流为最大流当且仅当无增广轨一个重要的问题增广一次，增加1的流量后无增广轨了，而最大流却不是1.我们可以走1-2-4和1-3-4得到2的流量反向弧刚才产生的问题在于没有“后悔”的机会怎么解决？回溯搜索？复杂度上升至指数级。我们给每条边增加一条反向弧即对于(i,j,c)我们增加边(j,i,0)当(i,j,c)被增广了X的流量后，我们把反向弧的可流量增加X割切将所有点划分为两个点集。其中S和T在不同点集割的容量为两点集之间的边的容量和右图割容量

7、：8+4+4+1=17最大流流量=最小割容量引理:对于任一可行流F和任一割K，均有当所有割边满流时等号设F*为最大流，P*为最小割我们找到一个割集P由引理得对于之间的边必然满流且由割与最小割的关系所以最大流算法直接找增广轨类似搜索，效率低采用分层思想Dinic算法BFS建立层次图根据层次图用DFS找增广轨增广，返回第一步1，建立层次图对网络进行一次BFS每条边要求要有可流量才能走S标号1A->B，B的标号为A的标号+1复杂度O(M)2，Dfs找增广轨Dfs