形式陈述

给定二分图 $G=(L\dot\cup R,E)$$G=(L\dot{\cup }R,E)$，构造网络：加入源 $s$$s$、汇 $t$$t$；对每个 $\ell\in L$$\ell \in L$ 加容量 $1$$1$ 的边 $s\to\ell$$s\to \ell$，对每个 $\ell r\in E$$\ell r\in E$ 加容量 $1$$1$ 的边 $\ell\to r$$\ell \to r$，对每个 $r\in R$$r\in R$ 加容量 $1$$1$ 的边 $r\to t$$r\to t$。

任意匹配 $M$$M$ 产生同值整数流：对 $\ell r\in M$$\ell r\in M$ 的路径 $s\to\ell\to r\to t$$s\to \ell \to r\to t$ 发送 $1$$1$。反之，整数流中值为 $1$$1$ 的中间边形成匹配。由整数容量的最大流整性，

$$ \nu(G)=\text{该网络的最大流值}, $$$$\nu (G)=\text{该网络的最大流值},$$

其中 $\nu(G)$$\nu (G)$ 是最大匹配大小。

直觉

源侧容量保证每个左顶点最多配一次，汇侧容量保证每个右顶点最多配一次；中间单位流恰好代表一对被选择的端点。

例子与边界

仅从任意实值最大流直接挑选正流边可能得到分数分配，不一定是一组匹配；关键是单位整数容量保证存在整数最大流，或算法从零流以整数增广保持整性。构造针对二分图；一般图匹配不能由同一个简单流网络完整解决。

推论与应用

该归约可用任一最大流算法求二分图最大匹配，并把增广路解释为残量网络中的源汇路。结合最大流最小割可证明 Hall 定理和 König 定理；专用 Hopcroft–Karp 算法利用分层增广达到更优复杂度。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，§25.1。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Ch. 7。