【笔记】网络流基本概念

---

最大流相关概念

流网络：由一些点和有向边组成的可以有环的图，记作 $G=(\text{V},\text{E})$，其中 $\text{V}$ 是点集，$\text{E}$ 是边集。定义 $n=|\text{V}|,m=|\text{E}|$，在本篇文章中使用。

源点：在一个流网络中，入度为 $0$ 且能流出的流量为 $\infty$ 的点。一般用斜体大写字母 $S$ 表示。

汇点：在一个流网络中，出度为 $0$ 且能流入的流量为 $\infty$ 的点。一般用斜体大写字母 $T$ 表示。

流网络里的每一条边都有一个属性，称为该边的 容量（该边每秒最多能流过的单位流量），一般用 $c(u,v)$ 表示。 { u ∈ V , v ∈ V , ( u , v ) ∈ E } \{u\in \text V,v\in \text V,(u,v)\in \text E\} {u∈V,v∈V,(u,v)∈E}

注意：

1. 在讨论流网络时为了简化讨论，默认不存在反向边，因为就算存在反向边，我们也可以将反向边中间加上一个点，这样就从两个点之间的双向边变成了三个点之间的环。
2. 如果有一条边不存在，我们就定义它的容量为 $0$。

下图为一个流网络，存在源点 $S$ 和汇点 $T$，每条边上都有对应的容量。

---

可行流： 对于任意满足以下两个条件的流，被称为可行流，用字母 $f$ 表示。$|f|$ 表示该可行流的流量。

1. 容量限制。每条边流过的流量不能超过这条边的容量。即：

0 < f ( u , v ) ≤ c ( u , v ) { u ∈ V , v ∈ V , ( u , v ) ∈ E } 0<f(u,v)\leq c(u,v)\{u\in \text V,v\in \text V,(u,v)\in \text E\} 0<f(u,v)≤c(u,v){u∈V,v∈V,(u,v)∈E}

2. 流量守恒。对于流网络中除源点和汇点外的每个点，都有流入的流量与流出的流量相等。即：

? x ∈ V / { S , T } , ∑ ( u , x ) ∈ E f ( u , x ) = ∑ ( x , v ) ∈ E f ( x , v ) \forall x\in \text V/\{S,T\},\sum_{(u,x)\in \text E}f(u,x)=\sum_{(x,v)\in \text E}f(x,v) ?x∈V/{S,T},(u,x)∈E∑?f(u,x)=(x,v)∈E∑?f(x,v)

最大流： 流网络中流量值最大的一个 可行流 被称为该流网络的 最大可行流，简称为最大流。

这张图显示的是原图的最大流，值为 $9$。

残量网络：对于任意一个流网络 $G$ 中的任意一个可行流 $f$，都能对应一个残量网络，记作 $G_f$。

$G_f$ 的构造：${\text{V}}_f=\text{V},{\text{E}}_f=\text{E}\cup \{(v,u)|?(u,v)\in \text{E}\}$

$$\{\begin{array}{c}{c}^{\prime }(u,v)=c(u,v)?f(u,v)[(u,v)\in \text{E}]\\ c^{\prime }(v,u)=f(u,v)[(v,u)\in \text{E}]\end{array}$$

上图最大流对应的残量网络如下：

原网络 $G$ 的可行流 $f$ 与残量网络 $G_f$ 的可行流 $f^{\prime }$ 的关系：

1. $f+f^{\prime }$ 也是 $G$ 的一个可行流。
2. $|f+f^{\prime }|=|f|+|f^{\prime }|$

证明：

首先定义一下两个可行流的相加。如果是两个同向边相加，则将容量累加，如果是反向边，就把残量网络里的流量在原网络里减去。

然后看可行流需要满足的两个条件。

首先看是否满足容量限制。对于同向边，由于 $0\le f^{\prime }(u,v)\le c^{\prime }(u,v)=c(u,v)?f(u,v)$，因此同向边满足 $0\le f(u,v)+f^{\prime }(u,v)\le c(u,v)$。

对于反向边，由于 $0\le f^{\prime }(u,v)\le c^{\prime }(u,v)=f(v,u)\le c(v,u)$，因此反向边满足 $0\le f(v,u)?f^{\prime }(u,v)\le c(v,u)$。

综上可知，两个可行流相加是满足容量限制的。

对于是否满足流量守恒，这不需要证明，由于原网络满足流量守恒，残量网络也满足流量守恒，那么对于同向边，流入的累加流入的，流出的累加流出的，满足流量守恒，而反向边只不过是相互抵消了一部分的流量，同样满足流量守恒。

由此得出，原网络的任意一个可行流加上残量网络的任意一个可行流所得到的流都是原网络的一个可行流。

对于计算得到的新流的流量值，因为流量值是可行流净往外流出的流量，因此新流的净往外流出的流量 = 原网络的可行流净往外流出的流量 + 残量网络的可行流净往外流出的流量

作用：

通过以上特性，任何一个在残量网络里面发现的流量 >0 的可行流，都能用来增加原网络的可行流。

同时得到一个推论，如果残量网络中存在任何一个流量 >0 的可行流，那么原网络里的可行流就一定不是最大的可行流。

对于最大流来说反过来也是正确的，即如果残量网络中不存在任何一个流量 >0 的可行流，那么原网络里的可行流就一定是最大的可行流。这个反命题可以通过下文的 最大流最小割定理 得出。

增广路径： 在残量网络中从源点出发，沿着容量 >0 的边，存在一条路径能走到汇点，这条路径被称为 增广路径。

注意： 增广路径一般指没有环的简单路径。

---

最小割相关概念

割： 对于流网络 $G=(V,E)$，将点集 $\text{V}$ 分成两个子集 $\text{S},\text{T}$（子集中的节点不需要连通），保证 $\text{S}\cup \text{T}=\text{V},\text{S}\cap \text{T}=?$，且 $S\in \text{S},T\in \text{T}$，像这样的一种将点集划分的结果，就称为割。

割的容量： 所有从 $\text{S}$ 指向 $\text{T}$ 的边的容量之和，即：

$$c(\text{S},\text{T})=\sum _{u\in \text{S}}\sum _{v\in \text{T}}c(u,v)$$

最小割：从流网络中割的所有划分方案中找出割的容量的最小值，被称为该流网络的最小割，又叫最小割的容量。$n$ 个点的流网络中存在 $2^{n?2}$ 种割的划分方案。

割的流量：流网络中所有从 $\text{S}$ 流到 $\text{T}$ 的流量，减去所有从 $\text{T}$ 流到 $\text{S}$ 的流量。即：

$$f(\text{S},\text{T})=\sum _{u\in \text{S}}\sum _{v\in \text{T}}f(u,v)?\sum _{u\in \text{T}}\sum _{v\in \text{S}}f(u,v)$$

• 性质 $1$：对于 $?[\text{S},\text{T}],?f$，都有 $f(\text{S},\text{T})\le c(\text{S},\text{T})$。
• 证明 $1$：
  $$\because f(\text{S},\text{T})=\sum _{u\in \text{S}}\sum _{v\in \text{T}}f(u,v)?\sum _{u\in \text{T}}\sum _{v\in \text{S}}f(u,v)$$
  且
  $$\sum _{u\in \text{T}}\sum _{v\in \text{S}}f(u,v)\ge 0$$

$$\therefore f(\text{S},\text{T})\le \sum _{u\in \text{S}}\sum _{v\in \text{T}}f(u,v)\le \sum _{u\in \text{S}}\sum _{v\in \text{T}}c(u,v)=c(\text{S},\text{T})$$

命题得证。

• 性质 $2$：对于 $?[\text{S},\text{T}],?f$，都有 $f(\text{S},\text{T})=|f|$。

• 证明 $2$：
  $$\because f(\text{S},\text{V})=f(\text{S},\text{S})+f(\text{S},\text{T})$$
  而 $$f(\text{S},\text{S})=0$$
  ∴ f ( S , T ) = f ( S , V ) = f ( { S } , V ) + f ( S ? { S } , V ) \therefore f(\text S,\text T)=f(\text S,\text V)=f(\{S\},\text V)+f(\text S?\{S\},\text V) ∴f(S,T)=f(S,V)=f({S},V)+f(S?{S},V)

而 f ( S ? { S } , V ) f(\text S?\{S\},\text V) f(S?{S},V) 中 S ? { S } \text S?\{S\} S?{S} 不包含 $S,T$，由于 f ( S ? { S } , V ) f(\text S?\{S\},\text V) f(S?{S},V) = 出去的流量 - 回来的流量，在不包含源点和汇点的前提下，其他点的流量的流出和流入都是固定的，流出多少就流回来多少，所以 f ( S ? { S } , V ) = 0 f(\text S?\{S\},\text V)=0 f(S?{S},V)=0。因此 f ( S , T ) = f ( { S } , V ) = ∣ f ∣ f(\text S,\text T)=f(\{S\},\text V)=|f| f(S,T)=f({S},V)=∣f∣。

• 性质 $3$：$f(\text{X},\text{Y})=?f(\text{Y},\text{X})$
• 证明 $3$：
  $$f(\text{X},\text{Y})=\sum _{u\in \text{X}}\sum _{v\in \text{Y}}f(u,v)?\sum _{u\in \text{X}}\sum _{v\in \text{Y}}f(v,u)$$

$$f(\text{X},\text{Y})=?\left\{\sum _{u\in \text{X}}\sum _{v\in \text{Y}}f(v,u)?\sum _{u\in \text{X}}\sum _{v\in \text{Y}}f(u,v)\right\}$$

$$\therefore f(\text{X},\text{Y})=?f(\text{Y},\text{X})$$

• 性质 $4$：$f(\text{Z},\text{X}\cup \text{Y})=f(\text{Z},\text{X})+f(\text{Z},\text{Y})$

• 证明 $4$：

$$f(\text{Z},\text{X}\cup \text{Y})=\left\{\sum _{u\in \text{Z}}\sum _{v\in \text{X}}f(u,v)+\sum _{u\in \text{Z}}\sum _{v\in \text{Y}}f(u,v)\right\}?\left\{\sum _{u\in \text{Z}}\sum _{v\in \text{X}}f(v,u)+\sum _{u\in \text{Z}}\sum _{v\in \text{Y}}f(v,u)\right\}$$

$$\therefore f(\text{Z},\text{X}\cup \text{Y})=f(\text{Z},\text{X})+f(\text{Z},\text{Y})$$

• 性质 $5$：$f(\text{X},\text{X})=0$
• 证明 $5$：

$$f(\text{X},\text{X})=\sum _{u\in \text{X}}\sum _{v\in \text{X}}f(u,v)?\sum _{u\in \text{X}}\sum _{v\in \text{X}}f(v,u)=0$$

• 推论： 通过 性质 1 和 性质 2 可知，对于 $?[\text{S},\text{T}],?f$，都有 $|f|\le c(\text{S},\text{T})$，所以就有 最大流 $\le$ 最小割（对于证明最大流最小割定理有重要作用）

---

最大流最小割定理

对于任意一个流网络 $G=(V,E)$ 都满足：

1. 可行流 $f$ 是最大流。

$$?$$

2. 可行流 $f$ 的残量网络中不存在增广路。

$$?$$

3. $?[\text{S},\text{T}],|f|=c(\text{S},\text{T})$。

证明：

• $1?2$：反证法。假设 $f$ 是最大流，且 $G_f$ 存在增广路径。这说明 $G_f$ 存在至少一个流量大于 $0$ 的可行流 $f^{\prime }$。这样能构造出原网络中另一个可行流 $f+f^{\prime }$，且 $|f+f^{\prime }|>|f|$，说明 $f$ 不是最大流，与假设矛盾。
• $2?3$：构造一个割，使得它在残量网络中不存在增广路径，且 $|f|=c(\text{S},\text{T})$。定义集合 $\text{S}$ 为在 $G_f$ 中从 $S$ 出发，沿容量大于 $0$ 的边走能走到的所有的点。由于残量网络中不存在增广路径，所以集合 $\text{S}$ 中不可能包含 $T$。在定义集合 $\text{T}=\text{V}?\text{S}$，即为构造的合法割。对于正向边 $(u,v)[u\in \text{S},v\in \text{T}]$，由于 $u,v$ 不相通，所以 $f^{\prime }(u,v)=0$，所以 $f(u,v)=c(u,v)$。对于反向边 $(u,v)[u\in \text{T},v\in \text{S}]$ 同理，$c^{\prime }(v,u)=0$，即 $f(u,v)=0$。发现原网络中 $?(u,v)(u\in \text{S},v\in \text{T})$，都有 $f(u,v)=c(u,v),f(v,u)=0$。因此 $|f|=f(\text{S},\text{T})={\sum }_{u\in \text{S}}{\sum }_{v\in \text{T}}f(u,v)?{\sum }_{u\in \text{S}}{\sum }_{v\in \text{T}}f(v,u)={\sum }_{u\in \text{S}}{\sum }_{v\in \text{T}}f(u,v)={\sum }_{u\in \text{S}}{\sum }_{v\in \text{T}}c(u,v)=c(\text{S},\text{T})$。
• $3?1$：由上文最小割的推论中已知 $|f|\le c(\text{S},\text{T})$，且最大流是可行流的一种，所以最大流 $\le c(\text{S},\text{T})$。易知 $|f|\le$ 最大流，而 $|f|=c(\text{S},\text{T})\ge$ 最大流。即 $|f|\ge$ 最大流。综上得出 $|f|=$ 最大流。已证最大流 $\le$ 最小割，而最小割又是割的容量的最小值，得出最小割 $\le c(\text{S},\text{T})=|f|\le$ 最大流，即最小割 $\le$ 最大流，最终得出最大流 = 最小割。

---

费用流相关概念

费用：对于任意一个可行流 $f$，每条边 $(u,v)$ 都有流量 $f(u,v)$ 和费用 $w(u,v)$，该可行流的费用为 $\sum f(u,v)\times w(u,v)$。

最大费用流： 所有最大可行流中费用最大的流称为最大费用最大流。

最小费用流： 所有最大可行流中费用最小的流称为最小费用最大流。

注意： 一张图 $G$ 有最大流，那么就一定有最小费用最大流，但是存在一些特殊的图，图中存在一个从源点无法到达的闭环，闭环中的费用是负的，这时最小费用流可能比我们求出来的更小，因此我们求费用流的做法存在局限性，并不一定能求出最小费用最大流。

如何求最小费用最大流：

最小费用最大流是基于 EK 算法来求的，只需要把 EK 算法中找增广路径的 BFS 算法换成找最短路的 SPFA 算法就可以求最小费用最大流了。

之前我们定义残量网络中反向边的流量等于正向边的容量，表示一个退流的概念，因此我们还需要定义一下反向边的费用，我们希望在退流的同时将费用也退掉，因此可以定义反向边的费用等于负的正向边的费用。

注意： 由于 SPFA 算法遇到负权回路会进入死循环，所以我们常规的求最小费用最大流的算法并不能处理有负权回路的网络。如果网络中存在负权回路，就需要用消圈法来做。