最大流与二分图

本文整理了关于最大流，以及其特例二分图最大图匹配的算法、正确性证明、复杂度证明。

笔者撰写本文的目的最初源于Dinic算法在二分图最大匹配上的复杂度证明，但在学习过程中发现网上很多文章要么缺乏证明，要么证明存在不严谨的情况。因此笔者阅读了算法原论文之后，决定系统整理相关的内容。

其中算法用到了BFS和DFS的很多性质，可以参见 图遍历算法

最大流的增广路算法

求解最大流的标准算法是基于定义在残留网络上的增广路算法。

对于算法流程，此处从略，可以详见 Dinic算法详解及实现。

下面主要整理其相关证明，很多重要内容也参考自上文。

性质

性质1：最大流最小割定理

最大流最小割定理是最大流的一个关键性质，即网络中的最大流的流量等价于最小割的容量。

下面将该重要性质拆分为以下几个部分组成。

性质1.1

图的所有割的流量(正向割边的流量与负向割边的流量之差)相等。

证明：由归纳法可得。

令图所有结点的集合为$V$,先定义一个特殊的割集$CUT(s,V/s)$, 其中$s$为源点，再由归纳法可以证明，任意割和上述割集的流量相等。

也即考虑在集合${s}$中不断添加结点$u$, 再由于流量守恒性质，所有割得流量相等，得证。

性质1.2

如果$f$是网络中的一个流，$CUT(S,T)$是任意一个割，那么$f$的值等于割的流量。

证明：由性质1.1简单推得，性质1.1中定义的割集$CUT(s,V/s)$的流量，满足流$f$的定义。

性质1.3

网络中任意流的流量小于网络中任意割的容量。

证明：由性质1.2可以推得。

由性质1.2，网络中任意流的流量等于网络中任意割的流量。

再由割的流量和容量的定义，流量定义为正向割边的流量与负向割边的流量之差，而容量定义为所有割边的最大容量和，显然任意割的流量小于其容量。

因此，网络中任意流的流量等于网络中任意割的流量，小于其容量。

性质1.4

如果网络中存在一个割的流量及其容量相等，那么同时找到了最大流和最小割。

证明：利用性质1.3.

因为网络中任意流的流量等于网络中任意割的流量，因为性质1.3的任意性，其相等的情况，只能是最大流和最小割。

正确性证明

寻找增广路，等价于寻找最大流，是算法的正确性保证。该证明分为两方面。

• 一方面，需证明：若找到了最大流，则无增广路。
• 另一方面，需证明：若找到了最大流，则无增广路。

性质2.1

若找到了最大流，则无增广路。

证明：若存在增广路，则沿着增广路增广，由于增广的性质决定了流量必然增加，与最大流矛盾。

性质2.2

若无增广路，则找到了最大流。

该部分证明的关键在于利用最大流最小割定理，也即利用性质1.4。

想要利用性质1.4，必须构造出一个流量与容量相等的割。由于无增广路，这样的割是天然存在的。

无增广路，说明残留网络中不存在一条从源点$s$到汇点$t$的路径，因此构造源点$s$沿着残留网络所能触及的最大点集$S$, 该点集一定不包含汇点$t$, 其补集为$T$,由此定义了割$CUT(S,T)$,满足割的定义。

又因为$S$是源点$s$沿着残留网络所能触及的最大点集，因此$CUT(S,T)$中的边，在残留网络中该边为反向边。

反之，该边存在且为前向边，则与最大点集的定义矛盾，因为沿着该边延展，可以扩大点集$S$.

而根据残留网络的定义，残留网络中的反向边即为网络中的满流，也即流量和容量相等的边。

因此，上述构造的割满足其流量和容量相等，再有性质1.4，找到了这样的割，就找到了最大流。

时间复杂度

基础的基于寻找增广路思想的最大流算法也称为Ford-Fulkerson算法，较为简单实际不使用，因此忽略其复杂度。

最短增广路算法

正确性证明

最短增广路算法基于多路增广的思想。

该算法的关键是不仅仅只寻找增广路，而是寻找最短增广路，这个改动的正确性也是显然的。因为当最短增广路不存在时，说明找不到增广路了，说明找到了最大流。

而由于BFS与最短路径的关系，可以详见图的遍历算法中的BFS部分，寻找最短增广路也即在BFS层次图上寻找增广路。

因此，可以使用BFS寻找最短增广路。

算法不断执行如下两个流程：

• 利用BFS构建层次图
• 利用BFS在层次图中寻找最短增广路直到无增广路为止

上述两个流程合起来称为算法的一个阶段,，反复执行多次阶段直到层次图无法构建，说明找不到最短增广路了。

时间复杂度

该算法的时间复杂度为$O(VE^2)$

性质3.1

将源点到汇点的最短路径上的一条边$u \rightarrow v$反向为$v \rightarrow u$，只会增加源点到汇点的最短路径长度。

证明：只需证明所有包含边$v \rightarrow u$的路径，都不是最短路径。

设原先最短路径长度为$d$,若路径$p$包含边$v \rightarrow u$,则其最短路径长度至少

$d(s \rightarrow v)+d(u \rightarrow v) +d(v \rightarrow t) \ge d(s \rightarrow t) + 1 \gt d(s \rightarrow t)$

因此，最短路径长度在增广后非减。

性质3.2

每个BFS增广阶段过后，汇点层级增加。

证明：根据性质3.1.

在每一次增广后，所有最短路径长度为$d$的增广路都被阻塞，说明下一轮找到的最短增广路长度至少为$d+1$.

性质3.3

在寻找最大流的过程中，最多仅存在$O(V)$个阶段

证明：根据性质3.2.

由于最短路径长度最长为$O(V)$，也即经过网络中的每一个结点，因此汇点层级最多为$O(V)$.

又每个阶段过后汇点层级增加，因此最多仅存在$O(V)$个阶段。

性质3.4

构建层次图的总时间复杂度为$O(VE)$。

证明：每次构建层次图采用BFS构建，复杂度为$O(E)$,又每个阶段仅构建一次层次图，总共不超过$O(V)$个阶段，因此总复杂度为$O(VE)$。

性质3.5

每个阶段最多仅有$O(E)$条增广路。

证明：根据增广的阻塞性质。

每次在层次图中增广，都会阻塞至少一条边，而这条边显然不能再成为该阶段的最短路径了（根据性质3.1），当$O(E)$条边全部被阻塞的时候，再也找不到增广路了。

因此，每个阶段最多仅有$O(E)$条增广路。

性质3.6

每次使用BFS增广，复杂度为$O(E)$.

每次增广，涉及两个部分的操作：

• 寻找增广路径
• 更改流量

寻找增广路径使用BFS算法，复杂度为$O(E)$.

更改流量，由于路径最多涉及$O(V)$个结点，故最多涉及$O(V)$条边，该操作复杂度为$O(V)$.

综上，每次BFS增广的复杂度为$O(E)$.

性质3.7：时间复杂度

最短增广路算法的时间复杂度为$O(VE^2)$.

证明：根据性质3.-3.6。

算法的复杂度来自两个部分：

• 构建层次图
• 增广

共有$O(V)$个阶段，每个阶段不超过$O(E)$次增广，每次增广的代价为$O(E)$

因此，增广部分的时间复杂度为$O(VE^2)$.

而性质3.4中已经证明，构建层次图的复杂度为$O(VE)$.

综上，最短增广路算法的时间复杂度为$O(VE^2)$.

Dinic算法

正确性证明

Dinic算法才是本文的关键，也是最大流较为普通的算法，有了上面的铺垫，该算法的理解将非常简单。

Dinic算法，不使用BFS增广，而使用DFS增广。

因为当层次图使用BFS构建好之后，只要沿着层次图走，就能找到最短路。

上面的算法仍然使用BFS寻找最短增广路，是为了实现方便（可以将构建层次图和寻找增广路都使用BFS），但却非最好的算法，Dinic将寻找增广路用DFS算法寻找，可以降低原先的时间复杂度。

Dinic算法，本质为在层次图中搜索所有的路径，搜索结束也即DFS结束，则当前结点所有的最短路都找到了。

从而，Dinic算法中的一次DFS相当于最短增广路算法中的多次BFS增广。

时间复杂度

Dinic算法中层次图的构建部分没有改变，复杂度也没有改变。

Dinic算法降低了增广部分的复杂度，而每次增广，涉及两个部分的操作：

• 寻找增广路径
• 更改流量

由于Dinic算法每个阶段仅涉及一次DFS寻找所有的增广路径，每次DFS的代价为$O(E)$，共$O(V)$个阶段，因此寻找增广路径的总代价为$O(VE)$.

而由于每个阶段最多只有$O(E)$条增广路(性质3.5)，每条路径最多涉及$O(V)$次流量修改（与性质3.6中证明相同），因此每个阶段更改流量部分的总代价为$O(VE)$，$O(V)$个阶段的总修改代价为$O(V^2E)$.

综上，Dinic算法的复杂度为$O(V^2E)$.

二分图的匈牙利算法

二分图匹配，也称为指派问题，最简单而经典的算法为匈牙利算法。

大多数匈牙利算法的介绍都不是由网络流开始的，但由网络流的角度理解，对于算法的正确性证明、复杂度证明、算法改进都将有更本质的了解。

匈牙利算法中不断为一个未被指派的结点寻找交错路，实际上和网络流算法中寻找增广路是一致的。

性质

性质4.1：二分图匹配与最大流的关系

设二分图由$X$和$Y$两个点集以及两个点集之间的连边构成，构建一个超级源点$s$连接$X$中的所有结点。再构建一个超级汇点$t$被$Y$中所有结点连接，所有边的容量设置为1，则易证：求解$s$到$t$的最大流等价于求解二分图的最大匹配。二分图的交错路等价于网络流的增广路。证明较为显然，从略，但该关系是后文所有证明的基础，非常重要。

性质4.2

对于从结点$u$开始的增广路($u \in X$)，边$s-u$最多仅被增广1次。

证明：由于边的容量为1，故边增广后必然被阻塞，且寻找增广路必须以$s$为起点，而被阻塞之后该边便不可能再被第二次增广。

性质4.3

每次增广都使得指派数目增加1，也即每次增广都产生了新的指派。

证明: 由于增广的容量为1，且增广路即为交错路，所以指派数目增加1.

性质4.4

对于从结点$u$开始的增广路，若在某次搜索中发现其不存在以其开始的增广路，则后续无论如何对网络进行增广调整，都不存在以其开始的增广路。

证明：该性质以其证明是保证匈牙利算法正确性的关键，证明用反证法。

假设在某次沿着增广路$x-y-…-z$的增广之后，存在从结点$u$开始的新的增广路$p=u-…-v$.

根据性质4.3，新增的指派为$x$与$y$的配对。

首先，$p$中必须包含结点$x$,否则$p$中的所有属于$X$集合中的结点都与新的调整无关，与$p$是“新”的增广路矛盾。

其次，对于$p$,有两种情况：

• 情况1，$p$中不包含结点$y$
• 情况2，$p$中包含结点$y$

对于情况1，由于新的指派为$x$与$y$的配对，因此若$p$中不包含$y$，则因为$x$在集合$Y$中仅与$y$连接，$p$中也不可能包含$x$，显然矛盾。

对于情况2，也即$p=u-…-x-y-…-v$,构造路径$u-…-y-…-v$,则这是一个不包含$x$的从$u$开始的增广路，这条增广路肯定在之前的搜索就被发现了，同样是矛盾的。

下面开始的其他性质将在Dinic算法再二分图中的应用，扮演着重要的作用。如果仅关注匈牙利算法，可以暂时忽略这一部分性质。

性质4.5

二分图中的增广路互无交集。

证明：根据性质4.2，每次增广后都导致增广路上的边被阻塞而不能再使用，则寻找到的增广路无交集。

性质4.6

给定二分图的任意一个非最大匹配$M$及最大匹配$M^{\star}$,$M^{\star} \bigoplus M$的结点和边构成的集合由环和路径成。

证明：该集合中的每个结点最多由$M^{\star}$和$M$分别贡献1的度数，因此其最大度数不超过2。

而结点最大度数不超过2的集合，只能由环和路径组成。

性质4.7

$ M^{\star} \bigoplus M $中的路径构成了 $M^{\star}-M$条不相交的交替路。

证明：由于$M$非最大匹配，所以$M<M^{\star}$,考虑集合$M^{\star} \bigoplus M$的构成：环与路径

由于二分图匹配的性质，该集合中的路径和环的结点交替由两个集合组成，因此环只能为偶环，因此环不能贡献$M$与$M^{\star}$之间的数量差距。因此该差距由路径构成，且该路径由不属于$M$中的结点出发，结束于不属于$M$中的结点，因此每条路径均各不相交，且每条路径贡献了1的数量差距，因此共有$M^{\star}-M$条不相交的交替路。

性质4.8

给定二分图的任意一个非最大匹配$M$及任意最大匹配$M^{\star}$,从$M$出发寻找的最短增广路长度$l\le \frac{V}{M^{\star}-M}$

证明：根据增广路的性质以及鸽巢原理。

根据性质4.7，可以找到所有由$M$出发到$M^{\star}$的$M^{\star}-M$条不相交的交替路，最短增广路一定属于其中的某一条。

再由反证法（或鸽巢原理），假设$M$出发寻找的最短增广路长度$l\gt \frac{V}{M^{\star}-M}$，则所有的$M^{\star}-M$条路径的集合的总长度大于总结点数$V$，但又已知$M^{*} \le V$,则推出矛盾。

正确性证明

对于形如二分图的最大流，从每个结点$u$开始的交错路的搜索仅需进行一次，因此算法正确性得证。

证明：由上面性质，易得。

分为两种情况：

• 情况1，从$u$开始的搜索找到了交错路/增广路
• 情况2，从$u$开始的搜索没有找到交错路/增广路

对于情况1，根据性质4.2，无需对结点$u$进行再次搜索。

对于情况2，根据性质4.4，也无需对结点$u$进行再次搜索。

时间复杂度

与网络流算法相同，匈牙利算法的时间复杂度由每次增广中的两部分组成：

• 寻找增广路
• 指派，相当于网络流中的流量修改

在增广路的寻找上，采用DFS或者BFS，复杂度为$O(E)$

而在指派上面，由于每条路径最多包含$O(V)$个结点，且流量修改仅需要1次，复杂度为$O(V)$.

又最多进行$O(V)$次增广，总复杂度为$O(VE)$.

Dinic算法在二分图中的应用

比其匈牙利算法，更优的算法是将Dinic算法使用在二分图上面，下面主要证明其更低的时间复杂度。

时间复杂度

性质5.1

Dinic算法在二分图上，每个阶段的时间复杂度为$O(E)$.

证明：由于Dinic算法的每个阶段中，复杂度来自于

• BFS构建层次图
• DFS寻找增广路
• 指派

BFS和DFS的代价为$O(E)$，下面考虑指派的代价：

由于该阶段中寻找的所有的增广路均不相交（类似性质4.7的推导），因此指派的代价也为$O(E)$.

综上，每个阶段的时间复杂度均为$O(E)$.

性质5.2

Dinic算法应用在二分图最大匹配问题上的时间复杂度为$O(E \sqrt{V})$.

证明：考虑Dinic算法的执行过程，将其所有$O(V)$个阶段分为两个部分。

• 第一个部分，前$O(\sqrt{V})$个阶段的增广
• 第二个部分，后面阶段的增广

对于第一个部分，每次找到的增广路长度不超过为$O(\sqrt{V})$,因此在这个部分中：时间复杂度为前$O(\sqrt{V})$个阶段每阶段$O(E)$的代价，总复杂度$O(E\sqrt{V})$。

对于第二个部分，根据性质4.8，此刻出发寻找的增广路路径长度$l$满足$\sqrt{V} \le l\le \frac{V}{M^{*}-M}$,

因此，$M^{*}-M \le \sqrt{V}$, 因此后面的阶段最多仅有$\sqrt{V}$条增光路。而每个阶段至少找到一条增广路，因此至多仅有$\sqrt{V}$个阶段。

因此，实际上所有的阶段数的更紧的上界不是$O(V)$,而是$O(\sqrt{V})$.

而根据性质5.1，每个阶段的复杂度为$O(E)$。

综上，Dinic算法应用在二分图最大匹配问题上的时间复杂度为$O(E \sqrt{V})$.

二分图的其他性质

性质

性质6.1：最小点覆盖

二分图的最大匹配数等于最小点覆盖数。

证明：给定二分图$X-Y$的最大匹配$M$，通过构造得出一个点覆盖，并且证明其为最小点覆盖

构造方法如下：

从$Y$中所有的未匹配结点出发，尝试走出一条从未匹配结点开始，以匹配结点结束的交替路。

将走过的$X$和未走过的$Y$中的所有结点加入集合$S$，则$S$为一个点覆盖。

下面分为几个部分证明：

性质6.1.1

$S$的大小与$M$的大小相同。

证明: $S$中属于$X$的结点属于匹配边，而$S$中属于$Y$的结点也因为连接的所有边都为匹配边而未被走过。因此$S$中的结点和匹配边一一对应，也即正好得到了$S$中的结点都属于匹配边的一个端点，因此$S$的大小与$M$的大小相同。

性质6.1.2

$S$能覆盖所有边。

证明：分为两种情况考虑图中的边：匹配边和非匹配边

对于匹配边，由于$S$为其端点的集合，$S$显然可以覆盖所有的匹配边。

对于非匹配边，再分为两种情况：

• 情况1，该非匹配边的右端点$v$，存在与某一个匹配边相连
• 情况2，该非匹配边的右端点$v$，不存在与任何一个匹配边相连

对于情况1，则$v$未被走过，因此属于集合$S$,则该边被覆盖。

对于情况2，考虑该非匹配边的左端点$u$,则$u$一定为匹配点，否则将$u-v$加入$M$可以获得更大的二分图匹配。

已知$u$一定为匹配点，则按照构造过程,$u$会被走过，因此这种情况下该边仍然被覆盖。

综上，$S$能覆盖图中的所有边。

性质6.1.3

点覆盖的最小规模为$M$。

证明：一个点覆盖至少覆盖所有匹配边，也即至少规模为$M$.

性质6.1.4

二分图最小点覆盖=最大匹配

综合上述性质，得到：$S$是一个规模最小的点覆盖，也即最小点覆盖。

推论：该性质可以推广到点权覆盖，二分图最小点权覆盖=最大流=最小割

性质6.2：最小路径覆盖

二分图的最小路径覆盖等于$V-M$,$M$为最大匹配。

证明：先考虑无匹配的情况，此时需要$V$个孤立点（路径）来覆盖。

考虑增加二分图的一个匹配，则将减小路径覆盖的数量1，因此最大匹配与最小路径覆盖同时取到。

特殊地，当不是二分图的情况下，如DAG也可以转化为二分图求解最小路径覆盖问题。

转化的方法如下：对于每个DAG中的每个结点，将其拆分为两个结点，分为位与二分图的左部和右部；对于DAG中的每条边，将二分图左部与起始端点对应的结点指向右部与结束端点对应的结点。易证明：两个问题的等价性。

具体地说，二分图的最大匹配指明了DAG的最小路径覆盖中，存在后继结点的数目，而又不存在后继结点的结点数目（路径末尾结点）表明了最小路径覆盖数，故该DAG的最小路径覆盖数为DAG的结点数目减去最大匹配数。

性质6.3：最小边覆盖

二分图的最小边覆盖等于$V-M$,$M$为最大匹配。

证明：由性质6.2易得，因为二分图的最小边覆盖和最小路径覆盖等价。

性质6.4：最大独立集

性质6.4.1

任意图的最大独立集+最小点覆盖=总结点

证明：由于点覆盖要求满足每一条边的两个端点不能都不在集合中，而独立集要求每一条边的两个端点不能都在集合中。因此两者本质为互补的关系。

性质6.4.2

二分图的最大独立集大小=总结点数-最大匹配

证明：由性质6.1，二分图的最小点覆盖可得。

推论：该性质也有带权版本，二分图的最大带权独立集=总点权和-最大流

性质6.5：最大团

性质6.5.1

任意图的最大团等于补图的最大独立集。

证明：较为简单，独立集中的结点两两不相邻，故在补图中两两相邻，也即构成团。

性质6.5.2

二分图的最大团规模=结点数-最大匹配

证明：同样由性质6.1直接可得。