网络流匹配.

图论小组专题之——网络流与匹配08年08月08日第一节最大二部图基数匹配1．何为二部图如果V(G)可以分到两个集合X，Y中，且X和Y内部没有G的边．那么图G就是一个二部图（等价于图G是可二顶点着色的）如右（图一）便是一个二部图．２．二部图的性质一个图是二部图当且仅当图G中没有奇环．比如说一个三角形就不可能分成两个部分，并且每个部分内部没有边，但一个正方形就可以．３．如何得到二部图的每个部分任意选一个顶点，所有到该点距离为偶数的点构成的集合便是G中的一部分，距离为奇数的点为另一部分XY(图一)最大匹配１．何为匹配图G的一个匹配是一组没有公共端点的边构成的集合，如（图一）两条黑色的边构成一个大小为２的匹配，三条红色的边构成一个大小为３的匹配．图中的最大匹配数就是３。２．判断一个匹配是不是最大匹配一个匹配M是图G的最大匹配当且仅当图G中不存在M-增广路径.M-增广路径是一条边交替出现在M和不出现在M中的路径，且两个端点没有被M中的边覆盖。如下（图二）红色的边代表匹配，灰色代表不是匹配的边。若是一个图有M-增广路径，我们用灰色的边作为匹配，就得到了一个更大的匹配(图二)是M-增广路径也是M-增广路径不是M-增广路径二部图基数匹配算法二部图的表示由于二部图的每个部分内部没有边，这允许我们用更少的空间来存储二部图的结构.若G[i][j]=1就表示X部分的第i个顶点与Y部分的第j个顶点有一条边，那么（图三）可表示为：001122XY(图三)101[3][3]110001G算法思想从X部分的每个顶点开始寻找一条M-增广路径，找到增广路径之后沿着该路径更新得到一个更大的匹配算法过程图解001122XY(图四)001122XY001122XY001122XY001122XY001122XY从X的顶点0开始,搜索到Y中顶点0,获得条M-增广路径由此M-增广路径更新得到0-0匹配从X中1开始搜索到Y中0,没得到M-增广路径继续沿着Y中0对应的匹配X中的0搜索,搜索到Y中的2,得到一条M-增广路径:X1-Y0-X0-Y2更新匹配得到大小为2的匹配从X2搜索最终得到一条M-增广路径,后面的更新就不画出来了,最终匹配大小就是3寻找M-增广路算法描述寻找M-增广路算法输入：一个匹配和一个没被匹配覆盖的顶点ualgorithmaugmentingpath;begininitializeLIST={u};labelnodeu;whileLIST≠φdobegindeleteanodeifromLIST;foreacharc(i,j)doifnodejisnotinmatchthenaugmentandreturn;elseifarc(j,k)∈Mandkisnotlabeledthensetpred(j):=iaddktoLISTandlabelk;endend注记:1。augment是沿着找到的增广路径更新当前匹配。2。pred是用于记录结点j的前继(predecessor)，下页由于使用的DFS实现，就不必要这个参数了算法代码实现/*G[x][y]表示二部图M[Y]表示匹配，记录Y中每个顶点对应的匹配，若M[3]=5表示Y中的３和X中的5匹配,最开始M全部初始化为-1A[X]用于记录DFS时X中顶点是否已经访问*/#defineX10#defineY20intG[X][Y],M[Y],A[X];/*u表示X部中当前访问的结点,y表示Y部分的大小*/intpath(intu,inty){A[u]=1;for(intv=0;vy;v++){if(!G[u][v])continue;if(M[v]!=-1&&A[M[v]])continue;if(M[v]==-1||path(v,y)){M[v]=u;return1;}}return0;}执行一次path为O(m),共调用n次，故该算法的复杂度为O(nm)完整的程序可参见:code\match.cpp推荐题目:POJ1469(POJ2239数据量相对较小)注记:１．m表示图的边数，n表示顶点数，下同。２．推荐题目括号内的题目表示是同一类题目，有兴趣可以做，解题报告不包括括号内的题，下同。二部图相关的一些性质１．二部图的最大匹配数ɑ’(G)等于最小顶点覆盖数ß(G)如(图五),ae,bf,cg构成一个最大匹配,a,f,c构成一个最小顶点覆盖.推荐题目:POJ1325febacdgh(图五)2.任意图的最大独立集记为ɑ(G),那么ɑ(G)+ß(G)=n独立集是指任意两点之间没有边的顶点的集合如（图五），b,d,e,g,h构成一个最大的独立集推荐题目:POJ14663.任意无孤立顶点的图的边覆盖大小的最小值记为ß’(G),那么ɑ’(G)+ß’(G)=n.如（图五），ae,bf,cg,fd,ch构成一个最小的边覆盖推荐题目:无本小节结束补充作业:POJ2446第二节最大流要解决的问题最大流问题就是像（图六）所示的，有一个源点s，一个汇点t，源点可发出和汇点可接受的容量都为无穷大，然后那些有向边的值代表最大能通过该边的容量。然后要求从源点s最大能到达到汇点t的容量如何解决每次从源点s找条能增大现有流量的路径，直到流量不能再增加为止st3533343212(图六)图解寻增广路径stab33311原始图stab00000第一步:流量初始化为0stab33300第二步:找到一条路径,可以流过3的流量stab33300好象从s只能到达b然后就不能流了,然后最大流是3,是吗??stab33300其实还可以从b再到a,代表取消原先从a流向b的部分流量stab32311这样就又找到了一条流量为1的路径.注意从a到b是减1.现在总流量就是4了(图七)算法描述最大流增广路径算法（x表示当前容量，u表示最大容量）algorithmaugmentingpath;beginlabelnodesandsetLIST:={s};whileLIST≠φandtisunlabeleddobeginremoveanodeifromLIST;foreacharc(i,j)andarc(j,i)ifxijuijorxji0thenifnodejisunlabeledthensetpred(j):=i,labelnodej,andaddjtoLIST;endiftislabeldthenaugment;end注记：augment先要遍历该路径得到的增广路径求出最大能通过的流量，然后对于正向通过的边的加上该流量，负向通过该路径的边就减去该流量算法代码实现/*G表示图的容量上限，X表示当前流量，初始化为0，A用于记录结点是否已经访问*/intG[N][N],X[N][N],A[N];/*u表示当前搜索的结点，t表示汇点，n表示图的阶，p表示流到当前结点的流量*/intpath(intu,intt,intn,intp){A[u]=1;if(u==t)returnp;for(intv=0;vn;v++){if(!A[v]&&G[u][v]-X[u][v]){intpt=path(v,n,min(p,G[u][v]-X[u][v]));if(pt){X[u][v]+=pt;returnpt;}}if(!A[v]&&X[v][u]){intpt=path(v,n,min(p,X[v][u]))if(pt){X[v][u]-=pt;returnpt;}}}return0;}运行复杂度:path运行时间为O(m)，而且每运行一次流量至少加一,若总流量为U,那么该算法时间复杂度为O(mU)因此该算法适用于流量较小的网络。算法代码可参考:code\flow_1.cpp推荐题目：POJ1273,POJ1087最小割最大流定理1.若去掉图的一些边，能把图的顶点分为两部分，那么去掉的边为该图的一个割，若s和t在不同的部分，则称这个割为s-t割。一个s-t割的大小是所有从s部分到t部分的边的容量之和。那么有这个定理:从s到t的最大流量等于最小的s-t割。首先，很显然任意割≥最大流，因为去掉那些边后流量为0，加上那些边后流量不会超过那些边的总容量。然后对于前面描述的算法，当找不到增广路径时就确定了一个s-t割，故存在一个割使它等于最大流，那么这个割就是最小割，且这个流是最大流。2.运用该定理建立用最大流解决匹配问题的模型如（图一）的匹配建立成（图八）的最大流模型，原来的最大匹配数就等于现在的最大流分析，由于最大流等于最小割，最小割肯定不包含原来匹配的边，因为他们流量为无穷大。故最小割只可能是从s出发和到达t的边，且这个割覆盖的顶点必定是原二部图的一个顶点覆盖，故最小割就等于原二部图最小顶点覆盖，再由二部图最小顶点覆盖等于最大匹配可知下面的最大流模型是正确的st∞∞∞∞∞111111(图八)货船运输问题一个货运公司签定合约给顾客运输物品，每个顾客要求在特定的时间在不同的港口间运输。给出货船在各个港口间满载和空载的运输时间，求货运公司可用的最少的货船能满足所有顾客。如右列出了各顾客需要运输的时间表以及船在空载和满载时在各港口间的行驶天数。现用4个顶点表示4个任务（图九（a）），由于完成第1个任务后该货船还可去完成第3个任务或第4个任务，连接13和14。完成第2个任务后还可以去完成第4个任务，连接24。这样就得到一个有向无回图。将每个顶点分为两个(图九(b))，s到1，2，3，4分别表示可以各派一只船给这个任务，1’,2’,3’,4’到t表示完成该任务的船可以选择立即返回，1’到3，1’到4，2’到4表示这些船完成当前的任务后可以选择继续去完成下一个任务。1到1‘的流量限制为等于1，表示任务1能且只能被完成一次。2和2’等同理。那么s到t的最小流量就是派出去的最少船只。由于这个最小流很容易确定一个总流量为n（任务数）的可行流，然后运用求最大流的算法找使流量减小的增广路，最终就能得到最小流量。仔细观察发现减少的流正是一个匹配的最大流模型，因此也可以用匹配来解决此题。推荐题目:POJ2060(POJ2594,POJ1422)时间表出发点目的地第1天港口A港口B第3天港口C港口D第6天港口C港口B第7天港口D港口A满ABCDA0322B3034C2303D2430空ABCDA0211B2023C1202D1320s=1123411'22'33'44'1t1111111=1=1=1111(图九)(a)(b)最短增广路算法若每次都选最短的路径作为增广路，最多有nm条增广路径，也就是说若用BFS寻增广路就可以取得O(nm2)的一个上界。但这个上界太差，将介绍的算法能在O(n)的时间内获得一条最短增广路径，从而得到一个O(n2m)的算法。该算法要先给每个顶点标号，记录每个顶点到达汇点t的距离。然后选择下一顶点的时候只能选标号比自己标号小1的顶点，选的这条边称为可行边，若到达汇点的路径的每条边都是可行边，那么就是一条最短路径。当某个顶点没有可行边时，就增大该顶点的标号直到恰好出现可行边。算法直到s的标号达到了n时结束，因为没有路径长度有n，也就是说这时已经没有增广路径能够到t了。0(图十)(1,0)13245SourceSink(3,0)(3,0)(3,0)(3,0)(3,0)(1,0)0112230(1,1)13245SourceSink(3,0)(3,0)(3,0)(3,1)(3,1)(1,0)0112231.初始化:设定初始的可行流为0用BFS给每个顶点标出距离标号2.沿着一条可行路径0-1-3-5增广了1的流量算法图解0(1,1)13245Source(3,1)(3,1)(3,0)(3,1)(3,1)(1,1)0112230(1,1)13245Source(3,1)(3,1)(3,0)(3,1)(3,1)(1,1)0132453.沿着另一条可行路径0-2-4-5增广了1的流量4.沿着0-2-4发现没有可行路径,然后4的标号改为它能到的2的标号+1,依次更改2和4的标号0(1,1)13245Source(3,3)(3,3)(3,2)