1 基本概念
最大匹配是图论中用于描述“成对连接”的核心概念之一。它关注的是在一张图里选出若干条边，使这些边彼此不共享端点，从而避免冲突。若在满足这一条件下，所选边的数量已经达到当前图结构所允许的上限，就称为最大匹配。该概念常被用来刻画资源之间的有效配对关系，也是在许多组合优化问题中出现的基础模型。
1.1 图与边的匹配定义
在图中，边连接着两个顶点。若取出一组边，并且这组边中的任意两条都不会在同一个顶点处相接，那么这组边就构成一个匹配。直观地说，匹配要求每个顶点在所选边中最多只能出现一次，因此不同边之间不会“争用”同一端点。
1.2 匹配的判定条件
判断一组边是否为匹配，关键在于检查这些边之间是否存在端点冲突。只要任意两条边没有共同端点，就可以认定它们彼此独立，满足匹配的要求。
1.2.1 边的端点互异性
匹配中的边必须保证端点互异，即同一顶点不能同时作为两条被选边的端点出现。这一条件是匹配定义中最直接的约束，也是防止重复占用的基本原则。
1.2.2 顶点不相邻约束
从顶点角度看，若某个顶点已经属于一条被选中的边，那么它就不能再与另一条被选边相连。也就是说，参与匹配的边在顶点层面应保持互不相邻的占用关系，从而形成分散而无冲突的配对结构。
1.3 最大匹配与极大匹配的区别
“最大匹配”强调规模最优，即边数在所有匹配中尽可能多；“极大匹配”则只要求不能再继续添加边而不破坏匹配性质。两者在定义上非常接近，但并不等价。
1.3.1 数量最优与局部不可扩展
最大匹配是全局意义上的最优解，关注的是匹配边数是否达到最大。极大匹配则更像局部饱和状态：只要再加入任意一条边都会造成冲突，就已满足要求，但这并不保证它是全局最大的那组边。
1.3.2 反例与直观理解
例如，在一条三边路径中，取中间一条边即可形成极大匹配，因为再加任何边都会冲突；但若改为取两端相隔的边，则可以得到更大的匹配。这个例子表明，极大并不等于最大，前者只保证“不能再扩”，后者要求“已经最多”。
1.4 相关术语
围绕匹配问题，还常用若干辅助术语来描述顶点状态和匹配规模，它们有助于更精确地讨论图中的配对结构。
1.4.1 饱和顶点
如果某个顶点已经与匹配中的一条边相连，那么称该顶点被匹配所饱和，或称其为饱和顶点。它表示这个顶点已经被当前配对方案占用。
1.4.2 未匹配顶点
没有与任何匹配边相连的顶点称为未匹配顶点。它们通常是后续寻找增广结构时重点关注的起点或终点。
1.4.3 匹配数
匹配数是指某个匹配中所包含的边的条数。对于最大匹配而言，匹配数达到所有匹配中可达到的最大值，因此也常被直接用来衡量匹配规模。
2 图论中的性质
最大匹配不仅是一个定义明确的对象，也具有若干稳定的图论性质。不同图结构下，最大匹配的大小、存在方式以及与其他概念之间的关系，往往会呈现出明显差异。
2.1 最大匹配的存在性
对于任意有限图，最大匹配总是存在的。原因在于图中的边数有限，而匹配的边集可以逐步扩展；在所有可行匹配中，必然能找到边数最多的一组。这种存在性是匹配理论中最基础的前提。
2.2 最大匹配的大小界
最大匹配的规模不会无限增长，它受到顶点数和边数等基本参数的限制。通过这些上界，可以迅速判断一个图中匹配可能达到的范围。
2.2.1 与顶点数的关系
若图中共有 n 个顶点，那么任一匹配至多包含 ⌊n/2⌋ 条边，因为每条匹配边都要占用两个不同顶点。这个界限是由配对本身的结构直接决定的。
2.2.2 与边数的关系
显然，匹配中的边数不可能超过图的总边数。此外，若图整体很稀疏，即使顶点很多，也可能只能形成较小的匹配。因此，边数为匹配提供了上限，但不保证达到该上限。
2.3 完美匹配与最大匹配
完美匹配是最大匹配中的特殊情形。当匹配能够把所有顶点都恰好覆盖一次时，它不仅是最大匹配，而且是覆盖最完整的一类匹配。
2.3.1 覆盖全部顶点的情形
如果图的顶点总数为偶数，且存在一组匹配边使每个顶点都被恰好匹配一次，那么这组边就是完美匹配。此时匹配规模达到 n/2，已经是理论上的上限。
2.3.2 不存在完美匹配时的处理
若图中不存在完美匹配，研究重点通常转向最大匹配，即寻找能覆盖尽可能多顶点的方案。此时可能会留下若干未匹配顶点，但仍可在结构分析和算法设计中获得最优结果。
2.4 最大匹配的非唯一性
很多图并不会只有一个最大匹配。不同的选边方式可能得到相同大小的最优解，这使得最大匹配问题具有一定的组合多样性。
2.4.1 多个最优解并存
在对称性较强或局部结构相似的图中，常常可以找到多种不同的最大匹配。它们的边集合未必相同，但匹配数完全一致，因此都属于最优解。
2.4.2 结构差异分析
虽然这些最大匹配在规模上相同，但所覆盖的顶点和边的位置可能差别明显。某些解更集中于图的一侧，另一些则更分散，这种差异会影响后续的调度、分配或路径构造。
3 二分图中的最大匹配
二分图是匹配理论中最重要的研究对象之一。由于其顶点天然分成两个互不相交的部分，边只允许跨部连接，因此很多匹配问题都能在二分图中得到更清晰的表述与更高效的算法处理。
3.1 二分图的基本结构
二分图的顶点集可以划分为两个部分，且所有边都连接这两个部分中的不同顶点，部内不允许直接相连。这种结构使得匹配问题更易于转换为“左侧顶点与右侧顶点”的配对任务。
3.2 增广路与二分图匹配
增广路是求解二分图最大匹配的核心工具。它描述了一条交替经过未匹配边与匹配边的路径，通过沿路翻转匹配状态，可以让匹配规模增加。
3.2.1 增广路的定义
增广路是一条从未匹配顶点出发、以未匹配顶点结束，并且边的状态在“未匹配”和“已匹配”之间交替出现的路径。对这条路径进行翻转后，原来未被选中的边会被加入，原来被选中的边会被移除，从而使匹配数增加一。
3.2.2 增广路定理
增广路定理指出：一个匹配是最大匹配，当且仅当图中不存在相对于该匹配的增广路。这个结论把“找不到可以继续扩大的路径”与“已经达到最大规模”严格联系起来，是匹配算法正确性的理论基础。
3.3 Hall定理
Hall定理是二分图匹配中极具代表性的判定工具，尤其适用于判断是否存在覆盖一侧顶点的匹配。它将匹配可行性与集合邻接关系联系起来，形成了简洁而有力的条件。
3.3.1 必要条件
若二分图中某一侧的每个顶点都希望被匹配，那么这侧任意顶点子集的邻居集合大小，必须至少与子集大小相当。否则，子集中的顶点数量多于它们可连接的对侧顶点数，就不可能全部匹配成功。
3.3.2 充分条件
Hall条件不仅是必要的，也同样充分。只要对一侧任意顶点子集都满足“邻居不少于子集大小”，就一定能够找到覆盖该侧全部顶点的匹配。这一结论在组合构造中非常常用。
3.4 二分图最大匹配的典型结论
二分图中，最大匹配与其他经典图论对象之间存在深刻联系，其中最重要的就是最小点覆盖及相关对偶关系。
3.4.1 匹配数与最小点覆盖
在二分图里，最大匹配的边数与最小点覆盖的顶点数相等。这意味着，选出尽量多的互不冲突边，与选出尽量少的顶点去覆盖所有边，在数量上竟然可以达到同一个最优值。
3.4.2 Kőnig定理
Kőnig定理正是上述关系的正式表述。它说明，在二分图中，最大匹配大小等于最小点覆盖大小。这一定理不仅具有理论价值，也为许多计算方法提供了直接依据。
4 算法与实现
最大匹配问题除了理论性质外，更重要的是如何高效求解。针对不同规模和不同类型的图，已经发展出多种算法，其中一些适合入门理解，另一些则面向更复杂的优化任务。
4.1 暴力搜索思路
最直接的想法是枚举所有可能的边集，并检查是否构成匹配，再从中挑出边数最多的一组。虽然这种方法在概念上最容易理解，但组合数量会迅速膨胀，因此只适用于很小的图。
4.2 增广路算法
增广路算法通过不断寻找可提升匹配规模的路径来逐步改进当前解。每发现一条增广路，就沿路径翻转边的状态，使匹配数增加，直到再也找不到可用路径为止。
4.2.1 深度优先搜索实现
深度优先搜索常用于寻找单条增广路。它从未匹配顶点出发，尝试递归地探索可连接的边，并在必要时回溯。实现简单、思路清楚，是许多教材中的标准版本。
4.2.2 广度优先搜索实现
广度优先搜索更适合按层次寻找路径，尤其在需要同时考虑多条候选路径时较为有用。它可以帮助缩短搜索深度，并在一些扩展算法中提高效率。
4.3 匈牙利算法
匈牙利算法是求二分图匹配的经典方法之一，通常用于从一侧顶点出发，寻找并维护一组最大匹配。它与增广路思想密切相关，但在实现上更系统，也更便于处理矩阵化问题。
4.3.1 算法思想
算法核心在于：对每个待匹配顶点，尝试通过已有匹配进行重新安排，如果能找到新的增广路径，就将匹配扩大一条边。不断重复这一过程，最终得到最大匹配。
4.3.2 时间复杂度
在常见实现中，匈牙利算法的时间复杂度通常为多项式级别，适合中等规模二分图。具体复杂度与图的表示方式、搜索策略和实现细节有关，但总体上远优于暴力枚举。
4.4 Kuhn-Munkres算法
Kuhn-Munkres算法，也常被称为 KM 算法，主要用于带权二分图中的最优匹配问题。它在最大匹配的基础上加入权值信息，使目标从“边数最多”扩展为“总权值最优”。
4.4.1 最大权匹配扩展
与普通最大匹配只关心选了多少条边不同，KM 算法考虑每条边的分值，并寻求权值总和最大的匹配方案。这样便能处理更细致的资源分配与成本优化场景。
4.4.2 与最大匹配的关系
如果把所有边权设置为相同常数，那么最大权匹配就会退化为普通的最大匹配问题。也就是说，最大匹配可以看作最大权匹配的一种特殊情形。
4.5 算法正确性证明
匹配算法的正确性通常需要从两个方面说明：一是过程会结束，二是结束时得到的结果确实最优。对增广路类算法而言，这两点都能借助图论定理加以证明。
4.5.1 终止性
由于每找到一条增广路，匹配数都会增加一，而最大匹配大小是有上界的，因此算法不可能无限执行下去。有限次扩展后，过程必然终止。
4.5.2 最优性
当算法终止且再也找不到增广路时，根据增广路定理，当前匹配已经是最大匹配。因此，最终结果不仅是一个可行解，而且已经达到最优规模。
5 相关扩展问题
最大匹配并不是孤立概念，它常常与权值优化、对偶结构以及更一般图类中的匹配问题共同出现。理解这些扩展，有助于把握匹配理论的整体框架。
5.1 最大权匹配
最大权匹配是在匹配基础上加入权重约束后的推广版本。它更接近实际应用，因为现实中的配对往往不仅要“配上”，还要“配得更合适”。
5.1.1 权值模型
权值可以表示收益、相容度、距离的负值或优先级等。不同模型下，同样的匹配边集合可能对应不同的总得分，因此需要先明确权值含义，再进行优化。
5.1.2 优化目标
最大权匹配追求的是总权值最大，而不一定是边数最多。有时少选几条边反而能得到更高的综合收益，这使得它与普通最大匹配在目标上存在明显差异。
5.2 最小点覆盖与最大匹配
最小点覆盖与最大匹配在二分图中形成典型对偶关系。前者从“覆盖边”的角度出发，后者从“选边不冲突”的角度出发，两者共同构成图优化中的经典配对。
5.2.1 对偶关系
最小点覆盖要求选出尽量少的顶点，使图中每条边至少与其中一个顶点相接；最大匹配则要求选出尽量多的互不相交边。二分图中的等值关系说明，这两类问题在结构上高度关联。
5.2.2 计算联系
在实际算法中，往往可以先求最大匹配，再借助相关定理构造最小点覆盖。这样能把一个看似不同的问题转换为同一类求解框架，减少计算复杂度。
5.3 交错路与交错树
交错结构是匹配算法中的重要中间对象。它把匹配边与非匹配边按照特定规则组织起来，便于搜索、证明和构造增广路径。
5.3.1 交错结构的作用
交错路和交错树帮助算法识别哪些边可以继续扩展，哪些路径可能形成增广路。借助这种结构，可以更有系统地探索图中的可行修改方式。
5.3.2 在增广中的应用
在寻找增广路时，算法常沿交错结构展开搜索。由于边的状态交替出现，翻转后即可得到更大的匹配，因此它是增广方法能够运行的关键支撑。
5.4 一般图中的匹配问题
当图不再具有二分结构时，匹配问题会变得更复杂。此时无法直接依赖二分图中的若干经典结论，需要使用更一般的理论与算法。
5.4.1 非二分图情形
在一般图里，可能出现奇环等复杂结构，使得简单的增广路策略不再足够。图的局部结构会显著影响匹配搜索的方式，也提高了求解难度。
5.4.2 Blossom算法概述
Blossom算法是处理一般图最大匹配的著名方法。它通过识别并收缩特殊的奇环结构，把复杂问题转化为更容易处理的形式，最终实现对一般图最大匹配的高效求解。
6 应用场景
最大匹配不仅是抽象理论中的对象，也广泛出现在实际建模中。凡是存在“成对安排”“有限资源分配”或“避免冲突配对”的问题，往往都可以借助匹配思想来分析。
6.1 任务分配问题
在任务分配中，常需要把人员、机器或时间段与工作项进行一一配对。最大匹配可以帮助在约束条件下尽量安排更多任务，减少空闲和冲突。
6.2 学生课程或资源匹配
课程选课、实验室资源分配、座位安排等问题，都常能抽象成匹配模型。通过匹配，可以让学生与课程、请求与资源之间形成尽可能合理的对应关系。
6.3 网络流与调度
在网络调度中，匹配常用于表示某时刻可并行执行的操作集合。它也经常与网络流模型相结合，帮助判断瓶颈位置和并发能力。
6.4 生物信息学中的配对模型
在一些生物信息学问题里，分子、片段或序列之间的配对关系可以抽象为图中的边。匹配模型能帮助描述稳定结合、结构配对或最优对应等问题。
6.5 算法竞赛中的常见题型
最大匹配是算法竞赛中的高频题型之一，常与二分图、增广路、最小点覆盖等知识点联动出现。题目常见形式包括情侣配对、岗位分派、网格覆盖和冲突消除等，考查参赛者对图论建模与算法实现的综合能力。