经由网络流的二分图匹配

形式陈述

设 $G=(L\dot\cup R,E)$ 是有限简单二分图，记 $p=|L|$ 、 $q=|R|$ 、 $n=p+q$ 、 $m=|E|$ 。本页求无权最大基数匹配，并判断能否饱和指定的左侧。输入显式列出左右顶点与有编号的边；孤立顶点也计入 $n$ 。

按最大流模型构造网络 $N$ ，流量须满足各原弧的容量约束和内部顶点的流量守恒：加入源 $s$ 、汇 $t$ ；加入 $s\to\ell$ （ $\ell\in L$ ）、 $\ell\to r$ （ $\ell r\in E$ ）及 $r\to t$ （ $r\in R$ ），所有容量均为 $1$ 。网络有 $n+2$ 个顶点、 $m+n$ 条原弧，构造耗时和空间均为 $O(n+m)$ 。归约结论是

\nu(G)=\max\{|f|:f\text{ 是 }N\text{ 的可行流}\}.

双向对应与整数性

给定匹配 $M$ ，沿每条 $s\to\ell\to r\to t$ （ $\ell r\in M$ ）送一单位。不同匹配边没有公共端点，因此每条源弧和汇弧最多用一次；中间弧也最多用一次。各内部顶点收到多少就送出多少，故得到值为 $|M|$ 的整数可行流。这说明最大流值至少为 $\nu(G)$ 。

反过来，给定整数可行流，全部原弧流量只能为 $0$ 或 $1$ 。左点 $\ell$ 唯一的入弧是 $s\to\ell$ ，容量为 $1$ ；守恒迫使从它流出的中间弧至多有一条流量为 $1$ 。右点唯一的出弧 $r\to t$ 同样保证至多一条中间入弧流量为 $1$ 。所以选取流量为 $1$ 的中间弧便得到匹配。对全部左点的守恒式求和，可知所选边数恰等于源的流出量，也就是 $|f|$ 。

还须证明能找到整数最大流。Ford–Fulkerson 方法从整数零流开始；若当前流整数，则每条正向余量 $c(a)-f(a)$ 和反向余量 $f(a)$ 都是整数。一条正残量路径的瓶颈是正整数，按原弧身份正增、反减后仍为整数可行流。每次流值至少增加 $1$ ，而流值不超过有限的源出容量和，故过程终止。终态无增广路，最大流最小割定理证明它最大。在本网络中正残量都为 $1$ ，每次恰增一单位。将这一整数最大流译回匹配，得到反向不等式，双向归约才闭合。

从终态搜索读出三种证书

设整数最大流对应匹配 $M$ ，大小为 $k$ 。残量源弧恰好通向未匹配左点；在两侧之间，非匹配边可从左向右走，匹配边可从右向左撤销。因终态不可到达 $t$ ，源可达集可写成

U=\{s\}\cup A\cup B,\qquad A\subseteq L,\quad B\subseteq R.

等价地，从全部未匹配左点组成的根集 $Q$ 开始作交替搜索，得到 $A,B$ 。若一个可达左点未匹配，它的所有邻边都能向右走；若它已匹配，其唯一匹配邻居正是搜索进入它之前经过的右点，其余邻边仍能向右走。因此 $N(A)\subseteq B$ 。每个可达右点又必由某个可达左邻居进入，故 $B\subseteq N(A)$ ，于是

N(A)=B.

$B$ 中没有未匹配右点，否则从根到它的路径可以增广。每个 $B$ 中的点都能沿匹配边到达其伙伴；每个 $A\setminus Q$ 中的点也正是沿这样的匹配边进入。因此匹配在 $B$ 与 $A\setminus Q$ 之间给出双射，且 $|Q|=p-k$ ，所以

|A|-|B|=p-k.

当 $k<p$ 时， $A$ 就是Hall 条件的具体违例；它指出哪一群左点缺少候选，而不仅是报告失败。当 $k=p$ 时没有搜索根， $A=B=\varnothing$ ，也没有正缺额。

再令 $C=(L\setminus A)\cup B$ 。任一原边若左端不在 $A$ ，便被左端覆盖；若左端在 $A$ ，其右端属于 $N(A)=B$ ，仍被覆盖。因此 $C$ 是顶点覆盖，且

|C|=p-|A|+|B|=k.

匹配中的 $k$ 条边端点互不相交，任何覆盖至少需要 $k$ 个点，故 $C$ 最小。这给出 Kőnig 定理的构造性证明。同一集合 $U$ 没有中间弧向外跨割，跨割弧只有从 $s$ 到 $L\setminus A$ 及从 $B$ 到 $t$ 的弧，所以割容量也是 $k$ 。

直觉

源弧与汇弧分别给每个左、右顶点一个配额；中间弧上的单位流登记一对端点。残量反向弧记录的是撤销已有配对的权利。一次长增广路可以先腾出别人占用的候选，再把这串调整传到一个空闲右点，因此“没有可直接加入的边”不等于已经最优。

找不到增广路时，搜索仍提供信息：它圈出的左点已经用尽共同邻集。这个可达区域既给出短缺人群，也给出同值割；把区域外的左点与区域内的右点取在一起，就得到同大小覆盖。三份证书描述的是同一次搜索的结果。

上图增广使匹配从三条边增至四条；下图删除 c3 后搜索失败，保留原匹配 M0，并得到三个左点仅有两个邻居的 Hall 障碍 — 上图沿完整增广路加入向右实线边、撤销向左虚线边；下图箭头仅表示残量方向，失败搜索不改变 M0，3→d 也未被访问。删去 c3 后 A={a,b,c}、B={1,2}，覆盖与割的值均为三。

例子与边界

一条需要连续改配的路径

取 $L=\{a,b,c,d\}$ 、 $R=\{1,2,3,4\}$ ，按顺序给七条边编号：

E_+=\{a1,a2,b1,c2,c3,d3,d4\}.

从零流依次沿 $s-a-1-t$ 、 $s-c-2-t$ 、 $s-d-3-t$ 增广，得到 $M_0=\{a1,c2,d3\}$ 。剩下的每条边都碰到已匹配点，所以 $M_0$ 极大，但未匹配的 $b$ 与 $4$ 之间仍有交替路

b\to1\to a\to2\to c\to3\to d\to4.

对应残量路在两端补上 $s,t$ 。沿路撤销 $a1,c2,d3$ ，加入 $b1,a2,c3,d4$ ，得到 $M_+=\{b1,a2,c3,d4\}$ 。每个内部顶点在新流中恰收一单位、送一单位；四条源弧和四条汇弧均流一单位，四条所选中间弧也流一单位，其余三条中间弧流零。网络共十个顶点、十五条原弧，流值为 $4$ ，源割 $\{s\}$ 的容量也为 $4$ ，所以已经最大。

删去一条边以后，失败的原因在哪里

只删去 $c3$ 得到 $G_-$ ，仍有四个左点、四个右点，且没有孤立点。相同的前三次增广仍得到 $M_0$ 。从 $b$ 搜索只能走到 $1,a,2,c$ ；空闲右点 $4$ 虽然存在，却被缺失的 $c3$ 隔在交替可达区域之外。因此

A=\{a,b,c\},\quad B=N(A)=\{1,2\},\quad |A|-|B|=1.

$A$ 中最多匹配两点，此外只剩左点 $d$ ，所以任何匹配最多有三条边； $M_0$ 恰达到这个上界。对应覆盖为 $C=\{d,1,2\}$ ：前四条边 $a1,a2,b1,c2$ 由 $1$ 或 $2$ 覆盖，后两条 $d3,d4$ 由 $d$ 覆盖。

在十四条原弧的网络中， $U=\{s,a,b,c,1,2\}$ 的跨割弧恰是 $s\to d$ 、 $1\to t$ 、 $2\to t$ ，总容量为 $3$ 。流一单位的弧来自 $s-a-1-t$ 、 $s-c-2-t$ 、 $s-d-3-t$ 三条路径，共九条。于是 Hall 缺额 $1$ 、最大匹配 $3$ 、最小覆盖 $3$ 与最小割 $3$ 全部对应同一终态。只检查全体左点会漏掉障碍：这里 $N(L)=R$ ，总量四对四完全够用。

为什么要指定整数流和特定的割

在 $K_{2,2}$ 中，两条源弧和两条汇弧各流 $1$ ，四条中间弧各流 $1/2$ ，得到值为 $2$ 的最大流。若直接选取流量为 $1$ 的中间弧，结果却是空匹配。分数最大流的值仍等于最大匹配值；失败的是这条直接提取规则。前面的整数不变量保证求解器返回适合提取的最优流，而没有断言每个最大流都整数。

全单位网络的任意最小割也不能直接变成覆盖。只有一条边 $a1$ 时，源侧 $W=\{s,a\}$ 的割容量为 $1$ ，已经最小；但按 $(L\setminus(W\cap L))\cup(W\cap R)$ 会得到空集，漏掉 $a1$ 。原因是割切断了中间弧。一般源侧 $W$ 的容量还包含 $E(W\cap L,R\setminus W)$ 中的边数，不能删去这一项。本页使用终态整数匹配的残量可达割，并已证明 $N(A)=B$ ，这才保证没有中间跨割弧。

推论与应用

产生结果与独立检查

设编号可在常数时间取到原边端点，机器字足以保存顶点、边编号和 $n+m$ 。求解器构造邻接表和残量记录后，每次搜索与更新耗时 $O(n+m)$ 。到最优值 $k$ 恰好成功增广 $k$ 次，另有一次失败搜索，所以总时间为 $O((k+1)(n+m))$ ，空间为 $O(n+m)$ 。保留孤立点时不能把每次成本无条件写成 $O(m)$ 。

证书算法把上述产生过程和下面的检查器分开。所有证书先检查长度、编号范围、集合无重复及输入引用；拒绝一份证书不等于证明相反答案。

要确认的结论	证书及接受条件	接受为何可靠
可以饱和左侧	$p$ 个匹配边编号；每条确为输入边，左右端点均不重复	$p$ 条边使用 $p$ 个不同左点，恰好饱和左侧
不能饱和左侧	左点集合 $A$ ；扫描所有边自行算出 $N(A)$ ，确认 $	N(A)
最大匹配值为 $k$	合法匹配 $M$ 和覆盖 $C$ ；逐边检查至少一端在 $C$ ，且 $	M
网络最大流值为 $k$	各原弧的 $0/1$ 流数组与源侧 $U$ ；检查容量、守恒、 $s\in U,t\notin U$ 及 $	f

前三类证书各用 $O(n)$ 个机器字，流割证书用 $O(n+m)$ 个条目；集合也可用位向量保存。各检查器含输入合法性扫描均为 $O(n+m)$ 时间，顶点标记和守恒累加器用 $O(n)$ 辅助空间。检查不需要重跑增广；单位流的等式用精确整数比较。

在 $G_-$ 上， $M_0,C=\{d,1,2\}$ 通过最优性检查， $A=\{a,b,c\}$ 通过否定检查。在 $G_+$ 上复用同一个 $A$ ，扫描会发现边 $c3$ ，算出 $N(A)=\{1,2,3\}$ ，缺额条件失败。这说明检查器必须核对原输入中的全部相关边，不能只相信求解器写下的候选邻集。

算法与模型分支

Hopcroft–Karp 算法直接在交替图中批量处理最短增广路；包含读取孤立点的完整时间界为 $O(n+m\sqrt n)$ ，空间为 $O(n+m)$ 。本页的逐条增广证明仍可用来理解其残量机制，批量阶段数则需要该算法自己的分析。

若把源到某个左点的容量提高，就允许该点承担多次配对，输出已不再是本页的普通匹配。边权需要匈牙利算法或费用流；一般图的奇圈需要开花算法等方法，不能直接套用左右分层网络。二分图匹配也可视为两个划分拟阵的公共独立集，进一步接入拟阵交算法。

参考资料

Mitchel T. Keller、William T. Trotter，Applied Combinatorics，在线现行版，2026-10-03 查阅，§14.2：单位网络、整数流恢复匹配、交替增广与定理 14.7。
MIT OCW，Lecture 11–12: Network Flows and Matching，PDF 首页日期 2022-03-18，托管于 18.200 Spring 2024 课程；PDF 第 7–9 页，定理 2–4。讲义的任意最小割译法使用无限中间容量；本页保留全单位构造，另证终态可达割无中间跨割弧。

形式陈述 ​

双向对应与整数性 ​

从终态搜索读出三种证书 ​

一条需要连续改配的路径 ​

删去一条边以后，失败的原因在哪里 ​

为什么要指定整数流和特定的割 ​

产生结果与独立检查 ​

算法与模型分支 ​

反向链接