matching · augmenting path · Hall / König / Tutte

匹配：增广路与三条配对定理

一个 matching（匹配）M 是一组边，两两不共端点——每个顶点至多被一条匹配边覆盖。把它做到最大，靠的是一个出奇简洁的判据：augmenting path（增广路）。本页在二部图上单步跑增广，翻转一条交替路就让 |M| 加一，直到再也找不到增广路——那一刻的匹配即最大匹配。围绕它有三条经典定理：Hall 给出左部可被完全匹配的充要条件，König 把最大匹配与最小点覆盖钉成相等，Tutte 把完美匹配推广到一般图。

交替路与增广路。 给定当前匹配 M，一条 alternating path（交替路） 是边在「非匹配边 / 匹配边」之间交替出现的路。若一条交替路的两个端点都是未匹配点，它就是一条 augmenting path。沿增广路把每条边的「匹配 / 非匹配」身份整体翻转：原本路上有 k 条匹配边、k+1 条非匹配边，翻转后变成 k+1 条匹配边——|M| 净增 1，且仍是合法匹配。Berge 定理： M 是最大匹配 ⟺ 不存在关于 M 的增广路。

这里跑的就是匈牙利算法 (Hungarian / Kuhn)。 逐个考察左部未匹配点，从它出发用 DFS 找一条增广路（沿非匹配边走到右点，若右点已被匹配，就递归尝试为占用它的左点另寻出路）；找到就翻转，匹配大小加一。每个左点最多触发一次成功增广，单次增广 $O(|V|+|E|)$ ，总复杂度 $O(|V|\cdot |E|)$ 。

Hall 婚配定理 (Hall's marriage theorem)。 设二部图左部为 L、右部为 R，对顶点集 S 记 N(S) 为其全部邻居之并。则存在饱和 L 的匹配（每个左点都被匹配）⟺ 对每个子集 $S \subseteq L$ 都有 $|N(S)| \ge |S|$ 。直觉：若某组左点 S 的可选对象 N(S) 比自己还少，它们必然无法全部被匹配——这组 S 就是匹配饱和左部的「瓶颈」。切到「Hall 条件失败」样本，页面会标出违例的 S 与 N(S)。

König 定理（二部图）。 一个 vertex cover（点覆盖） 是一组顶点，使每条边至少有一个端点在其中。König 断言：在二部图中，最大匹配的边数 = 最小点覆盖的顶点数。匹配是「尽量多挑互不冲突的边」，点覆盖是「尽量少挑顶点盯住所有边」，二者在二部图里恰好对偶相等（它是线性规划对偶在 0/1 情形下的整数版，也是最大流最小割的特例）。点开「显示最小点覆盖」按钮，可见覆盖点数恰等于 |M|。一般图中只有弱对偶 $最大匹配 \le 最小点覆盖$ ，不一定取等（如三角形：最大匹配 1，最小点覆盖 2）。

Tutte 定理（一般图）。 把「完美匹配」推广到任意图：记 o(H) 为图 H 中奇数阶连通分支（顶点数为奇数的分支）的个数。则**G 有完美匹配 ⟺ 对任意顶点集 $U \subseteq V$ 都有 $o(G - U) \le |U|$ **。直觉：删掉 U 后每个奇分支至少要有一个点匹配到 U，而它们只能匹配进 U 内，于是奇分支数不能超过 |U|。Tutte 把 Hall 从二部的「单侧饱和」一举推广到一般图的「全体配对」；König 的等式则不再成立，需换成 Gallai–Edmonds 结构与带花树 (blossom) 算法。