二分图及匹配算法

1、-这是个问题- 二分图现有若干大龄男女青年，要安排相亲，每位女青年只能和一位男青 年结为对象，为了使得每位女青年都有对象，可供选择的男青年至少要和 女青年一样多，可女青年不会草率地处理终生大事，她们都有一个自己认 为可以接受的配偶的名单。那么： 1.每个女青年是否都可以和自己名单里的男青年结为对象？ 2.什么条件下可以满足所有女青年的心愿？如果不能满足，那么最多有几 位女青年可以找到心仪的对象？ 3.如何匹配，才能使结为对象后的家庭最为美满？ 二分图及匹配算法 Made by siang 二分图 概述 01 二分图 最大匹 配 02 二分图 最佳匹 配 03 二分图 模型的 应用 04 稳定婚

2、 姻问题 05 内容大纲 Chapter 1 二分图概述 -二分图概述- “二分”指中国人民银行在以前发行的一种钞票面值。 二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无 向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条 边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。 Chapter 2 二分图最大匹配 -二分图匹配- 给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条 边都不依附于同一个顶点，则称M是一个匹配匹配。 极大匹配极大匹配是指在当前已完成的匹配下,无法再通过

3、增加未完成匹配的边的 方式来增加匹配的边数。 最大匹配最大匹配是所有极大匹配当中边数最大的一个匹配。选择这样的边数最 大的子集称为图的最大匹配问题。 如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配 为完全匹配，也称作完备匹配完备匹配。 -算法的前奏- 内容：图G的匹配M是最大匹配当且仅当G中没有M-增广路。 学习二分图匹配需要用到3个定理：Berge定理，Hall定理，Konig定理 给定图G的一个匹配M。如果一条路径的边交替出现在M中和不出现在M 中，则这条路径为一条M-交错路径。路径的起始点和终点未被M匹配的 M-交错路径称为M-增广路径。 设增广路径M 则|M|=|M|+

4、1 1.Berge定理 2.Hall定理 对于G=V，E，SV，V中与S通过边直接相连的点称为S的邻集，记做 N（S） 内容：在二分图G=X,Y;E中，存在一个匹配M，使得X中所有点都被M 匹配当且仅当对于任意SV，都有|N（S）|=|S| -匈牙利算法- 匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。 匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常 见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求 二分图最大匹配的算法。 算法轮廓： 置M为空 找出一条增广路径P，通过异或操作获得更大的匹配M代替M 重复操作直到找不出增广路径为止 -Hopc

5、roft-karp算法- 为了降低时间复杂度，可以在增广匹配集合M时，每次寻找多条增广 路径。这样就可以进一步降低时间复杂度，可以证明，算法的时间复 杂度可以到达O（n0.5*m） 看下面的还不如听我解释： （1）从G=(X,Y;E)中取一个初始匹配。 （2）若X中的所有顶点都被M匹配，则表明M为一个完美匹配，返回； 否则，以所有未匹配顶点为源点进行一次BFS，标记各个点到源点的 距离。 （3）在满足disv = disu + 1的边集中，从X中找到一个未被M 匹配的顶点x0，记S = x0，T = 。 （4）若N（S） = T，则表明当前已经无法得到更大匹配，返回；否 则取一y0N(S) -

6、 T。 （5）若y0已经被M匹配则转步骤（6），否则做一条x0-y0的M-增广 路径P（x0,y0）,取M = MP（x0,y0）。 （6）由于y已经被M匹配，所以M中存在一条边（y0,z0）去S = S z0，T = Ty0，转步骤（2） -二分图多重匹配- 在二分图最大匹配中，每个点（不管是X方点还是Y方点）最多只能 和一条匹配边相关联，然而，我们经常遇到这种问题，即二分图匹配 中一个点可以和多条匹配边相关联，但有上限，或者说，n表示点i最 多可以和多少条匹配边相关联。 解决一：利用网络流 解决二：改进匈牙利算法 1.从G=X,Y;E中取一个初始值匹配M。设置上限下限 2.对最大限制n进行

7、二分搜索 3.若x都被M匹配，则可行，转至2.否则若与yi匹配的数量 小于n，则匹配xi，yi 4.如果yi匹配达到上限，那么在yi中选择一个元素增广，如 果能让出位置，匹配xi，yi。转至2. Chapter 3 二分图最佳匹配 -二分图最佳匹配- KuhnMunkras算法：该算法是通过给每个顶点一个标号（叫做顶标） 来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标 为A i ，顶点Yj的顶标为B j ，顶点Xi与Yj之间的边权为wi,j。在算法 执行过程中的任一时刻，对于任一条边(i,j)，A i +Bj=wi,j始终成立。 KM算法的正确性基于以下定理： 若由二分图中所

8、有满足A i +Bj=wi,j的边(i,j)构成的子图（称做相等 子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。 KM算法流程： (1)初始化可行顶标的值； (2)用匈牙利算法寻找完备匹配； (3)若未找到完备匹配则修改可行顶标的值； (4)重复(2)(3)直到找到相等子图的完备匹配为止； 这样做是O（n4）的 定义：图G中权值和最大的完全匹配。 -二分图最佳匹配- 改进 我们给每个Y顶点一个“松弛量”函数slack，每次开始找增广路时初始化为 无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中， 则让slackj变成原值与A i +Bj-wi,j的较小值。这样

9、，在修改顶标时，取 所有不在交错树中的Y顶点的slack值中的最小值作为d值即可。但还要注意 一点：修改顶标后，要把所有的不在交错树中的Y顶点的slack值都减去d。 这样是O（n3）的。 -二分图最佳匹配- KM算法的几种转化： 1.二分图最佳匹配=最小点权覆盖（对偶问题） 2.KM算法是求最大权完备匹配，如果要求最小权完备匹配怎么办？方法很 简单，只需将所有的边权值取其相反数，求最大权完备匹配，匹配的值再 取相反数即可。 3.KM算法的运行要求是必须存在一个完备匹配，如果求一个最大权匹配(不 一定完备)该如何办？依然很简单，把不存在的边权值赋为0。 4.KM算法求得的最大权匹配是边权值和最

10、大，如果我想要边权之积最大， 又怎样转化？还是不难办到，每条边权取自然对数，然后求最大和权匹配， 求得的结果a再算出ea就是最大积匹配。至于精度问题则没有更好的办法 了。 -二分图网络流解法- 具体解决方法略。你们懂得！ 关于费用流与KM算法的比较： KM时间复杂度比费用流好，但是实际上差不多，对于稀疏 图来说，许多优秀的费用流算法效率也很高，相对而言KM编程复杂 度低。 Chapter 4 二分图模型的应用 -二分图模型的应用- 我们在谈最佳匹配的时候已经说明了：二分图最佳匹配=最小点权覆 盖(证明略)，所以现在谈一谈二分图的其他变换： 1.二分图最大匹配=最小顶点覆盖（要求在二分图下） 2

11、.二分图最大独立集数=顶点总数-最大匹配数（要求在二分图下） 3.最小路径覆盖（有向无环图） 在一个的有向图中，路径覆盖就是在图中找一些路经，使之覆盖 了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联；（如果把 这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中 的每个顶点一次且仅一次）；如果不考虑图中存在回路，那么每条路径就是 一个弱连通子集 -二分图模型的应用- 由上面可以得出： .一个单独的顶点是一条路径； 如果存在一路径p1,p2,.pk，其中p1 为起点，pk为终点，那么在覆盖 图中，顶点p1,p2,.pk不再与其它的顶点之间存在有向边 我们这样理清一个关系：

12、最小路径覆盖数=G的点数-最小路径覆盖中的边数 将每一个顶点i拆分成两个顶点Xi，Yi，然后根据原图中边的信息从X部向 Y部引边，方向由X到Y。这样就构成了一个二分图。我们发现，最大匹 配数就是原图G中最小路径覆盖数边数。 我们可以得到：最小路径覆盖数=G的顶点数-二分图最大匹配 Chapter 5 稳定婚姻问题 -稳定婚姻问题- 你们班上有n位男生和n位女生，每个人对异性都有一个排序，表示对他们 的爱恋程度。现在你的任务是使他们凑成CP，使他们的爱情坚不可摧！ 满足一下条件的爱情不是坚不可摧的： 男生u和女生v不是CP，但他们爱恋对方的程度都大于爱恋现任 的程度。 因为这样男生u和女生v会抛

13、下已经是CP的那个她/他，另外组成一对。于 是乎多出了两位前任，这样就会让人再也无法相信爱情了！ 怎么能避免悲剧的发生呢？ -稳定婚姻问题- 求婚拒绝算法（Gale-Shapley算法/延迟认可算法）： 先对所有男生进行单身标记，称其为单身狗男。当存在单身狗男时，进行 以下操作： 选择一位单身狗男在所有尚未拒绝她的女生中选择一位被他排名最优先 的女神； 女神将正在追求她的单身狗男与其现任进行比较，选择其中排名优先的 男生作为其男友，即若单身狗男优于现任，则现任被抛弃为前任；否则保 留其男友，拒绝单身狗男。 若某男生被其女友抛弃，则重新变成单身狗男，至重复。 -稳定婚姻问题- 求婚拒绝算法（Ga

14、le-Shapley算法/延迟认可算法）： 函数 稳定婚姻 初始所有 m in M 与 w in W 为 单身 当 存在单身 男子 m w = m所有可考虑的女子中排名最高的 若 w 是 单身 撮合 (m, w) 否则 有些夫妇 (m, w) 存在 若 w 喜欢 m 更于 m (m, w) 为 夫妇 m 为 单身 否则 (m, w) 仍为 夫妇 -稳定婚姻问题- 这么个过程数学上可以证明： 第一，这个过程会中止，也就是说，总有大家都订了婚的一天，不可能无限循 环。 第二，中止后所有的婚姻是稳定婚姻。所谓不稳婚姻是说，比如说有两对夫妇 M1,F1和M2,F2,M1的老婆是F1,但他更爱F2;而F2的老公虽说是M2.但她更爱M1, 这样的婚姻就是不稳婚姻,M1和F2理应结合,他们现在各自的婚姻都是错误.我们 能证明的是,通过上面那个求婚过程,所有的婚姻都是稳定的,没有人犯错误。 第三,比较引人注目的是，这个过程是male-optimal的，男性能够获得尽可能好 的伴侣，比如说最后有二十个女人拒绝了他，他仍然能够得到剩下的八十个女 人中他最爱的那一个。 第四，更有甚者，这个过程是female-pessimal的,女人总是在可能的情况下被最 不喜欢的人追上。这一点没有那么直观的理解，勉强要解释的话，可以这么看: 虽说女人每换一次订婚对象，都往上升一层，但起点可能很低，虽说在一步步 接近