网络流匹配.ppt

图论小组专题之
——网络流与匹配
08年08月08日
第一节最大二部图基数匹配

如果V(G)可以分到两个集合X,Y中,(等价于图G是可二顶点着色的)如右(图一)便是一个二部图.

,并且每个部分内部没有边,但一个正方形就可以.

任意选一个顶点,所有到该点距离为偶数的点构成的集合便是G中的一部分,距离为奇数的点为另一部分
最大匹配

图G的一个匹配是一组没有公共端点的边构成的集合,如(图一)两条黑色的边构成一个大小为2的匹配,。

一个匹配M是图G的最大匹配当且仅当图G中不存在M-增广路径. M-增广路径是一条边交替出现在M和不出现在M中的路径,且两个端点没有被M中的边覆盖。如下(图二)红色的边代表匹配,灰色代表不是匹配的边。若是一个图有M-增广路径,我们用灰色的边作为匹配,就得到了一个更大的匹配
二部图基数匹配算法
二部图的表示
由于二部图的每个部分内部没有边,[i][j]=1就表示X部分的第i个顶点与Y部分的第j个顶点有一条边,那么(图三)可表示为:
算法思想
从X部分的每个顶点开始寻找一条M-增广路径,找到增广路径之后沿着该路径更新得到一个更大的匹配
算法过程图解
寻找M-增广路算法描述
寻找M-增广路算法
输入:一个匹配和一个没被匹配覆盖的顶点u
algorithm augmenting path;
begin
initialize LIST={u};
label node u ;
while LIST≠φdo
begin
delete a node i from LIST;
for each arc (i ,j ) do
if node j is not in match then augment and return;
else if arc (j ,k )∈M and k is not labeled then set pred(j ):=i add k to LIST and label k;
end
end
注记: 1。augment 是沿着找到的增广路径更新当前匹配。
2。pred是用于记录结点j的前继(predecessor),下页由于使用的DFS实现,就不必要这个参数了
算法代码实现
/*G[x][y]表示二部图
M[Y]表示匹配,记录Y中每个顶点对应的匹配,若M[3]=5表示Y中的3和X中的5匹配,最开始M全部初始化为-1
A[X]用于记录DFS时X中顶点是否已经访问*/
#define X 10
#define Y 20
int G[X][Y],M[Y],A[X];
/*u表示X部中当前访问的结点,y表示Y部分的大小*/
int path(int u,int y){
A[u]=1;
for(int v=0;v<y;v++){
if(!G[u][v])continue;
if(M[v]!=-1&&A[M[v]])continue;
if(M[v]==-1||path(v,y)){
M[v]=u;
return 1;
}
}
return 0;
}
执行一次path为O(m),共调用n次,故该算法的复杂度为O(nm)
完整的程序可参见:code\
推荐题目:POJ 1469 (POJ 2239数据量相对较小)
注记:,n表示顶点数,下同。
,有兴趣可以做,解题报告不包括括号内的题,下同。
二部图相关的一些性质
’(G)等于最小顶点覆盖数ß(G)
如(图五),ae,bf,cg构成一个最大匹配,a,f,c构成一个最小顶点覆盖.
推荐题目:POJ 1325
(G),那么ɑ(G)+ ß(G)=n
独立集是指任意两点之间没有边的顶点的集合
如(图五),b,d,e,g,h构成一个最大的独立集
推荐题目:POJ 1466

ß’(G),那么ɑ’(G)+ ß’(G)=n.
如(图五),ae,bf,cg,fd,ch构成一个最小的边覆盖
推荐题目:无
本小节结束补充作业:POJ 2446
第二节最大流
要解决的问题
最大流问题就是像(图六)所示的,有一个源点s,一个汇点t,源点可发出和汇点可接受的容量