用匈牙利算法求二分图的最大匹配.doc

《用匈牙利算法求二分图的最大匹配.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、用匈牙利算法求二分图（二部图，偶图）的最大匹配算法中的几个术语说明：  1。二部图：    如果图G=(V,E)的顶点集何V可分为两个集合X,Y，且满足X∪Y=V,X∩Y=Φ，则G称为二部图；    图G的边集用E(G)表示，点集用V(G)表示。  2。匹配：    设M是E(G)的一个子集，如果M中任意两条边在G中均不邻接，则称M是G的一个匹配。M中的—条边的两个端点叫做在M是配对的。    3。饱和与非饱和：     若匹配M的某条边与顶点v关联，则称M饱和顶点v，并且称v是M-饱和的，否则称v是M-不饱和的。  4。交互道：     若M是二分图G＝(V,E)

2、的一个匹配。设从图G中的一个顶点到另一个顶点存在一条道路，这条道路是由属于M的边和不属于M的边交替出现组成的，则称这条道路为交互道。  5。可增广路：     若一交互道的两端点为关于M非饱和顶点时，则称这条交互路是可增广路。显然，一条边的两端点非饱和，则这条边也是可增广路。  6。最大匹配：     如果M是一匹配，而不存在其它匹配M'，使得

3、M'

4、>

5、M

6、，则称M是最大匹配。其中

7、M

8、表示匹配M的边数。  7。对称差：     A，B是两个集合，定义A⊕B=(A∪B)(A∩B)，则称A⊕B为A和B的对称差。      定理：M为G的最大匹配的充要条件是G中不存在可

9、增广道路。       Hall定理：对于二部图G，存在一个匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X的任意一个子集A，和A邻接的点集为T(A)，恒有：

10、T(A)

11、>=

12、A

13、。 匈牙利算法是基于Hall定理中充分性证明的思想，其基本步骤为：  1。任给初始匹配M；  2。若X已饱和则结束，否则进行第3步；  3。在X中找到一个非饱和顶点x0，作V1←{x0}，V2←Φ； 4。若T(V1)=V2则因为无法匹配而停止，否则任选一点y∈T(V1)V2； 5。若y已饱和则转6，否则做一条从x0→y的可增广路P，M←M⊕E(P)，转2；  6。由于y已饱和，所以M中

14、有一条边(y,z)，作V1←V1∪{z}, V2←V2∪{y}，转4； 二、用匈牙利算法求二分图的最大匹配（伪代码）给定一个二分图(x,y)，x中的点和y中点的连接情况，一个匹配是二分图的子图，其中任一个x中的点只能和最多一个y中的点连接，一个y中的点也只能和一个x中的点连接，最大匹配就是使子图中的边数（我们称为匹配边）最多的匹配。mat[i,j]记录x中的i和y中j是否可匹配，cov[i]记录y中的已盖点i连着x中的那个点，如果i是未盖点，则cov[i]=0，另外在寻找可增广轨时不能有重复，所以用use[i]记录x中的i是否被访问过。从x中一未盖点出发，通过交错轨（匹

15、配边和非匹配边交错）找到y中的一个未盖点，然后把这条交错轨上的匹配边和非匹配边交换，则匹配边比原先多了一条，重复以上步骤直到找不到交错轨为止。伪代码如下：functioncan(s:byte):boolean;beginifuse[s]thenexit(false);use[s]:=true;for所有y中的点idoifmat[s,i]thenifi是未盖点thenbegincov[i]:=s;//i点变成已盖点，交换匹配边和非匹配边exit(true);endelseifcan(cov[i])thenbegincov[i]:=s;//交换匹配边和非匹配边exit(tr

16、ue);end;exit(false);end;proceduremain;beginforx中的点i//i肯定是未盖点ifcan(i)theninc(sum)//sum是匹配数end;