二分图匹配

给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。(源于百度百科)

通俗来讲,有一堆人(图中的点),每个人都有一定的人际关系(图中的边),你需要使他们和他们的朋友两两组队,每个人只能在一个队伍。这就是二分图匹配。

极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。

最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。

一般问题都是求解二分图最大匹配问题。求解最大匹配最常用的算法为匈牙利算法。

匈牙利算法

匈牙利算法

这是网上最好的一篇关于匈牙利算法的文章,我不能写的比他更好了。

匈牙利算法代码量并不多,记忆起来也不复杂,在做题时遇到最主要的问题就是建图。如何将问题转化成简单的二分图匹配问题,是最需要解决的。

建图

接下来直接看一个比较复杂的二分图问题:

poj3020

这个题大致意思就是一个天线可以覆盖本身以及相邻四个方向其中一个,问最少需要多少个天线才能覆盖所有点。

建图思路(懒得码字了→_→)。

感谢您的支持
-------------本文结束感谢您的阅读-------------