1. 首页
  2. 模板

二分图匹配 匈牙利算法与HK算法

二分图匹配

1.一个二分图中的最大匹配数等于这个图中的最小点覆盖数

König 定理是一个二分图中很重要的定理,它的意思是,一个二分图中的最大匹配数等于这个图中的最小 点覆盖数。如果你还不知道什么是最小点覆盖,我也在这里说一下:假如选了一个点就相当于覆盖了以它 为端点的所有边,你需要选择最少的点来覆盖所有的边。

2.最小路径覆盖=|G|-最大匹配数  

在一个 N*N 的有向图中,路径覆盖就是在图中找一些路经,使之覆盖了图中的所有顶点,且任何一个顶点 有且只有一条路径与之关联;(如果把这些路径中的每条路径从它的起始点走到它的终点,那么恰好可以经 过图中的每个顶点一次且仅一次);如果不考虑图中存在回路,那么每每条路径就是一个弱连通子集. 由上面可以得出:

1.一个单独的顶点是一条路径;

2.如果存在一路径 p1,p2,……pk,其中 p1 为起点,pk 为终点,那么在覆盖图中,顶点 p1,p2,……pk 不再 与其它的

顶点之间存在有向边.

最小路径覆盖就是找出最小的路径条数,使之成为 G 的一个路径覆盖.  路径覆盖与二分图匹配的关系:最小路径覆盖=|G|-最大匹配数;

3.二分图最大独立集=顶点数-二分图最大匹配

独立集:图中任意两个顶点都不相连的顶点集合。

匈牙利算法

二分图最大匹配的经典匈牙利算法是由Edmonds在1965年提出的,算法的核心就是根据一个初始匹配不停的找增广路,直到没有增广路为止。

匈牙利算法的本质实际上和基于增广路特性的最大流算法还是相似的,只需要注意两点:

(一)每个X节点都最多做一次增广路的起点;

(二)如果一个Y节点已经匹配了,那么增广路到这儿的时候唯一的路径是走到Y节点的匹配点(可以回忆最大流算法中的后向边,这个时候后向边是可以增流的)。

找增广路的时候既可以采用dfs也可以采用bfs,两者都可以保证O(nm)的复杂度,因为每找一条增广路的复杂度是O(m),而最多增广n次,dfs在实际实现中更加简短。

匈牙利算法的时间复杂度为O(VE),其中V为二分图左边的顶点数,E为二分图中边的数目。

现在我们来看看增广路有哪些性质:

(1)有奇数条边。

(2)起点在二分图的左半边,终点在右半边。

(3)路径上的点一定是一个在左半边,一个在右半边,交替出现。

(4)整条路径上没有重复的点。

(5)起点和终点都是目前还没有配对的点,而其它所有点都是已经配好对的。

(6)路径上的所有第奇数条边都不在原匹配中,所有第偶数条边都出现在原匹配中。

(7)最后,也是最重要的一条,把增广路径上的所有第奇数条边加入到原匹配中去,并把增广路径中的所有第偶数条边从原

匹配中删除(这个操作称为增广路径的取反),则新的匹配数就比原匹配数增加了1个。

当然,匹配开始时我们任意选择一边的所有点为起始点找增广路径,由增广路的性质可以看出,每找到一条增广路径,匹配数增加1。

很多问题都可以转化为二分图匹配模型。二分图有如下几种常见变形:

(1)二分图的最小顶点覆盖 

最小顶点覆盖要求用最少的点(X或Y中都行),让每条边都至少和其中一个点关联。

Knoig定理:二分图的最小顶点覆盖数等于二分图的最大匹配数。

(2)DAG图的最小路径覆盖 

用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点,这就是DAG图的最小路径覆盖问题。

结论:DAG图的最小路径覆盖数 = 节点数(n)- 最大匹配数(m)

(3)二分图的最大独立集

最大独立集问题: 在N个点的图G中选出m个点,使这m个点两两之间没有边.求m最大值

结论:二分图的最大独立集数 = 节点数(n)— 最大匹配数(m)

匈牙利算法模板

邻接矩阵:

邻接表:

Hopcroft-Karp算法

该算法由John.E.Hopcroft和Richard M.Karp于1973提出,故称Hopcroft-Karp算法。

原理

为了降低时间复杂度,可以在增广匹配集合M时,每次寻找多条增广路径。这样就可以进一步降低时间复杂度,可以证明,算法的时间复杂度可以到达O(sqrt(n)*e),虽然优化不了多少,但在实际应用时,效果还是很明显的。

基本算法

该算法主要是对匈牙利算法的优化,在寻找增广路径的时候同时寻找多条不相交的增广路径,形成极大增广路径集,然后对极大增广路径集进行增广。在寻找增广路径集的每个阶段,找到的增广路径集都具有相同的长度,且随着算法的进行,增广路径的长度不断的扩大。可以证明,最多增广n^0.5次就可以得到最大匹配。

算法流程

(1)从G=(X,Y;E)中取一个初始匹配。

(2)若X中的所有顶点都被M匹配,则表明M为一个完美匹配,返回;否则,以所有未匹配顶点为源点进行一次BFS,标记各个点到源点的距离。

(3)在满足dis[v] = dis[u] + 1的边集<v,u>中,从X中找到一个未被M匹配的顶点x0,记S = {x0},T = ¢。

(4)若N(S) = T,则表明当前已经无法得到更大匹配,返回;否则取一y0∈N(S) – 。

(5)若y0已经被M匹配则转步骤(6),否则做一条x0->y0的M-增广路径P(x0,y0),取M = M△P(x0,y0)。

(6)由于y已经被M匹配,所以M中存在一条边(y0,z0)去S = S∪ {z0},T = T∪{y0},转步骤(2)。

算法具体时间与分析

在寻找增广路径中可以对X中的每个未匹配的顶点进行BFS,BFS时对每个顶点维护一个距离编号dx[nx],dy[ny],如果某个Y中的节点为未匹配点,则找到一条增广路径。BFS结束后找到了增广路径集。然后利用DFS与匈牙利算法类似的方法对每条增广路进行增广,这样就可以找到最大匹配。

实现起来也并不复杂,对于两边各50000个点,200000条边的二分图最大匹配可以在1s内出解~~

 

评分 0, 满分 5 星
0
1
看完收藏一下,下次也能找得到
  • 版权声明:本文基于《知识共享署名-相同方式共享 3.0 中国大陆许可协议》发布,转载请遵循本协议
  • 文章链接:http://www.carlstedt.cn/archives/939 (转载时请注明本文出处及文章链接)
上一篇:
:下一篇

发表评论

gravatar

快来吐槽一下吧!

  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40