经由网络流的二分图匹配

容量在此扮演配额：$s\to \ell$ 的单位容量说“左顶点 $\ell$ 至多结一次对”，$r\to t$ 说右侧同理，而中间的一个单位流恰是一对被选中的端点沿 $s\to \ell \to r\to t$ 的登记路线。最大流问“最多能塞进多少条互不冲突的单位路线”，恰好就是最大匹配问“最多能选多少条互不共享端点的边”。更妙的是残量网络自动管理反悔：一条增广路公理库增广路Augmenting path相对于当前匹配，边在未匹配与已匹配之间交替且两个端点均未匹配的路径。若逆行已用弧，翻译回匹配语言就是交替路——拆掉一条旧配对、换上两条新配对；流的簿记把这类重排全部自动化了。

设 $L=\{1,2\}$，$R=\{a,b\}$，边为 $1a,1b,2a$。贪心可能先配 $1$–$a$，此后 $2$ 只认识已被占用的 $a$，卡在大小 $1$。流的视角下，残量网络中仍有路 $s\to 2\to a\to 1\to b\to t$（其中 $a\to 1$ 是已用弧 $1\to a$ 的反向弧）：增广一次即得匹配 $\{2a,1b\}$，达到最大值 $2$——反向弧完成了“让 $1$ 改配 $b$、把 $a$ 腾给 $2$”的重排。

边界之一：整性不可省略。若允许实值流，网络可以在多条弧上各放二分之一单位，流值最大却对应不到任何匹配；结论成立靠的是整数容量保证存在整数最大流，或算法从零流出发始终以整数增广而保持整性。之二：构造依赖二分结构。一般图中奇圈使同样的编码失效——三角形的分数匹配值可达 $3/2$，而真匹配至多 $1$；一般图的最大匹配需要 Edmonds 的开花算法，而非本归约。另一方面，把 $s\to \ell$ 的容量改为 $c_{\ell }$ 就允许 $\ell$ 被匹配至多 $c_{\ell }$ 次——归约顺带解决度约束子图这类推广，这是流表述的额外红利。

这一归约把匹配接入流的定理库：对 $N$ 应用最大流最小割定理公理库最大流最小割定理Max-flow min-cut theorem网络最大流值等于源汇最小割容量。，把割翻译回图论语言即得二分图的 König 定理公理库Kőnig 二分图定理Kőnig's theorem for bipartite graphs二分图中最大匹配大小等于最小顶点覆盖大小。（最大匹配数等于最小顶点覆盖数），进而可推出 Hall 婚配定理公理库Hall 婚配定理Hall's marriage theorem有限二分图存在饱和一侧的匹配，当且仅当每个该侧顶点子集的邻集至少同样大。的相异代表系判别法。

算法分支由输入结构决定。Hopcroft–Karp 算法公理库Hopcroft–Karp 算法Hopcroft-Karp algorithm按阶段同时增广一族顶点不交的最短增广路，以 O(E√V) 时间求二分图最大匹配。在静态无权二分图上成批处理最短增广路，给出确定性最坏 $O(|E|\sqrt{|V|})$；Edmonds 开花算法公理库Edmonds blossom 算法Edmonds' blossom algorithm · Blossom algorithm通过识别并收缩奇交替环，在一般图中保持增广路存在性并求最大匹配的算法。处理一般无向图中的奇圈，不能由本页的二分流网络直接推出。把匹配看成两个 partition matroid 的公共独立集，则进入更一般的拟阵交算法公理库拟阵交算法Matroid intersection algorithm · Unweighted matroid intersection在两个有限拟阵的交换有向图中寻找最短增广路，以独立性 oracle 构造最大公共独立集并在无路时输出秩和证书。及其 oracle 成本模型。加权二分匹配又离开纯可行流框架，由匈牙利算法公理库匈牙利算法Hungarian algorithm通过对偶标号和增广结构求解赋权二分图完美匹配的算法。或最小费用流处理。