Introduction
给定二分图G
, M
为G
边集中的一个子集. 如果M
满足当中的任意两条边都不依附于同一个顶点, 则称M
是一个G
的一个匹配。
极大匹配(Maximal Matching)是指在当前已完成的匹配下, 无法再通过增加未完成匹配的边的方式来增加匹配的边数.
最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配. 选择这样的边数最大的子集称为图的最大匹配问题.
如果一个匹配中, 图中的每个顶点都和图中某条边相关联, 则称此匹配为完全匹配, 也称作完备匹配.
完美匹配 : 如果所有点都在匹配边上, 称这个最大匹配是完美匹配.
求二分图最大匹配可以用 最大流(Maximal Flow) 或者 匈牙利算法(Hungarian Algorithm)
如果G为加权二分图, 则权值和最大的完备匹配称为最佳匹配, 求一个二分图的最佳匹配的普遍算法是KM(Kuhn-Munkres)算法.
References
-
Harold W. Kuhn. The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2:83-97, 1955.
-
Harold W. Kuhn. Variants of the Hungarian method for assignment problems. Naval Research Logistics Quarterly, 3: 253-258, 1956.
-
Munkres, J. Algorithms for the Assignment and Transportation Problems. Journal of the Society of Industrial and Applied Mathematics, 5(1):32-38, March, 1957.