1 基本概念
增广路是图论、匹配理论和网络流中的基础概念，通常指一条能够对当前解进行“增量改进”的路径。它并不只是普通意义上的连通路径，而是要满足某种结构条件，使得沿路径更新后，原有方案变得更优，例如匹配规模增大、流量增加，或者约束满足程度提升。
在不同分支中，增广路的具体形式并不完全一致，但核心思想高度统一：先找到一条可改进的路径，再按特定规则对路径上的状态进行翻转、调整或补充，从而得到新的可行解。
1.1 定义
增广路的定义依赖于所讨论的对象。在图论中，它常与匹配中的交替结构联系在一起；在流网络中，则对应于残量网络中的可增流路径。虽然表述不同，但都强调“可继续改进”的特征。
1.1.1 图论中的增广路
在图论语境下，增广路通常是指与当前结构相配合、能够通过路径操作提升某种目标值的路径。最常见的场景是匹配问题：路径两端是未被当前匹配覆盖的顶点，路径内部边在匹配边与非匹配边之间交替出现。沿该路径翻转边的匹配状态后，匹配边数会增加一条。
1.1.2 匹配中的增广路
在匹配理论中，增广路是以未匹配顶点为端点、并且边在“非匹配—匹配—非匹配”之间交替排列的路径。对路径上的边执行匹配状态反转后，原先未匹配的端点会被纳入匹配，原有匹配结构得到扩充，因此它是寻找最大匹配的关键工具。
1.1.3 流网络中的增广路
在流网络中，增广路是残量网络里从源点到汇点的一条可行路径，路径上每条边都具有正的残量容量。沿该路径增加流量后，整个流值上升。这里的“增广”体现为在不破坏容量约束和流守恒的前提下，把更多流从源点输送到汇点。
1.2 基本性质
增广路的性质集中体现在“能够改进当前解”这一点上。它不是任意路径，而是与现有方案状态紧密相关，必须满足特定的边结构、端点条件或容量条件。
1.2.1 路径的可改进性
一条路径之所以被称为增广路，是因为它能够直接带来目标函数或结构规模的提升。对匹配而言，是增加匹配边数；对网络流而言，是提升总流量；对其他组合优化问题，则可能意味着减少冲突、增加覆盖或改善可行性。
1.2.2 与当前解的关系
增广路总是建立在“当前解”之上。若当前解已经无法继续增广，则说明在该约束体系下已达到局部最优，很多经典定理进一步表明这类局部最优实际上就是全局最优。
1.2.3 增广后结构的变化
沿增广路更新后，结构通常发生局部重排而非整体重构。匹配问题中会改变路径上边的选取状态；流问题中会重新分配部分流量。变化范围有限，但能够带来全局收益，这是增广路方法高效的重要原因。
1.3 相关术语
增广路常与若干概念一同出现，这些术语帮助刻画路径上的边类型、搜索方式以及可操作空间。
1.3.1 交替路
交替路是指路径上的边在两种状态之间交替出现，最常见的是匹配边与非匹配边交替。在匹配理论中，增广路通常就是一种特殊的交替路，但它还要求两端点都是未匹配点。
1.3.2 可增广边
可增广边通常指在当前结构下，能够参与构成增广路并最终带来改进效果的边。它本身未必单独改变结果，但在路径搜索中起到连接和引导作用。
1.3.3 残量网络
残量网络是流算法中的核心辅助结构，用来表示当前流还能如何继续调整。其边的残量容量描述了还能增加多少流，也包括通过反向边撤回既有流量的可能性。
2 图论中的增广路
在图论的许多问题里，增广路主要服务于匹配、覆盖和路径优化等任务。它通过“找到一条能改进现状的路径并进行更新”来推动算法向最优解逼近。
2.1 普通图中的路径增广
普通图中的增广思想并不局限于二分图或流网络，只要问题具有可局部改善的路径结构，就可能使用类似方法。
2.1.1 路径选择规则
选择增广路径时，通常需要满足端点条件和边状态条件。算法往往优先寻找长度较短、结构清晰、便于更新的路径，以减少搜索成本并简化后续维护。
2.1.2 局部改进与全局改进
增广路方法的一个重要特点是，以局部操作实现全局优化。每次只处理一条路径，却能持续提升当前解，反复执行后往往可以达到全局最优或接近最优的结果。
2.2 二分图中的增广路
二分图是增广路应用最经典的场景之一。由于顶点天然分为两个部分，边只能连接不同侧顶点，匹配结构因此更容易组织和分析。
2.2.1 二分图匹配背景
在二分图中，匹配问题常用于表示两类对象之间的一一对应关系，例如任务与人员、学生与课程。增广路是寻找最大匹配的核心方法之一。
2.2.2 从未匹配点出发的增广
二分图匹配中的增广路通常从一个未匹配顶点开始，沿交替边逐步延伸，最终到达另一个未匹配顶点。找到这样的路径后，对路径上的匹配状态进行翻转，就能使匹配规模增加一。
2.2.3 奇偶交替结构
由于二分图的分层特性，增广路径往往呈现出明显的奇偶交替特征。路径上边的状态、层次和方向可以被系统地记录，这也是分层搜索方法能够发挥作用的原因。
2.3 最大匹配中的作用
增广路与最大匹配之间存在紧密联系。它不仅是构造更大匹配的手段，也是判断当前匹配是否已经最优的重要依据。
2.3.1 提升匹配规模
只要存在增广路，就可以通过一次翻转使匹配规模增加。因此，反复寻找增广路并执行更新，是逐步扩张匹配的直接策略。
2.3.2 判定是否存在更大匹配
如果在当前匹配下已经找不到任何增广路，通常意味着无法再扩大匹配规模。于是，是否存在增广路成为判断匹配是否还能继续优化的关键标准。
2.3.3 与最优性条件的联系
很多匹配最优性结论都可归结为“无增广路即最优”。这一关系使得增广路不仅是算法工具，也成为理论证明中的核心中间环节。
3 增广路算法
增广路算法的基本框架非常统一：先发现一条可增广路径，再沿路径更新状态，随后继续搜索，直到再也找不到新的增广路径为止。
3.1 基本思想
这类算法的优势在于结构清晰，易于实现，并且具有很强的适配性，能够应用于匹配、流和若干扩展问题。
3.1.1 发现增广路
算法的第一步是搜索满足条件的路径。搜索对象可能是图中的未匹配点对，也可能是残量网络中的源汇通路。不同问题对应不同的判定规则。
3.1.2 沿路径翻转状态
找到路径后，需要对其进行增广操作。匹配问题中通常是将路径上的非匹配边改为匹配边、匹配边改为非匹配边；流问题中则是沿路径增加流量，并同步更新反向边。
3.1.3 重复增广直到停止
单次增广一般只能得到局部改进，因此算法会重复执行“搜索—更新”过程。直到不存在增广路时，算法终止，输出当前结果。
3.2 常见搜索方法
为了高效寻找增广路，常用多种图搜索技术。不同方法在速度、实现复杂度和路径质量上各有特点。
3.2.1 深度优先搜索
深度优先搜索实现简单，适合在规模不大的问题中快速尝试构造增广路。它容易找到一条可行路径，但不一定保证路径最短。
3.2.2 广度优先搜索
广度优先搜索能够按层次展开，通常更适合寻找最短增广路。对于某些算法来说，这种策略有助于控制总体复杂度并提升稳定性。
3.2.3 分层搜索
分层搜索会先构造层次结构，再在层内寻找可增广通路。这种方式常用于优化增广路搜索效率，尤其适合处理较大规模图结构。
3.3 算法复杂度
增广路算法的效率取决于单次搜索代价、增广次数和路径长度等因素。不同问题中复杂度差异较大。
3.3.1 单次增广代价
一次增广的成本主要包括搜索路径和更新路径状态两部分。若图较稠密或约束较复杂，搜索代价往往成为主要瓶颈。
3.3.2 总体时间复杂度
总体复杂度由“每次增广的成本”与“增广次数”共同决定。若每次都只能增加很少的改进量，则需要较多轮次；若能找到更高质量的路径，则可显著减少总耗时。
3.3.3 性能优化思路
常见优化包括使用更高效的数据结构、优先选择短路径、减少重复搜索以及结合分层策略等。这些改进通常能提升实际运行表现。
4 匹配理论中的增广路
匹配理论是增广路思想最成熟的应用领域之一。这里的核心任务是从现有匹配出发，寻找能够增加匹配边数的路径。
4.1 匹配与交替路
匹配结构本身就具有明显的交替特征，因此增广路的定义和性质都围绕这种结构展开。
4.1.1 匹配边与非匹配边
匹配边是当前方案中已被选中的边，非匹配边则未被纳入。增广路必须在两类边之间交替排列，这样才能保证翻转后仍保持匹配合法性。
4.1.2 交替结构的构造
交替结构通常从未匹配顶点出发，依照“非匹配边—匹配边”交替前进。只要最终抵达另一个未匹配顶点，就形成了可增广路径。
4.2 增广路定理
增广路定理是匹配理论中的经典结论，直接揭示了增广路与最大匹配之间的等价关系。
4.2.1 定理表述
该定理指出：一个匹配是最大匹配，当且仅当图中不存在相对于该匹配的增广路。换言之，能否继续增广，决定了匹配是否还可以扩大。
4.2.2 定理的直观理解
若存在增广路，就能通过翻转使匹配数增加，因此当前匹配显然不是最大；反之，若找不到增广路，说明所有尝试扩展的方向都被阻断，匹配已无法再增长。
4.2.3 定理在证明中的应用
该定理常被用于证明算法正确性。许多匹配算法的证明思路都是：算法终止时没有增广路，于是依据定理可知此时得到的是最大匹配。
4.3 经典应用
增广路在匹配问题中有大量成熟应用，尤其在二分图和一般图的最大匹配求解中发挥核心作用。
4.3.1 二分图最大匹配
二分图最大匹配是最典型的应用场景。通过不断寻找增广路并更新匹配，可以逐步得到最大匹配，算法实现与理论分析都较为成熟。
4.3.2 一般图匹配问题
在一般图中，匹配结构更复杂，增广路的寻找和处理也更具挑战性。不过其核心思想仍然是通过路径改进当前匹配，只是需要额外处理奇圈等特殊结构。
4.3.3 稳定匹配相关扩展
在某些匹配扩展问题中，增广路思想也可作为分析工具。虽然稳定匹配的目标与最大匹配不同，但路径改进、冲突调整等思想在方法论上有相通之处。
5 网络流中的增广路
在网络流中，增广路是指能够继续增加源点到汇点流量的路径。它是经典最大流算法的基础。
5.1 残量网络
残量网络记录了当前流还可以怎样调整，是寻找增广路的直接工作空间。
5.1.1 残量容量
残量容量表示某条边还能承载多少额外流量。若边上已有流量，则其残量容量通常为原容量减去当前流量。
5.1.2 反向边的意义
反向边表示可以撤回或调整先前送出的部分流量。它使算法具备“纠错”能力，允许先前的分配在后续被重新安排。
5.1.3 可行流与残量图
残量图建立在可行流之上，用于描述当前流状态下所有可操作的增量空间。只有在满足容量约束和流守恒的前提下，残量图中的路径才有意义。
5.2 Ford-Fulkerson 方法
Ford-Fulkerson 方法是基于增广路思想的经典最大流求解框架。
5.2.1 增广路径搜索
该方法不断在残量网络中寻找从源点到汇点的路径。只要路径存在，就可以继续增加流量。
5.2.2 流量更新规则
一旦找到增广路径，通常取路径上最小的残量容量作为增广值，然后沿路径统一增加该值，并同步更新反向边的残量。
5.2.3 终止条件
当残量网络中再也找不到源点到汇点的路径时，算法停止。此时得到的流通常已经达到最大值。
5.3 Edmonds-Karp 算法
Edmonds-Karp 算法是 Ford-Fulkerson 方法的一个重要实现版本，采用最短增广路策略提升稳定性。
5.3.1 最短增广路
这里的“最短”通常按边数计算。每次选择边数最少的可增广路径，有助于避免某些低效的反复迂回。
5.3.2 BFS 实现
由于需要按层寻找最短路径，广度优先搜索成为该算法的标准工具。BFS 既简单又能保证路径长度最短。
5.3.3 复杂度分析
与任意选路的增广方法相比，Edmonds-Karp 算法通常具有更好的理论复杂度保证，因此在教学和工程中都很常见。
6 相关理论与证明
增广路不仅是算法手段，也常出现在各类存在性证明和最优性证明中，构成离散优化中的重要桥梁。
6.1 增广路判定
判断是否存在增广路，往往直接决定当前解是否还能改进。
6.1.1 存在性判断
增广路的存在性通常通过图搜索完成。只要能找到满足条件的路径，就说明当前结构尚未最优。
6.1.2 不存在时的最优性
在许多经典问题中，若不存在增广路，就可以推出当前解已经最优。这种“无增广则最优”的性质是相关理论最有力的结论之一。
6.2 经典证明方法
围绕增广路的证明通常较为构造化，也常结合反证思路，形式清晰。
6.2.1 反证法
若假设当前解不是最优，则通常能推出存在一条增广路；若算法已确认不存在增广路，则假设矛盾，从而完成证明。
6.2.2 归纳法
归纳法常用于证明增广次数增加后，某些性质依旧成立。例如匹配规模逐步增大、流保持可行等，都可通过归纳建立。
6.2.3 构造性证明
增广路证明往往具有构造性：不仅说明“存在”，还直接给出“怎么找、怎么改”。这使其特别适合算法正确性论证。
6.3 与其他定理的联系
增广路理论与多个经典定理密切相关，共同构成图论与组合优化的重要基础。
6.3.1 Hall 定理
Hall 定理给出了二分图完美匹配存在性的判据，而增广路方法则常用于实际构造匹配，两者在理论和算法上相互呼应。
6.3.2 最大流最小割定理
最大流最小割定理与增广路密切相关：当不存在增广路时，残量网络中的结构可导出一个最小割，从而连接“无路可增”和“已达最优”两种描述。
6.3.3 Konig 定理
Konig 定理说明二分图中最大匹配与最小点覆盖之间具有深刻联系。增广路算法常被用于求最大匹配，进而间接服务于该定理相关的构造与应用。
7 实际应用
增广路思想不仅存在于理论中，也广泛应用于竞赛、工程和教学场景，是离散优化问题中的常用工具。
7.1 算法竞赛中的应用
在算法竞赛中，增广路是高频知识点，尤其常见于匹配和网络流建模题。
7.1.1 二分图匹配题
这类题目通常要求把两组对象进行尽可能多的一一配对。使用增广路搜索可以直接构造最大匹配，属于标准解法之一。
7.1.2 网络流建模题
许多看似复杂的分配、限制和选择问题，都可以转化为网络流模型。此时增广路算法往往是求解核心。
7.2 工程与资源分配
在工程应用中，增广路方法常用于处理有限资源的优化分配问题。
7.2.1 任务分配
例如将任务分给人员、机器或时间段时，增广路可帮助不断扩展可行分配，使整体匹配更充分。
7.2.2 物流调度
在运输和调度中，增广思想可用于持续调整路径与容量分配，以提高运输效率或减少冲突。
7.2.3 资源匹配
当资源与需求之间存在一一或多对多的约束时，增广路方法可以辅助寻找更优的匹配方案。
7.3 教学与研究
增广路概念结构清楚、证明典型，因此在教学和研究训练中都具有较高价值。
7.3.1 典型例题
增广路题目常用于训练学生识别交替结构、构造路径和理解局部改进思想，是离散数学与算法课程中的经典内容。
7.3.2 证明训练
围绕增广路的证明有助于培养严格的推理能力，尤其适合练习“存在性—构造—最优性”的完整论证链条。
7.3.3 算法实现练习
实现增广路算法可以锻炼图搜索、路径回溯、状态维护和复杂度分析能力，因此常被作为算法入门到进阶阶段的重要练习内容。