图的交错路径与增广路径 图论中的交错路径与增广路径是匹配理论的核心概念，主要用于解决二分图最大匹配问题（如匈牙利算法）和一般图的匹配问题（如Edmonds开花算法）。下面从基本定义到应用逐步讲解。 1. 基本定义：匹配与交错路径 匹配 ：图的边集的一个子集，其中任意两条边不共享公共顶点。 交错路径 ：一条路径，其边交替属于匹配 \(M\) 和不在匹配中（即属于 \(E \setminus M\)）。 例如，若路径的边依次为 \(e_ 1 \notin M, e_ 2 \in M, e_ 3 \notin M, \dots\)，则称为交错路径。 2. 增广路径的定义与性质 增广路径 ：一条起点和终点均未匹配的交错路径（即路径的两端顶点不在匹配 \(M\) 中）。 关键性质：增广路径的长度必为奇数（因为未匹配的起点和终点分别位于路径的两端）。 例如，在二分图中，增广路径会从一个未匹配点出发，交替经过非匹配边和匹配边，最终到达另一个未匹配点。 3. 增广路径的作用 匹配扩大 ：若存在增广路径 \(P\)，则可通过将 \(P\) 中的匹配边与非匹配边互换，使匹配大小增加1。 操作：将 \(P\) 中所有非匹配边加入匹配，同时移除原匹配边（称为“翻转”操作）。 例如，路径 \(u_ 1 \to u_ 2 \to u_ 3 \to u_ 4\)（其中 \(u_ 1, u_ 4\) 未匹配，边 \((u_ 1,u_ 2) \notin M, (u_ 2,u_ 3) \in M, (u_ 3,u_ 4) \notin M\)），翻转后匹配边变为 \((u_ 1,u_ 2)\) 和 \((u_ 3,u_ 4)\)，匹配大小增加1。 4. Berge定理 定理内容：匹配 \(M\) 是图的最大匹配，当且仅当图中不存在增广路径。 证明思路：若存在增广路径，可通过翻转操作扩大匹配，故 \(M\) 不是最大匹配；反之，若 \(M\) 不是最大匹配，则存在一条增广路径（通过对称差 \(M \oplus M'\) 导出，其中 \(M'\) 是更大的匹配）。 5. 算法应用 二分图最大匹配 ：匈牙利算法通过从每个未匹配点搜索增广路径来逐步扩大匹配。 一般图匹配 ：Edmonds算法通过处理奇环（“花”）来收缩图，确保增广路径的搜索可行。 6. 扩展与变体 权重匹配 ：在带权图中，增广路径的概念推广为“增广环”或“增广树”，用于寻找最大权匹配（如KM算法）。 增量算法 ：动态图中，当边或顶点更新时，可局部搜索增广路径以维护匹配的近似最优性。 通过理解交错路径与增广路径，可以掌握匹配理论的核心机制，并进一步学习高效算法及其证明。