二分匹配定义

 

n如果一个图的顶点可以分为两个集合X和Y，图的所有边一定是有一个顶点属于集合X，另一个顶点属于集合Y，则称该图为“二分图”（ Bipartite Graph ）

给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。(设M是E(G)的一个子集，如果M中任意两条边在G中均不邻接，则称M是G的一个匹配。M中的—条边的两个端点叫做在M是配对的。)

极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。

在二分图的应用中，最常见的就是最大匹配问题，很多其他的问题都可以通过转化为匹配问题来解决。

求二分图最大匹配可以用最大流(Maximal Flow)或者匈牙利算法(Hungarian Algorithm)

 

匈牙利算法(Hungarian Algorithm)

饱和与非饱和： 
若匹配M的某条边与顶点v关联，则称M饱和顶点v，并且称v是M-饱和的，否则称v是M-不饱和的。

交互道： 
若M是二分图G＝(V,E)的一个匹配。设从图G中的一个顶点到另一个顶点存在一条道路，这条道路是由属于M的边和不属于M的边交替出现组成的，则称这条道路为交互道。 

可增广道路： 
 若一交互道的两端点为关于M非饱和顶点时，则称这条交互道是可增广道路。显然，一条边的两端点非饱和，则这条边也是可增广道路。 

最大匹配： 
  如果M是一匹配，而不存在其它匹配M'，使得|M'|>|M|，则称M是最大匹配。其中|M|表示匹配M的边数。 

对称差： 
 A，B是两个集合，定义 A⊕B = (A∪B)\(A∩B) ,  则A⊕B称为A和B的对称差。

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

 

匈牙利算法是基于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中有一条边(y,z)，作 V1 ← V1 ∪{z}, V2 ← V2 ∪ {y}， 转4；

 

匈牙利算法：
说穿了，就是你从二分图中找出一条路径来，让路径的起点和终点都是还没有匹配过的点，并且路径经过的连线是一条没被匹配、一条已经匹配过，再下一条又没匹配这样交替地出现。找到这样的路径后，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个。不断执行上述操作，直到找不到这样的路径为止。