二分匹配

匹配一、二分图的概念二分图又称作二部图是图论中的一种特殊模型。设G(V,E)是一个无向图。如顶点集 V 可分割为两个互不相交的子集并且图中每条边依附的两个顶点都分属两个不同的子集。则称图 G 为二分图。简单解析也就是设 G ( V,E) 是一个无向图如果顶点集 V 可以被划分为两个互不相交的子集 X 和 Y使得图中的每一条边都连接一个 X 中的顶点和一个 Y 中的顶点那么称图 G 为二分图。匹配的定义给定二分图 G(V,E)一个匹配M⊆E 是指满足以下条件的边集每个顶点最多只能与匹配中的一条边相关联一个顶点可以不与任何边关联称为自由顶点但不能同时与两条或更多边关联匹配是一个边集其中任意两条边都不共享顶点每个点最多匹配一条边即在匹配子图中每个顶点的度数只能是 0 或 1 。最大匹配给定一个二分图 G一个匹配 M 是 G 的边子集使得 M 中任意两条边都不依附于同一个顶点。选择这样的边数最大的子集称为图的最大匹配问题。最大匹配就是在一个子集中满足合法匹配条件且边数最多的那个匹配。完备匹配如果一个匹配中图中的每个顶点都和图中某条边相关联则称此匹配为完全匹配也称作完备匹配。也就是如果一个匹配 M 满足图中的每个顶点都恰好与一条匹配边相关联则称 M 为完备匹配。换句话来说所有顶点都被覆盖或饱和没有自由顶点没有未被匹配的顶点每个顶点的度数在匹配中恰好为 1二、匹配算法求最大匹配的一种显而易见的算法是先找出全部匹配然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此需要寻求一种更加高效的算法。增广路的定义(也称增广轨或交错轨)若 P 是图 G 中一条连通两个未匹配顶点的路径并且属 M 的边和不属 M 的边 (即已匹配和待匹配的边) 在 P 上交替出现则称 P 为相对于 M 的一条增广路径。一条路径被称为增广路径或增广路当且仅当满足以下条件‌起点和终点都是未匹配点‌即非饱和点也就是 第一条和最后一条边都‌不属于匹配 M路径上的边‌交替地属于和不属于当前匹配 M‌称为交错路径路径长度为‌奇数‌且非匹配边比匹配边多一条。求最大匹配常用匈牙利算法它的基本思想是对于已知的匹配 M从 X 中的任一选定的 M 非饱和点还未被匹配的点出发用标号法寻找 M 增广链。如果找到 M 增广链则 M 就可以得到增广否则从 X 中另一个 M 非饱和点出发继续寻找 M 增广链。重复这个过程直到 G 中不存在增广链 结束此时的匹配就是 G 的最大匹配。这个算法通常称为匈牙利算法因为这里介绍的寻找增广链的标号方法是由匈牙利学者 Egerváry 最早提出来的。也就是通过不断寻找增广路扩展匹配不断靠近最大匹配 由增广路的定义可以推出下述三个结论1. P 的路径长度必定为奇数第一条边和最后一条边都不属于 M 。2. P 经过取反操作可以得到一个更大的匹配 M’将增广路 P 上的边取反原属 M 的移除原不属 M 的加入新匹配 M′ M ⊕ P 的大小满足 | M | | M | 1。3.M 是最大匹配 ⇔ 图中不存在相对于 M 的增广路。 这是匈牙利算法的理论根基不断寻找增广路直到无法找到为止。算法轮廓(1)置 M 为空(2)找出一条增广路径 P通过取反操作获得更大的匹配 M’ 代替 M效果路径两端的未匹配点被纳入匹配匹配数 1(3)重复 (2) 操作直到找不出增广路径为止此时 M 就是最大匹配。也就是将匹配 M 初始化为 0即空集→ 不断找增广路 → 更新匹配 → 直到找不到增广路 → 此时的 M 就是最大匹配。三匹配的应用1.最小点覆盖问题定义假如选了一个点就相当于覆盖了以它为端点的所有边。最小顶点覆盖就是选择最少的点来覆盖所有的边。可以证明二分图最小点覆盖数最大匹配数。证明假设最大匹配边数为M1.M是足够的。因为如果存在边E未与顶点相连则E可以匹配此时不是最大匹配。2.M是必须的。仅考虑构成最大匹配的M条边他们两两无公共点所以需要M个顶点覆盖他们。实例说明我们用二分图来构造最小顶点覆盖。对于上面这个二分图顶点分为左右两个集合X集合包含 1,2,3,4Y集合包含 5,6,7,8,9 假如现在我们已经找到一个最大匹配 M就是上面的红线所标注的M{(1,7),(2,5),(4,8)}。我们作如下定义(1)定义 1、2、4、5、7、8 为已经匹配过的点其他点为未匹配的点(2)定义 (4,8)、(1,7)、(2,5) 为已匹配的边其他边为未匹配的边。下面我们从Y集合中找出未匹配的点就是上面标记的 6 和 9 。每次我们从右边选出一个未匹配的点从该点出发 做一条未匹配边-匹配边-未匹配边-……-匹配边注意最后以匹配边结尾并且标记用到的点得到下图其中紫色的边为我们刚才画的边其中标记的点有 2、4、5、6、8、9。 上图的两条路为19-4-8-2-526-2-5。这两条路都是未匹配边-匹配边-未匹配边-……-匹配边。注意如果一个右侧未匹配点有多条边那么这样的从该点开始的路径就有多条上面的6和9都只有一条边所以从每个点开始的这样的路径只有一条。现在我们将左侧标记的点 2、4 和右侧未标记的点 7 选出组成集合 S 那个 S 就是一个最小顶点覆盖集就是 S 集合可以覆盖所有的边。所以对于二分图来说最小点覆盖问题可以直接转化为最大匹配问题来解决——先求最大匹配数就等于知道了最少需要多少个点来覆盖所有边。2.最大独立集定义选出一些顶点使得这些顶点两两不相邻则这些点构成的集合称为独立集。找出一个包含顶点数最多的独立集称为最大独立集。方法最大独立集所有顶点数-最小顶点覆盖。当是二分图时定理UV-MV顶点数M最大匹配数最小覆盖数U最大独立集。在左面这个图中最小顶点覆盖3即 2,4,7 构成最小顶点覆盖则其他点6个构成最大独立集。且其他点不可能相连。假设其他点相连则这条边必定没有被 2,4,7 覆盖与 2,4,7 是最小顶点覆盖矛盾。因此其他点之间必定没有边。而 2,4,7 是最小顶点覆盖所谓最小就是不能再小了因此我们的独立集就是最大了。3.有向无环图DAG的最小路径覆盖定义在一个有向图中找出最少的路径使得这些路径经过了所有的点。最小路径覆盖分为最小不相交路径覆盖和最小可相交路径覆盖。最小不相交路径覆盖每一条路径经过的顶点各不相同。如图其最小路径覆盖数为3。即1-3425。最小可相交路径覆盖每一条路径经过的顶点可以相同。如果其最小路径覆盖数为2。即1-3-42-35。特别的每个点自己也可以称为是路径覆盖只不过路径的长度是0。什么是有向图G的最小路径覆盖首先图G必须是有向无环的。路径覆盖就是在图G中找出一些路径每条路径从起点走到终点并且标记中间经过的点。最后每个点只被标记一次。选出的这些路径组成路径覆盖。如果找出最少的路径成为一个路径覆盖则称为最小路径覆盖。在上图中,以下两个均是路径覆盖a、1,2 4,6 3 5b、1,2,4,6 3 5在上面两个覆盖中b为最小覆盖|b|3,而|a|4。注意一个单独的节点也是一个路径由原图G构造对应的二分图S将原图G中的每个点i拆成两个点i1和i2i1和i2属于S。i1组成二分图的X集合i2组成Y集合。若原图G中有边i,j则在S中有边i1,j2则上面的图可以得到如下二分图把原图的每个点V拆成Vx和Vy两个点如果有一条有向边A-B那么就加边Ax−By。这样就得到了一个二分图。那么最小路径覆盖原图的结点数-新图的最大匹配数。证明一开始每个点都是独立的为一条路径总共有n条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径也就相当于路径数减少了1。所以找到了几条匹配边路径数就减少了多少。所以有最小路径覆盖原图的结点数-新图的最大匹配数。因为路径之间不能有公共点所以加的边之间也不能有公共点这就是匹配的定义。