最大二分匹配问题
给定一个无向图,一个匹配是边的一个子集M,使得对于所有的结点,子集M中最多有一条边与结点相连。如果子集M中的某条边与结点v相连,那么称结点v由M所匹配;否则,结点v就是没有匹配的。最大匹配是最大基数的匹配。
结点划分成L/R的二分图与它的匹配:
Ford-Fulkerson方法寻找最大二分匹配
如上图c所示,构造一个网络,将其中的流对应于匹配,源点s与汇点t不属于结点集V,从L指向R的边都是流网络的边,并赋单位容量。可证图G中的一个匹配G所对应的流网络G’中的一个流,且二分图G中的一个最大匹配M的基数对应于流网络G’中某一最大流f的值。
于是寻找最大二分匹配可以转化为寻找最大流问题,使用Ford-Fulkerson方法解决,方法具体原理可参考我的前一篇文章: 最大流最小割原理与Ford-Fulkerson方法
匈牙利算法
匈牙利算法很有意思,从上图我们可以看到被染色的边连接的点就是匹配点,其余点为非匹配点。
在二分图的匹配中,如果一条路径的首尾是非匹配点,路径中除此之外(如果有)其他的点均是匹配点,那么这条路径就是一条增广路径(Agumenting path)。
由于增广路径的首位是非匹配点,所以增广路径的第一条和最后一条路径都是非匹配边,同时它的第二条和倒数第二条边将是匹配边……以此类推。
如下图,红边为非匹配边,加粗黑边为非匹配边:
此时,我们置换匹配边与非匹配边,匹配边数将会加一,于是我们可以不断搜索增广路径来增加匹配边,找到最大二分匹配。
示例(画了下示意图但是懒得打一遍字了就直接放截图):
以上就是匈牙利算法的DFS实现。顺便说个很有意思的事情,我看一个大佬在视频里讲匈牙利,弹幕出现一条“又日的”,我没反应过来,想了一下原来是大佬念used数组时的发音,我愣了愣,好像是这么回事。