当前位置：文档之家 › 基本概念匹配最大匹配完美匹配 - 组合最优化.

基本概念匹配最大匹配完美匹配 - 组合最优化.

  • 格式：pdf
  • 大小：252.72 KB
  • 文档页数：7

下载文档原格式

  / 7

合集下载

四大匹配原理的应用场景

四大匹配原理的应用场景

四大匹配原理的应用场景
四大匹配原理指的是最大匹配原理、最小匹配原理、最大权匹配原理和最小权匹配原理。

这些原理在算法中广泛应用于各种场景，以下列举一些常见的应用场景：
1. 图论中的匹配问题：最大匹配原理和最小匹配原理在图论中被广泛应用于解决匹配问题，如最大匹配数和最小匹配数的求解，二分图的完美匹配问题等。

2. 任务分配：最大权匹配原理和最小权匹配原理可用于解决任务分配问题，如在资源有限的情况下，将任务分配给最合适的人员或设备，以最大化或最小化配对的权重。

3. 社交网络分析：匹配原理可应用于社交网络中的社交关系分析，如推荐系统中的好友推荐、配对算法中的匹配问题等。

4. 信息检索与推荐系统：最小匹配原理可应用于信息检索与推荐系统中的相关性匹配问题，如在文本检索中，通过匹配文档和查询的关键词，进行相关性排序和推荐。

5. 婚姻稳定性问题：最大匹配原理和最小匹配原理可以应用于解决婚姻稳定性问题，如解决稳定婚姻匹配的问题，确保没有任何对两个人有更强吸引力的第三人。

需要注意的是，四大匹配原理并不仅限于以上应用场景，它们在组合数学、运筹学、计算机科学等领域都有广泛的应用。

实际应用中，需要根据具体的问题和算法设计来选择合适的匹配原理。

组合优化

组合优化

0 0 3 4 4 7
0 0 3 4 5 7
0 0 3 4 5 7
启发式算法
• 在实际应用中，可以通过数值模拟的方法 来衡量算法的性能，从而免去了理论证明 的困难和局限，使我们可以充分地利用经 验和技巧，自由地调整算法的步骤和参 数，设计出性能尽可能好的算法。这样的 算法称为启发式算法（heuristic）
k 0 w • 实例 0 0 C 5, n 4 p1 3, p2 4, p3 5, p4 6 1 0 w1 2, w2 3, w3 4, w4 5 2 0 • 最优值为 7，最优 3 0 解为物品1，2 放入 4 0 背包 5 0
1 2 3 4
0 0 3 3 3 3
• 由初始条件和递推关系可逐步求得 I (n, C)， 外层循环为 k 0,, n ，内层循环为 w 0,, C • 该动态规划时间复杂性为 Ο(nC) ，背包问题 的实例规模为 Ο(n log2 B), B max{ p j , wj , C} ， 因此它是一个伪多项式算法
背包问题的动态规划
中国邮递员问题
• 一位邮递员从邮局选好邮件去投 递，然后返回邮局。他必须经过 由他负责投递的每条街道至少一 次。如何为这位邮递员设计一条 投递线路，使其耗时最少。
中国邮递员问题
• Euler环游（一笔画）
• 经过图中所有边恰好一 次的回路称为Euler 回路 ，含有Euler回路的图称 为Euler 图 • 图是Euler 图的充要条件 是图中没有奇度顶点
P NP 假设下
• NP 类中的问题既不是没有多项式时间算法的问题 ，也不是最难的问题。
P NP 假设下
P 与NP-hard
• P问题
• 图的最短路 • 图的最大流、最小割 • 背包问题 • 划分问题 • 图的独立集、团、顶 点覆盖 P 问题 线性规划 （二维）匹配 指派 Euler圈 中国邮递员 最小生成树 NP-hard问题 整数规划 三维匹配 二次指派 Hamiltion圈 TSP 最小Steiner树

二分图匹配题目类型总结.

二分图匹配题目类型总结.

二分图匹配题目类型总结二分图最大匹配的匈牙利算法二分图是这样一个图，它的顶点可以分类两个集合X和Y，所有的边关联在两个顶点中，恰好一个属于集合Ｘ，另一个属于集合Ｙ。

最大匹配：图中包含边数最多的匹配称为图的最大匹配。

完美匹配：如果所有点都在匹配边上（x=y=m），称这个最大匹配是完美匹配。

最小点覆盖：(二分图)最小覆盖要求用最少的点（Ｘ集合或Ｙ集合的都行）让每条边都至少和其中一个点关联。

可以证明：最少的点（即覆盖数）＝最大匹配数。

支配集：（二分图）最小点覆盖数+孤立点最小边覆盖：找最大匹配（注意可能是任意图最大匹配）m则有2*m 个点被m 条两两不相交的边覆盖。

对于剩下的n-2*m 个点，每个点用一条边覆盖，总边数为n-m条;最小路径覆盖：用尽量少的不相交简单路径覆盖有向无环图Ｇ的所有结点。

解决此类问题可以建立一个二分图模型。

把所有顶点i拆成两个：Ｘ结点集中的i和Y结点集中的i',如果有边i->j，则在二分图中引入边i->j'，设二分图最大匹配为m,则结果就是n-m。

最大独立集问题：(二分图)n-最小点覆盖;任意图最大匹配：（没有奇环）转换为二分图：把所有顶点i拆成两个：Ｘ结点集中的i和Y结点集中的i',如果原图中有边i->j，则在二分图中引入边i-> j',j->i’；设二分图最大匹配为m,则结果就是m/2。

最大完全子图：补图的最大独立集三大博弈问题威佐夫博奕（Wythoff Game）：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

这种情况下是颇为复杂的。

我们用（ak，bk）（ak ≤bk ,k=0，1，2，...,n)表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。

前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。

常见5种基本匹配算法

常见5种基本匹配算法

常见5种基本匹配算法在计算机科学中，匹配算法（Matching algorithms）是指用于确定一个集合中的元素是否与另一个集合中的元素相匹配的算法。

匹配算法可以应用于各种领域，如字符串匹配、模式匹配、图匹配等。

下面介绍五种常见的基本匹配算法。

1. 暴力匹配算法（Brute Force Matching Algorithm）：暴力匹配算法是最基本的匹配算法之一、它遍历待匹配字符串和目标字符串，逐个字符进行比较，直到找到匹配或者遍历完整个字符串。

该算法的时间复杂度为O(n*m)，其中n和m分别是待匹配字符串和目标字符串的长度。

2. KMP匹配算法（Knuth-Morris-Pratt Matching Algorithm）：KMP匹配算法是一种优化的字符串匹配算法。

它通过预处理待匹配字符串的信息，快速确定定位下一次比较的位置，减少了不必要的比较次数，从而提高了匹配效率。

该算法的时间复杂度为O(n+m)，其中n和m分别是待匹配字符串和目标字符串的长度。

3. Boyer-Moore匹配算法：Boyer-Moore匹配算法是一种高效的字符串匹配算法。

它利用了字符出现位置的规律，从目标字符串的末尾开始匹配，并利用预处理的跳转表格快速跳过不匹配的字符，从而减少比较次数。

该算法的平均时间复杂度为O(n/m)，其中n和m分别是待匹配字符串和目标字符串的长度。

4. Aho-Corasick算法：Aho-Corasick算法是一种多模式匹配算法，适用于在一个文本中同时查找多个模式串的情况。

该算法利用Trie树的特性，同时利用一个自动机状态转移表格进行模式匹配，可以高效地找到多个模式串在文本中的出现位置。

该算法的时间复杂度为O(n+k+m)，其中n是文本长度，k是模式串的平均长度，m是模式串的个数。

5. Rabin-Karp算法：Rabin-Karp算法是一种基于哈希函数的字符串匹配算法。

它通过对待匹配字符串和目标字符串的部分子串进行哈希计算，比较哈希值是否相等，进而确定是否匹配。

组合优化算法

组合优化算法

组合优化算法组合优化问题已经成为当今研究领域的热门话题，这是由于随着现代科技的发展，许多组合优化问题日益普遍，需要有效的算法来解决这些问题。

组合优化是指应用算法来求解组合最优化问题，使得组合中每个元素都能尽可能最大限度地实现最优化。

组合优化算法是指组合优化问题的解决方案，它通过探索搜索途径，克服问题的复杂性，并最终寻求最优解。

组合优化算法可以分为两类：搜索算法和极限优化算法。

搜索算法是一种迭代搜索算法，运行的过程中以搜索的方式来搜索更合适的解决方案。

搜索算法的过程可以用树状图来表示，中心是起点，外围是有可能的解决方案，而搜索算法根据定义的条件来搜索解析，最终得出最优解。

极限优化算法也叫边界优化，是一种用数学方法来解决包含约束条件的优化问题的算法。

极限优化算法的实现过程是遍历搜索边界上的极值点，通过极值点来近似优化问题的最优解，而不是穷尽地去搜索整个空间的解决方案。

组合优化算法的发展尤其引人瞩目，今天，它们应该是投资者、科学家和工程师们的热门话题，不仅能够解决现有的组合优化问题，而且也能够解决更大规模和更复杂的问题。

组合优化算法在处理复杂的投资决策、技术设计、系统工程等各个方面都有广泛的应用，为当今科技的发展提供了重要的支持。

针对组合优化算法，有许多有影响力的研究成果，比如遗传算法、蚁群算法、混合算法、模糊多目标优化算法等。

遗传算法是一种基于进化规则的算法，它模拟自然界中的进化过程，将最优解直接映射到算法搜索空间中，从而有效地解决组合优化问题。

蚁群算法是一种仿生模型，它模拟蚂蚁行为来解决组合优化问题，采用信息素的概念，集群策略实现全局最优解的搜索；混合算法则是将遗传算法、蚁群算法和其他优化算法结合在一起，实现更好的求解效果；模糊多目标优化算法则采用模糊逻辑理论，结合多目标模型，实现多目标优化。

总之，组合优化算法已经发展成为一个热门的研究领域，它们的研究成果和应用发展为当今的科技发展提供了重要的支持和帮助。

常见5种基本匹配算法

常见5种基本匹配算法

常见5种基本匹配算法匹配算法在计算机科学和信息检索领域广泛应用，用于确定两个或多个对象之间的相似度或一致性。

以下是常见的5种基本匹配算法：1.精确匹配算法：精确匹配算法用于确定两个对象是否完全相同。

它比较两个对象的每个字符、字节或元素，如果它们在相同位置上完全匹配，则返回匹配结果为真。

精确匹配算法适用于需要确定两个对象是否完全相同的场景，例如字符串匹配、图像匹配等。

2.模式匹配算法：模式匹配算法用于确定一个模式字符串是否出现在一个文本字符串中。

常见的模式匹配算法有暴力法、KMP算法、BM算法等。

暴力法是最简单的模式匹配算法，它按顺序比较模式字符串和文本字符串的每个字符，直到找到一次完全匹配或结束。

KMP算法通过预处理建立一个跳转表来快速定位比较的位置，减少了无效比较的次数。

BM算法利用模式串的后缀和模式串的字符不完全匹配时在文本串中平移模式串的位置，从而快速定位比较的位置。

3.近似匹配算法：4.模糊匹配算法：5.哈希匹配算法：哈希匹配算法用于确定两个对象之间的哈希值是否相等。

哈希值是通过将对象映射到一个固定长度的字符串来表示的，相同的对象会产生相同的哈希值。

常见的哈希匹配算法有MD5算法、SHA算法等。

哈希匹配算法适用于需要快速判断两个对象是否相等的场景，例如文件的完整性校验、数据校验等。

以上是常见的5种基本匹配算法，它们各自适用于不同的场景和需求，选择合适的匹配算法可以提高效率和准确性，并且在实际应用中经常会结合多种算法来获取更好的匹配结果。

基本概念匹配最大匹配完美匹配 - 组合最优化.


令
，
。我们不妨先假设
是一个顶点覆盖。那显
然与
中的每个顶点相关联。既然 是一个匹配，所以 中不存在两端点都在
中的边。因为，给定一个被匹配的顶点
，设
为匹配边，那么由
的构建可知 一定也在 。
剩下的问题就是来证明
中，从而 中每条边至少与
中的一个端点相交。综上，
是顶点覆盖。假设不是，那么必存在一条以
和
为两端点的边
□
要在一般图中找一条可增广路，我们可以修改一下二部图中的算法，使之可以发现花。发现 了，就对其进行收缩，然后在新的图上重新开始。在新图上找到的任意增广路都可以很容易 的对应到原图中的增广路，而且，由上面的引理可知，如果在新图中匹配是最大的，那么原 图中对应的匹配也是最大的。
下面是算法的正式描述。令 为图 的一个匹配， 为未被匹配顶点的一个子集（如果 每个顶点都是被匹配的，那么这个匹配就是最大匹配），我们要构造一个森林 ，使 中 的每一个顶点在一个连通分支上。像以前那样交替的增加未匹配边和匹配边来扩展 。那 么被添加到 中的 的边与 的距离为奇数。而且，与 距离为奇数的顶点度数为 2（一 条未匹配边，一条匹配边），我们把这样的顶点称为内顶点，而其余的称外顶点。 中所有 的顶点都是外顶点。
是 M 和 P 的对称差，记为
容易证 也是一个匹配，而且所含边数比 M 多一条。
这样的交错路 P 称为一条可增广路。上述分析就产生了下面的“算法”。
匹配算法：
{ 1、 从任意匹配开始。 2、 找当前匹配的一条可增广路。 3、 增广当前匹配。 4、 尽可能地重复上面两步。
} 算法终止的时候，得到一个没有可增广路的匹配 们此时 一定是最大匹配。
完美匹配。如果 A 等于 0 或 1，显然结论成立。下面分两种情况考虑：

最大匹配算法

最大匹配算法
在解释最大匹配算法之前，我们先来了解一下什么是二分图和最大匹配。

二分图是指一个图的所有顶点可分为两个互斥的顶点集合，且任意一条边的两个端点都分属于不同的顶点集合。

二分图可以用一个二元组(V,E)表示，其中V表示顶点集合，E表示边集合。

最大匹配是指在一个二分图中找到一个边的子集，使得该子集中的边两两没有公共顶点，并且该子集中的边数量最大。

匈牙利算法是通过增广路径的方式求解最大匹配。

增广路径是指在一个二分图中，通过一系列的未匹配边和匹配边交替组成的路径，起点和终点分别属于不同的顶点集合。

下面是匈牙利算法的步骤：
1.初始化一个空的最大匹配。

2.对二分图中的每个未匹配顶点，找到一个增广路径。

如果找到了增广路径，就将其上的匹配边和未匹配边互换，并将路径上的所有未匹配边变为匹配边，所有匹配边变为未匹配边。

3.重复步骤2，直到无法找到增广路径为止。

在匈牙利算法中，为了找到增广路径，通常会使用深度优先或广度优先。

具体的实现方式可以根据实际情况选取。

匈牙利算法的时间复杂度为O(VE)，其中V为顶点的数量，E为边的
数量。

由于每次找到增广路径后都会改变匹配边和未匹配边的状态，所以
算法的时间复杂度可能比较高。

但是在实际应用中，匈牙利算法在大多数情况下都能快速求解最大匹配问题。

总结起来，最大匹配算法（匈牙利算法）是一种用于求解二分图最大匹配的算法，通过不断寻找增广路径来实现。

它的时间复杂度为O(VE)，并且在实际应用中具有广泛的应用价值。

论服装卖场陈列设计中的“匹配原则”

服务部分则主要 有试衣室 、 收银台 、 仓库等组成 。
３２ 服装 卖场 陈 列 设 计 中 的人 机 工 程 学 “ 配原 则” ． 匹
械 、人与环境 以及机械 与环境之 间的相 互作用 ， 人一机一环 “
境”的配合达到最 佳状态的工程系统提供理论和方法 的科学 。 研究 的 目的是寻求 “ 舒适 、 有效 、 ”其学科体系涉及广泛 ， ： 美 ， 如 人体测量学 、 生理学 、 心理学 、 人体力学 、 美学 、 环境 医学和工程
２０ ０ ９年 ６月
广 西 轻 工 业
ＧＵＡ ＮＧＸＩ Ｊ ＵＲＮ ＡＬ Ｏ ＯＦ ＬＩ ＧＨＴ Ｉ Ｎ
．
第 ６期 （ 第 １７期 ） 总 ２
Ｄ ＳＲ ＵＴＹ
纺 织 与设 计
论 服装 卖场 陈列设 计 中的“ 匹配原 则＂
袁 燕
（ 攀枝 花学 院 ， 四川 攀枝 花 ６ ０ ０ ｌ ０） ７
人体工程学 在服装卖场陈列设 计中的有效利用 ， 主要是针 对顾客 的生理和心理 的特点 ， 使卖场 的设备和规划更好的满足 顾客要求。服装卖场设计 中的“ 一机 一环境 ” 人 系统 ，人 ” “ 就是 消费者 ；机” “ 为展架、 道具等 ；环境” 的是服装卖场的空间环 “ 指 境 。 以“ ” 在 人 为本 的设计理念指导下 ， “ ——展架 、 使 机” 道具等 和“ 环境 ” ——服装卖场空间环境更好的服务于消费者 。 使卖场 具有更好的有效性 、 舒适性 、 美观性 。 服装卖 场陈列设 计中的“ 匹配原则” 则就是实现 消费者 原
技术 等多个领域。其 中“ ——指操作者或使用者 ；机” — 人” “ —
泛指人操作或使用 的物 ， 以是机器 ， 可以是用 具、 可 也 工具或设 施、 设备等 ；环境 ” “ ——是 指人 、 所处 的周 围环境 ， 作业 场 机 如

多对多组合匹配算法

多对多组合匹配算法1. 引言1.1 背景介绍在当今社会，随着信息时代的来临，数据的数量呈指数级增长，如何高效地进行数据的匹配和组合成为了一个重要的课题。

而多对多组合匹配算法作为解决这个问题的一种重要方法，受到了越来越多的关注和研究。

背景介绍着眼于当前大数据时代背景下，多对多组合匹配算法的重要性和必要性。

在实际应用中，如社交网络、推荐系统、交通管理等领域，常常需要对大量的数据进行有效的匹配与组合。

传统的匹配算法往往只涉及到一对一或者多对一的匹配，而多对多组合匹配算法的出现填补了这一空白，能够更加灵活高效地处理多对多的匹配需求。

本文将从多对多组合匹配算法的概述、基本原理、常见算法、优缺点分析以及应用领域等方面进行探讨，旨在全面介绍多对多组合匹配算法的研究现状和发展趋势，为相关领域的研究者提供参考和借鉴。

1.2 研究意义多对多组合匹配算法在当今社会中具有非常重要的研究意义。

随着信息技术的快速发展，人们在日常生活和工作中需要处理大量的数据和信息，而多对多组合匹配算法可以帮助人们更有效地处理这些信息，提高工作效率。

多对多组合匹配算法在许多领域都有着广泛的应用，比如在社交网络中，人们需要进行多对多的匹配，以找到适合自己的朋友或合作伙伴；在物流配送中，需要对多个货物进行合理的匹配和分配；在生物信息学中，可以用于多对多基因组的比对和分析等等。

研究多对多组合匹配算法不仅可以帮助人们更好地处理信息和数据，提高工作效率，还可以推动各个领域的发展和进步。

希望通过深入研究多对多组合匹配算法，能够为实际应用提供更多有益的启发和帮助，促进社会的发展和进步。

2. 正文2.1 多对多组合匹配算法概述多对多组合匹配算法是一种重要的匹配算法，其主要作用是在多个数据集之间进行匹配，实现多对多的关联。

在实际应用中，我们经常会遇到多对多的关系，例如用户和商品之间的关系，学生和课程之间的关系等。

多对多组合匹配算法在数据处理和分析中具有非常广泛的应用前景。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

们可以转换 中的边而得到与 同样大小的一个匹配 。然后， 满足圈收
缩引理的条件，我们可以把 收缩成一个顶点，从而得到一个新图 。接下来
我们的目的就变为在 中寻找一条可增广路。
4、 如果每个外顶点都仅与内顶点相邻，那么 已经是最大匹配。为了得出这个结论，
不妨假设 有 p 个内顶点和 q 个外顶点，那么
□
要在一般图中找一条可增广路，我们可以修改一下二部图中的算法，使之可以发现花。发现 了，就对其进行收缩，然后在新的图上重新开始。在新图上找到的任意增广路都可以很容易 的对应到原图中的增广路，而且，由上面的引理可知，如果在新图中匹配是最大的，那么原 图中对应的匹配也是最大的。
下面是算法的正式描述。令 为图 的一个匹配， 为未被匹配顶点的一个子集（如果 每个顶点都是被匹配的，那么这个匹配就是最大匹配），我们要构造一个森林 ，使 中 的每一个顶点在一个连通分支上。像以前那样交替的增加未匹配边和匹配边来扩展 。那 么被添加到 中的 的边与 的距离为奇数。而且，与 距离为奇数的顶点度数为 2（一 条未匹配边，一条匹配边），我们把这样的顶点称为内顶点，而其余的称外顶点。 中所有 的顶点都是外顶点。
，
表示与其相邻的顶点集合。由上面的
定理可以得出经典的 Frobenius-Hall 定理
（实际上两者等价）。
定 理 5.(Frobenius-Hall) 。
有一个到 的匹配当且仅当 的任意子集 满足
证明. 显然，如果存在子集 满足
，则一定不存在以 为基数的匹配。
反之，假设
对任意
成立，我们想证明最小顶点覆盖的大小为 ，
分支中。
3、 加入 中与
中顶点相邻接的边。
4、 重复上面两步直到再没有边被加入 。
如果森林中存在 中的一个顶点，就给出了一条可增广路。否则，由下面的引理可知， 即为最大匹配。
引理 3. 是最大匹配当且仅当 不含有 中的顶点。
证明. 如果 包含 中的一个顶点 ，那么从 到 中顶点的这条路在顶点 所在的分 支中是一条以未匹配的顶点为端点的交错路，也就是一条可增广路。因此 不是最大匹配。
的导出子图最大度数为 2。注意到 和 都是匹配，所以，这些路和
首先考虑导出图中的圈。所有圈的边数一定为偶数，否则一定有一个顶点与 或 中的 两条边相邻，这与匹配的定义矛盾。所以，这些圈中含有的 和 的边数相等。
接下来考虑导出子图中的路。假设有一条路 P 含有奇数条边，那么要么来自 的边比来自 的边多一条，要么相反。在前一种情况下，P 是 的一条可增广路，与 是最大匹
令
，
。我们不妨先假设
是一个顶点覆盖。那显
然与
中的每个顶点相关联。既然 是一个匹配，所以 中不存在两端点都在
中的边。因为，给定一个被匹配的顶点
，设
为匹配边，那么由
的构建可知 一定也在 。
剩下的问题就是来证明
中，从而 中每条边至少与
中的一个端点相交。综上，
是顶点覆盖。假设不是，那么必存在一条以
和
为两端点的边
从而就可以证明本定理。由假设知 中任一顶点至少与一条边相关联，且
。注
意到顶点集 是一个大小为 的顶点覆盖。设
是另一顶点覆盖，这里
，
，可以看出
，从而
，所以
，即证明了 是一个最小覆盖，大小为 。
□
定理 6. 在二部图中寻找一个最大匹配需要
。
4
证明. 易知找一条增广路需要
，而最多增广 次，因此总时间为
。我们可
的一条可增广路。令 表示从 出发通过交错路可达的顶 中的一个顶点，那么到这个顶点的这条交错路就是 的一
集合 可以通过如下方法构造一个交错森林 得到：
1、 将 中的所有顶点加入 ，每个均为 的独立分支。
2、 加入从
中顶点到 中顶点的边，注意，不要合并任何两个连通分支。
也就是说，如果 中的一个顶点不止邻接于一个分支，那么仅将其添加到一个
| N(U ) | ≥ |U | (∀U ⊆ A).
证明：若二部图存在完美匹配，显然右边是一个必要条件。 对顶点集为 A 和 B 的二部图，若右边条件成立，下面我们对 A 利用归纳法来证明此图存在
完美匹配。如果 A 等于 0 或 1，显然结论成立。下面分两种情况考虑：
1、 假设 (∀U ⊆ A, U ≠ ∅, U ≠ A) | N(U ) | > |U | 。令 e = (u,v) , G′ = G −{u} −{v} .
是 中的一条可增广路，所以此时， 也不是 的最大匹配。
接下来，假设 不是 的最大匹配，我们要证明 也不是 的最大匹配。取 中的一 条增广路 ，假设其与 相交，否则 也是 中的可增广路。注意到， 仅包含一个未 被匹配的顶点，所以 中至少有一个顶点，不妨设为 ，位于 外。用 表示从 开始
5
沿着 直到与 相交的一段路，可知 也是 的一条可增广路。从而结论得证。
中匹配边用粗体标明。
图 1：一个花
下面的引理给出了处理花的一个方法，它是求一般图中最大匹配的 Edmonds 算法的核心思 想。
引理 8.(圈收缩) 是图 的一个匹配， 是一个花，且与 中其余的边是顶点不交的（即 没有共同顶点）。把 收缩为单个顶点后得到一个新图 ，那么由 导出的匹配 是 的最大匹配当且仅当 是图 的最大匹配。
以对上面的分析加以改进。注意，寻找增广路的算法可能找到不止一条增广路，这种情况下，
我们可以对一个最大的不交增广路的集合进行增广。做这种改进后，可以证明总的阶段（交
错森林的构造）数为
。其中关键的结论如下（证明留作习题）：
结论 7. 在每个阶段中最短增广路的长度递增。
有了这个结论，可知在经过 个阶段后所有的增广路长度至少为
是 M 和 P 的对称差，记为
容易证 也是一个匹配，而且所含边数比 M 多一条。
这样的交错路 P 称为一条可增广路。上述分析就产生了下面的“算法”。
匹配算法：
{ 1、 从任意匹配开始。 2、 找当前匹配的一条可增广路。 3、 增广当前匹配。 4、 尽可能地重复上面两步。
} 算法终止的时候，得到一个没有可增广路的匹配 们此时 一定是最大匹配。
证明. 首先，假设 不是 的最大匹配。由引理 2 可知， 中含有 的一条可增广路 。假设 在 中不与 相交，那 一定也是 中的一条可增广路，从而 不是 的
最大匹配。所以， 在 中一定与 相交。特别地，收缩后的 一定是 中路 上的 一个端点，因为 与 是顶点不交的。不妨设 与 相交于顶点 ， 为 中未被匹配 的顶点。将 中从 出发，先经过与之相关联的匹配边，最后到达 的路称为 ，易知
在 G′ 中，对 ∀U ⊆ A −{u} 均有
| NG′ (U ) | ≥ | N(U ) | −1 ≥ | U | .
由归纳假设知 G′ 存在一个 A −{u}到 B −{v} 的完美匹配 M ，则 A 到 B 的一个完美匹配。
为G 中
2、 否则：必存在非空集 A′ ⊂ A 满足 | N ( A′) | = | A′ | 。令 G1 表示 子图， G2 表示 G − A′ − N ( A′) 的导出子图。
。考虑最大匹
配 和对称差
，如果 不是最大匹配，则对称差
中必存在一条交
错路是 的可增广路。既然每一条可增广路长度至少为
，且总共仅有
条
这样的路，那
，因此，最多再经过 个阶段算法就会终止。
□
2 一般图
不难看出前面的算法不适用于一般图。主要是因为一般图中可能存在含有最多匹配边的奇
圈，即长度为
含有 条匹配边的圈。这样的奇圈称为花，图 1 给出了一个例子，其
若图 G 的顶点集存在一个拆分 A 和 B ，且 G 中每条边恰好都是一个端点属于 A 而另一个端 点属于 B ，则称图 G 为二部图。下面的定理给出了二部图存在完美匹配的条件。对于
U ⊆ A ，记 N (U ) 为所有与U 中顶点相邻的顶点的集合。
定 理 1 （ Hall ） 顶 点 集 为 A 和 B 的 二 部 图 存 在 完 美 匹 配 当 且 仅 当 | A | = | B | 且
一个基数为 的最大匹配。如果 M 不是完美匹配，那要么可以找到一个比 M 基数更大的匹
配，也就是增广 M，要么断定 M 已经是最大匹配。增广 M 的一种方法如下：找一条路 P， 从未匹配顶点开始，交替的经过 M 中的边和不在 M 中的边（即匹配边和未匹配边），最后 结束于未匹配顶点。删去 P 上在 M 中的边而增加路上其余的边，得到边的集合 ，也就
18．433 组合最优化
September 4, 9, 11
匹配算法
授课教师：Santosh Vempala
给定一个图 G = (V , E) ，若边子集 M 内任两边不相邻，则称其为匹配。若顶点 v ∈V 与匹
配中的边相关联，则称 v 是匹配的，否则称 v 是未匹配的。含边数最多的匹配称为图 G 的最 大匹配。特别地，若在此最大匹配下图 G 的每个顶点都是匹配的，则称其为完美匹配。
现在，考虑外顶点的相邻顶点。只可能出现下列四种情况之一：
1、 如果我们找到外顶点 ，与不在 中的顶点 相邻，那么把边
和
两个外顶点是相邻的，那么这两个分支的根之间存在一条可
增广路。
3、 如果同一个分支中的两个外顶点 是相邻的，那么边
和 中从 到
的路形成一个圈，记为 。令 为 和这个分支的根之间的一条路。首先，我
□
那我们的算法要用多长时间呢？在第 2 和 3 步中，每做一次迭代匹配的基数增加 1，那我们
最多做 次迭代。接下来的问题就是找到一条可增广路需要多长时间。实际上我们必须弄 清楚如何寻找可增广路。我们先来看二部图的情况，这相对容易一些。
1 二部图
给定一个二部图， 是它的一个匹配，令
，