二分图专题解析

概念记忆

什么是二分图?首先二分图是一个无向图,其次该图的点集可以分割成两个非空子集,该图的每一条边都是横跨两个子集的。

什么是图的匹配?注意,这里是说图的匹配。图的匹配是一个边集,这个边集里没有任何两条边共用一个点。在图的所有匹配中, 边的个数最多的,就称为最大匹配。图的匹配是一个边集,也可以得到一个点集,如果这个点集合包含图中所有的点, 这个匹配就叫做完全匹配。

什么是增广路径? 是一条路径,路径的起始点都不在匹配内(不在匹配的点集内),并且在匹配内的边和不在匹配里的边交替 进行。

匈牙利算法(二分图最大匹配)

初始化:先找到一个匹配。

处理:寻找增广路径,变换匹配(边总数+1了哦),使用新的匹配。

终止:找不到增广路径

参考

二分图

Table of Contents