二分图匹配.

Presentation on theme: "二分图匹配."— Presentation transcript:

1 二分图匹配

2 什么是二分图？ 在离散数学中，我们都学过偶图，而偶图就是二分图。
二分图：给你一个图，它的顶点可以分为两个集合，集合V1和V2，所有关联边的一个顶点在V1中，另一个顶点则在V2中。 v1 v2 v3 v1 v2 v4 v4 v5 v3 二分图 非二分图

3 什么是二分图匹配？ 二分图匹配：给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。 匹配1
匹配2 v2 v3 v1 v1 v2 v3 v4 v5 v4 v5

4 今天我要讲的是无权二分图的最大匹配问题，采用匈牙利算法。
最大匹配：图中包含边数最多的匹配称为图的最大匹配。 今天我要讲的是无权二分图的最大匹配问题，采用匈牙利算法。

5 匈牙利算法必备知识： 1.盖点：有被M中的边关联到的节点，未盖点则相反。
2.增广路径：若二分图中有一条路径p，其起始点和结束点都是未盖点，其间属于M的边和不属于M的边交替出现，则称路径p是一条关于M的增广路径。 匈牙利算法： 计算二分图最大匹配就是应用增广路径的概念，每次寻找一条关于M的增广路径p，通过M和增广路径进行异或，使得M中的匹配数增加1。以此类推，直至二分图中不存在关于M的增广路径为止。此时得到匹配M就是图G的一个最大匹配。 注：M为一个边集，M就是二分图的匹配

6 结合增广路径的定义和下图所示，我们可以理解以下结论：
1.增广路径的长度必定为奇数，第一条边和最后一条边都不属于 M。 2.将 M 和增广路径进行异或操作（去同存异）可以得到一个更大的匹配 M'。 3.M' 比 M 的匹配数多 1。 4.M 为 G 的最大匹配当且仅当不存在 M 的增广路径。 核心：判断当前结点为起点的增广路径是否存在。

7 poj1274 题目大意：有N头奶牛，M个产奶的棚子，每头奶牛都有自己想去产奶的几个棚子，问可以产生的最大匹配数。 数据：
Sample Input N M 第一头： t m2 m5 第二头： t m2 m3 m4 第三头：….. 第四头：….. 第五头：….. Sample Output 4

8 解题思路：将奶牛看成N集合，棚子看成M集合
1,对于N集合中一个未匹配的节点i,寻找它的每条关联边,如果它的边上的另一个节点j还没匹配则表明找到了一个匹配,直接转步骤4; 2,假如节点i它边上的另一个节点j已经匹配,那么就转向跟j匹配的节点，也就是它的前驱,假设是pre[j],然后再对pre[j]重复1,2的步骤,即寻找增广路径. 3,假如我们在1,2步过程中找到一条增广路, 那么修改各自对应的匹配点,转步骤4,若无增广路, 则退出. 4,匹配数+1;

9 2 3 4 5 1 2 3 4 5 1

10 2 3 4 5 1 i = 1 时： Pre[2] = 1;

11 2 3 4 5 1 i = 2 时： Pre[5] = 1; Pre[2] = 2; 1 3 2

12 2 3 4 5 1 i = 3时： Pre[1] = 3; 1

13 2 3 4 5 1 i = 4时 ： Pre[3] = 2; Pre[2] = 1; Pre[5] = 3; Pre[1] = 4;

14 二分图最大匹配延伸 最小点覆盖 最小边覆盖 最大独立集 有向图最小路径覆盖 最优匹配（KM算法）