二部图与匹配

《二部图与匹配》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二部图与匹配二部图与匹配1*二部图相关的定义2*二部图的判定3*匹配相关定义4*二部图最大匹配——匈牙利算法1*二部图相关的定义二部图与匹配二部图有着许多应用，很多实际问题都可以使用二部图来解决，如资源分配，任务派遣等。这类问题的本质是在两个不相交的子集中寻找一种匹配对方案，并且在给定的条件下，希望这种配对达到最大，对条件的满足程度最好。定义：给定无向图,若能将顶点集划分成两个非空子集和,满足，,且对中的任意一条边，有,,则称为二部图，和称为的互补顶点子集，可记为。在二部图中的每个顶点与的每个顶

2、点都有且仅有一条边相连接，则称是完全二部图。记为其中,。二部图与匹配是二部图完全二部图。不是二部图(a)(b)(c)1.判断题二部图与匹配二部图的判定：1*任意一点标记为A；2*把上一步标记为A的所有相邻的点标记为B，同样把上一步标记为B的所有相邻的点标记为A，照此继续直到每点都被标记为止；3*判断原则：如果标记后的图没有任何相邻两点有相同的标记，则G是二部图，否则不是二部图。二部图与匹配例2二部图与匹配5.16定理（二部图的判定定理）一个无向图G是二部图当且仅当G中无奇数长度的回路。定理的通俗

3、阐释：二部图中的任何一条通路，其顶点序列往返于互补点集和之间，因此，图中任意一条回路都是偶数边构成。(1)(2)二部图与匹配定理证明：必要性：设是一个二部图，不妨设回路从出发，由于回路的每条边依次是从到，再从到，再从到，再从到......,最后回到，从而回路的长度为偶数。充分性：不妨设至少有一条边且连通，取任一顶点，令，其中,表示顶点到顶点的路长度，则.先证中任意两点不相邻.假设存在设分别是到和到的路径，则是一条回路，其长度为奇数,与假设矛盾.同理中任意两点不相邻.二部图与匹配匹配相关定义5.2

4、8设图是二部图，是图中一些边组成的集合，如果中的任意两条边都没有公共端点，则称为图的一个匹配（或称对集）。设是图中的顶点，如果是匹配中某一条边的端点，则称饱和顶点，并称是饱和的.否则称是非饱和的。例如，在图中，边集是匹配，顶点和都是饱和的，顶点和是是非饱和的。二部图与匹配若中的每个结点都是饱和点，则称是完美匹配。显然，每个完美匹配是最大匹配，但反之不真。定义5.92：设为一个二部图，为中的一个最大匹配，若，称为中的一个完备匹配，且若，称为到的一个完备匹配；若,此时为的完美匹配。显然，完美匹配是完

5、备匹配，反之不真。二部图与匹配定理5.17（Hall定理）设是一个二分图，,中存在从到的完备匹配当且仅当中任意个顶点（）至少邻接中的个顶点。由Hall定理容易证明下面的定理。设是一个二分图，若存在正整数，满足（1）中每个顶点至少关联条边。（2）中每个顶点至多关联条边。则中存在从到的完备匹配。二部图与匹配最大匹配的求法：增益路径：设和是二部图的两个互补顶点集，是一个初始匹配，如果有一条简单路径起点连着中的非饱和点，而终点连着中的非饱和点，路径上边交替出现在和中，即路径的第一条边不在，第二条边在中，

6、以此类推，直到最后一条边不在中。这样的路径称为的增益路径。二部图与匹配匈牙利算法：寻找关于当前匹配的增广路径，然后沿着增广路径进行增广，将得到一个更大的匹配，重复这一个过程，直到找不到增广路径时停止。（1）**先把进行初始匹配。（2）**在中找一条可增广路径，令为上所有边的集合（3）**（4）**重复（2）和（3）直到中找不到可增广路径。二部图与匹配初始匹配二部图与匹配2.求最大匹配习题二部图与匹配匈牙利算法的具体实现Boolean型数组c[u，v]表示原图中u到v之间是否有边。Boolean型

7、数组x[k](y[k])表示当前寻找增广路径时X(Y)集合中k点是否访问过。Link[k]:如果Link[k]<>0则边（Link[k]，k）属于当前匹配。二部图与匹配proceduremainwork主过程ans:=0匹配的边数fillchar(link,sizeof(link),0)；当前匹配没有边fork:=1tondo为X中k点寻找匹配边fillchar(x,sizeof(x),false);fillchar(x,sizeof(y),false);开始XY都未访问iffind(k)the

8、ninc(ans);找到合适的边writeln(ans);fork:=1tondoiflink[k]<>0thenwriteln(link[k],'',k);输出匹配二部图与匹配functionfind(v:integer):boolean；寻找增广路径ifx[v]thenexit(false);已经访问过v点x[v]:=true;fori:=1tondo寻找没访问过的Yifc[v,i]andnoty[i]then中的点y[i]:=true;if(link[i]=0)orfind(link[i]