← 线性规划网络流 · 最大流、最小割与建模归约 / 二分图最大匹配 待审核 9 / 13
二分图匹配 · König / Hall

二分图最大匹配

把任务分给员工、把面试者配给岗位、把课程排进教室——这些问题都长一个样：左边一组、右边一组，只在允许的「左-右」对之间连一条线，要求最多能配成几对，且每个元素至多用一次（一个员工只做一件任务、一个岗位只录一人）。这就是二分图最大匹配 (maximum bipartite matching)，也是网络流最优雅、最实用的应用之一。

它的精彩之处在于：不需要为它发明新算法——把二分图建成一张单位容量的流网络，前面几页学过的最大流原封不动跑下去，流值就是最大匹配数；残量网络里的增广路 (augmenting path) 恰好就是教科书里匈牙利算法的「交替路 / 取反已匹配边」。本页建立这座桥，再单步跑一遍。

1 · 建模：二分图 → 单位容量网络

一张二分图 (bipartite graph) 的点能分成不相交的两部 L 与 R，所有边都横跨两部、部内无边。一个匹配 (matching) M 是一组两两不共端点的边；最大匹配就是边数最多的那个 M。问题本身没有「流」的影子，关键的一步是给它套上源汇、把「至多用一次」翻译成容量 1。

建网三步（单位容量网络）：

  • 加一个超级源 super source s，从 s 向每个左点连一条 cap = 1 的边——限定每个左点至多被选一次;
  • 每条允许的对 (l, r) 连一条 l→rl\to r、cap = 1 的边；
  • 加一个超级汇 super sink t，从每个右点向 t 连一条 cap = 1 的边——限定每个右点至多被选一次。

最大流 = 最大匹配。 在这张网里所有容量都是整数，由整数流定理 (integrality)，最大流必有一个整数解；每条边容量为 1，所以每条 l→rl\to r 边的流量只能是 0 或 1——flow = 1 的那些 l→rl\to r 边正好是一个匹配。源边容量 1 保证每个左点至多发出 1 单位、汇边容量 1 保证每个右点至多接收 1 单位，即「两两不共端点」。于是流值 |f| = 匹配大小 |M|，最大流就是最大匹配。

那么残量网络里的增广路在匹配语言里是什么？一条 s→l1→r1→⋯→ts \to l_1 \to r_1 \to \dots \to t 的增广路，凡是走正向边 l→rl\to r 就是「新建一对」，凡是走反向边 r→lr\to l 就是「拆掉一对已匹配的 (l, r)，把 r 让给别人」。正向、反向交替出现——这正是匈牙利算法里的交替增广路 (alternating augmenting path)：沿它把「已匹配 / 未匹配」全部取反，匹配数恰好 +1。网络流的反向边，就是匈牙利算法「撤销已有配对、给 r 改配对象」的那一步。

2 · 单步运行：求最大匹配

左部 x1 x2 x3、右部 y1 y2 y3，允许的对见下方圆角标签。用 bipartiteNet(left, right, pairs) 建成单位容量网，跑 maxflowSteps(net, 'bfs')（BFS 找最短增广路，即 Edmonds-Karp）。每点「下一步」找一条增广路并推流；每凑成一对，对应的 l→rl\to r 边与左右名牌都会变绿。留意某一步可能走反向边（橙色虚线）——那就是「拆一对、改配」的撤销操作。这张图的最大匹配是 3（完美匹配）。

读出匹配。 跑到底后，用 matchingFromFlow(net, flow, left, right) 把 flow = 1 的 l→rl\to r 边筛出来，就是最终匹配 M。本例得到大小为 3 的完美匹配：左右六个点全部配上，无人落单。

为什么用 BFS (Edmonds-Karp)? 任何最大流算法都能得到正确的最大匹配，区别只在快慢。BFS 每次找最短增广路，在单位容量网上正是把增广路按长度递增地扫一遍，这恰好是下面要说的 Hopcroft-Karp 思路的雏形。

3 · 两条定理：König 与 Hall

把匹配建成流网络，顺带白拿了网络流的全部定理。其中两条在二分图上格外优雅——它们分别回答「最大匹配等于什么」与「什么时候能配满左部」。

König 定理：二分图里 最大匹配 = 最小点覆盖。 一个点覆盖 (vertex cover) 是一组点，使每条边都至少有一个端点被选中；最小点覆盖就是这样的最小点集。König 定理说，在二分图上，最大匹配的边数 = 最小点覆盖的点数。

它就是 max-flow min-cut 的影子。 在我们这张单位容量网上，最小割的最大流 = 最小割给出：最大匹配 = 最小割容量。而这张网的一个最小割，挑出的恰好是覆盖所有 l→rl\to r 边的一组源边 / 汇边——对应到原二分图，就是一组最小点覆盖（被割掉的源边 s→ls\to l 选中左点 l、被割掉的汇边 r→tr\to t 选中右点 r）。最小割 ↔ 最小点覆盖,König 定理因此是 max-flow min-cut 在单位容量二分图网上的一个具体体现。

Hall 婚配定理 (Hall's theorem): 左部 L 存在完美匹配（每个左点都被配上）当且仅当——对任意左点子集 X⊆LX \subseteq L，其邻居集合满足 ∣N(X)∣≥∣X∣|N(X)| \ge |X|。其中 N(X) 是 X 里所有点能连到的右点之并。

直觉： 若某 k 个左点加起来只够得着不到 k 个右点(|N(X)| < |X|)，这 k 个左点要抢的右点不够分，鸽笼原理下必有人落单，完美匹配无从谈起；Hall 定理说，只要不存在这样的「拥挤子集」，完美匹配就一定存在。这也叫「婚配定理」：把左部看成待嫁者、右部看成候选对象，只要每一群待嫁者的可选对象总数都不少于这群人本身，就能让人人成婚。

复杂度。 通用最大流（如 Edmonds-Karp）在匹配网上是 O(V⋅E)O(V\cdot E)。但这张网每条边容量都是 1，属于单位容量网络——在它上面跑 Dinic，相位数被压到 O(V)O(\sqrt V)，每相位 O(E)O(E)，总复杂度 O(E⋅V)O(E\cdot \sqrt V)。这正是二分图匹配的专用算法 Hopcroft-Karp 的复杂度：Hopcroft-Karp 本质就是「单位容量网络上的 Dinic」——每个相位用 BFS 分层、再一次性沿所有最短增广路推流。

4 · 应用：指派 · 稳定匹配

最大匹配只问「能配几对」。现实里常常每对配上还有代价或收益，要的不是配得多、而是配得最划算——这就升级成了指派问题 (assignment problem)。

带权指派 → 最小费用流。 在同样的单位容量网上，给每条 l→rl\to r 边附一个 cost（做这对配对的代价），求一个完美匹配使总代价最小，就是把问题交给最小费用最大流 (min-cost max-flow)：先用源汇容量逼出最大流（配满），再让 MCMF 在所有最大匹配里挑总 cost 最小的那个。经典的匈牙利算法 (Kuhn–Munkres) 正是这个问题的另一种解法。

与稳定匹配的区别。 本页的最大 / 带权匹配，是站在「全局」找总数最多 / 总代价最小的配对，由一个中央算法统一最优化。另一类著名问题——稳定匹配 (stable matching)，关心的不是全局总量，而是双方各有偏好排序时，有没有一对「彼此都更想要对方却没被配上」的不稳定对，Gale–Shapley 算法保证给出稳定解。两者目标不同、算法不同，不要混为一谈。本站另有 稳定匹配 (stable matching) 系列 专讲后者，可对照阅读。