初始网络流(最小割)

声明：

1. 本文知识点内容部分参考 oi-wiki 相关内容。

网络流:

网络是指一个特殊的有向图 $G=(V,E)$ 其与一般图不同之处在于有容量和源汇点。

• $E$ 中每条边 $(u,v)$ 都有一个容量（cspacity）记作 $c(u,v)$ 当 $c(u,v)\notin E$ 时，$c(u,v)=0$。
• $V$ 中有两个特殊的点：源点（source）一般称为 $s$ 汇点（sink）称为 $t$ 这里 $s\ne t$。

对于网络 $G=(V,E)$ 流（flow）是一个边集 $E$ 满足以下性质：

1. 容量限制，对于每一条边 $0\le f(u,v)\le c(u,v)$

2. 流量守恒性，除了源汇点外，任意点的净流量是 $0$ 这里定义净流量是 $g(u)={\sum }_{v\in V}f(u,v)-{\sum }_{v\in V}f(v,u)$

3. 对于图 $G=(V,E)$ 我们定义其上的流 $f$ 流量 $|f|$ 为 $s$ 的净流量 $g(s)$。根据流量守恒，还可以得到 $|f|=-g(t)$。

最大流问题（Maximum flow problem）：

我们令 $G=(V,E)$ 是一个有源汇点的有向图，我们希望在 $G=(V,E)$ 上找到一个合适的流量 $f$ 以最大化整个网络的流量 $|f|=g(s)$。这一类问题被称作网络最大流问题（Maximum flow problem）。

对于边 $(u,v)$ 我们定义剩余流量是 $c_f(u,v)$ 即 $c_f(u,v)=c(u,v)-f(u,v)$。

对于整张图 $G=(V,E)$ 我们定义剩余流量（Residual Capacity）为：大于 $0$ 的边和 $V$ 组成的子图叫做 $G$ 的残余网络 （Residual Network），即 G f = ( V , E f ) , E f = { c f ( u , v ) > 0 } G_f = (V,E_f),E_f = \{c_f(u,v) > 0\} Gf​=(V,Ef​),Ef​={cf​(u,v)>0}。

Ford–Fulkerson 增广：

我们定义增广路（Augmenting Path）为 $G_f$ 图中一条从 $s\to t$ 的路径。

对于一条增广路，我们给每一条边 $(u,v)$ 都加上等量的流量，以令整个网络的流量增加，这一过程被称为增广（Augment）。由此，最大流的求解可以被视为若干次增广分别得到的流的叠加。

此外，在 Ford–Fulkerson 增广的过程中，对于每条边 $(u,v)$，我们都新建一条反向边 $(v,u)$。我们约定 $f(u,v)=-f(v,u)$，这一性质可以通过在每次增广时引入退流操作来保证，即 $f(u,v)$ 增加时 $f(v,u)$ 应当减少同等的量。

• 在最大流算法的代码实现中，我们往往需要支持快速访问反向边的操作。
  在邻接矩阵中，这一操作是 trivial 的 $g_{u,v}\leftrightarrow g_{v,u}$。但主流的实现是更加优秀的链式前向星。其中，一个常用的技巧是，我们令边从偶数（通常为 0 或者 2）开始编号，并在加边时总是紧接着加入其反向边使得它们的编号相邻。由此，我们可以令编号为 i 的边和编号为 $i\oplus 1$ 的边始终保持互为反向边的关系。

我们可能察觉到一个违反直觉的情形——反向边的流量 $f(v,u)$ 可能是一个负值。实际上我们可以注意到，在 Ford–Fulkerson 增广的过程中，真正有意义的是剩余容量 $c_f$，而 $f(v,u)$ 的绝对值是无关紧要的，我们可以将反向边流量的减少视为反向边剩余容量 $c_f(v,u)$ 的增加——这也与退流的意义相吻合——反向边剩余容量的增加意味着我们接下来可能通过走反向边来和原先正向的增广抵消，代表一种「反悔」的操作。

退流操作带来的「抵消」效果使得我们无需担心我们按照「错误」的顺序选择了增广路。

容易发现，只要 $G_f$ 上存在增广路，那么对其增广就可以令总流量增加；否则说明总流量已经达到最大可能值，求解过程完成。这就是 Ford–Fulkerson 增广的过程。

最大流最小割定理：

割的定义：

在有源汇点的有向图 $G(V,E)$ 中，存在边集 $E^{\prime }\in E$ 满足 $E^{\prime \prime }=E-E^{\prime }$ 这里 - 是补集的意思。满足 $E^{\prime \prime }$ 中 $s$ 与 $t$ 不联通，则称 $E^{\prime }$ 是原图 $G=(V,E)$ 的一个割。

最小割定义：

最小割即为在所有的 $E^{\prime }$ 中满足 ${\sum }_{(u,v)\in E^{\prime }}c(u,v)$ 的和最小的 $E^{\prime }$。

实际上，Ford–Fulkerson 增广的正确性和最大流最小割定理（The Maxflow-Mincut Theorem）等价。这一定理指出，对于任意网络 $G=(V,E)$，其上的最大流 f 和最小割 { S , T } \{S, T\} {S,T} 总是满足 $|f|=||S,T||$。

• 引理：对于网络 $G=(V,E)$，任取一个流 $f$ 和一个割 { S , T } \{S, T\} {S,T}，总是有 $|f|\le ||S,T||$，其中等号成立当且仅当 $\{(u,v)|u\in S,v\in T\}$ 的所有边均满流，且 $\{(u,v)|u\in T,v\in S\}$ 的所有边均空流。

• 引理：对于有源汇点的图 $G=(V,E)$ 其最大流等于最小割。

  • 假设某一轮增广后，我们得到流 $f$ 使得 $G_f$ 上不存在增广路，即 $G_f$ 上不存在 $s$ 到 $t$ 的路径。此时我们记从 $s$ 出发可以到达的结点组成的点集为 S，并记 $T=V\setminus S$。

  • 显然， { S , T } \{S, T\} {S,T} 是 $G_f$ 的一个割，且 $||S,T||={\sum }_{u\in S}{\sum }_{v\in T}{c}_f(u,v)=0$。由于剩余容量是非负的，这也意味着对于任意 $u\in S,v\in T,(u,v)\in E_f$，均有 $c_f(u,v)=0$。以下我们将这些边分为存在于原图中的边和反向边两种情况讨论：

  • $(u,v)\in E$：此时，$c_f(u,v)=c(u,v)-f(u,v)=0$，因此有 $c(u,v)=f(u,v)$，即 $\{(u,v)\mid u\in S,v\in T\}$ 的所有边均满流；

  • $(v,u)\in E$：此时，$c_f(u,v)=c(u,v)-f(u,v)=0-f(u,v)=f(v,u)=0$，即 $\{(v,u)\mid u\in S,v\in T\}$ 的所有边均空流。

  因此，增广停止后，上述流 $f$ 满足取等条件。根据引理指出的大小关系，自然地，$f$ 是 $G$ 的一个最大流， { S , T } \{S, T\} {S,T} 是 $G$ 的一个最小割。

在整数流量的网络 $G=(V,E)$ 上，平凡地，我们假设每次增广的流量都是整数，则 Ford–Fulkerson 增广的时间复杂度的一个上界是 $O(|E||f|)$，其中 $f$ 是 $G$ 上的最大流。这是因为单轮增广的时间复杂度是 $O(|E|)$，而增广会导致总流量增加，故增广轮数不可能超过 $|f|$。

求解最大流的方法：

Edmonds–Karp 算法

算法思想：

如何在 $G_f$ 中寻找增广路呢？当我们考虑 Ford–Fulkerson 增广的具体实现时，最自然的方案就是使用 BFS。此时，Ford–Fulkerson 增广表现为 Edmonds–Karp 算法。其具体流程如下：

如果在 $G_f$ 上我们可以从 $s$ 出发 BFS 到 $t$，则我们找到了新的增广路。

对于增广路 $p$，我们计算出 $p$ 经过的边的剩余容量的最小值 $\Delta ={\min }_{(u,v)\in p}{c}_f(u,v)$。我们给 $p$ 上的每条边都加上 $\Delta$ 流量，并给它们的反向边都退掉 $\Delta$ 流量，令最大流增加了 $\Delta$。

因为我们修改了流量，所以我们得到新的 $G_f$，我们在新的 $G_f$ 上重复上述过程，直至增广路不存在，则流量不再增加。

以上算法即 Edmonds–Karp 算法。

时间复杂度分析
接下来让我们尝试分析 Edmonds–Karp 算法的时间复杂度。

显然，单轮 BFS 增广的时间复杂度是 $O(|E|+|V|)$。

增广总轮数的上界是 $O(|V||E|)$。将单轮 BFS 增广的复杂度与增广轮数的上界相乘，我们得到 Edmonds–Karp 算法的时间复杂度是 $O(|V||E{|}^2)$。