【管理运筹学】第 7 章 | 图与网络分析（4，最大流问题）

系列文章目录

【管理运筹学】第 7 章 | 图与网络分析（1，图论背景以及基本概念、术语、矩阵表示）
【管理运筹学】第 7 章 | 图与网络分析（2，最小支撑树问题）
【管理运筹学】第 7 章 | 图与网络分析（3，最短路问题）
【管理运筹学】第 7 章 | 图与网络分析（5，最小费用流问题及最小费用最大流问题）

---

引言

承接系列文章，这一节主要来学习最大流问题。

生活中，有许多流量问题，例如公路系统的车辆流、控制系统的信息流和金融系统的现金流等等。对于这类包含了流量问题的系统，我们往往要在现有系统容量的约束下，求出系统的最大流。

---

四、最大流问题

4.1 有关概念与定理

4.1.1 基本概念

定义 1 —— 对于网络 $G=(V,A,C)$ ，在弧集合 $A$ 上的一个函数 f = { f ( v i , v j } f=\{f(v_i,v_j\} f={f(vi​,vj​} 称为网络流，$f(v_i,v_j)$ 为弧 $a_{ij}$ 上的流。$c_{ij}$ 为弧 $a_{ij}$ 所能通过的最大流量。

定义 2 —— 满足下列条件的网络流 $f$ 称为可行流。

（1）容量限制条件。即每条弧上的流量满足 $0\le f(v_i,v_j)\le c_{ij}.$

（2）平衡条件。对于中间点，流出量和流入量相等。对于起点，记所有从起点流出的流量，减去流进起点的流量为 $V(f)$ ；对于终点，所有从终点流出的流量，减去流进终点的流量为 $-V(f).$

$V(f)$ 即为可行流 $f$ 的流量，即起点的净输出量或终点的净输入量。

可行流总是存在的，如所有弧的流量 $f_{ij}$ 均取 0 ，就是一个可行流，$V(f)=0.$

定义 3 —— 网络中可能会有多条可行流，其中流量最大的可行流我们称为最大流。

设 $\mu =(x,\cdots ,u,v,\cdots ,t)$ 是网络 $G$ 中的一条初等链（各个顶点均不相同），定义链的方向为 $x\to t$ 。若链上有弧 $(u,v)$ 的方向与 $\mu$ 的方向一致，称其为前向弧，所有前向弧记为 ${\mu }^{+}$ 。若链上有弧 $(v,u)$ 的方向与 $\mu$ 的方向相反，称其为后向弧，所有后向弧记为 ${\mu }^{-}$ 。

对于一个可行流 f = { f i j } f=\{f_{ij}\} f={fij​} ，我们把网络中使 $f_{ij}=c_{ij}$ 的弧称为饱和弧，使 $f_{ij}<c_{ij}$ 的弧称为非饱和弧，把 $f_{ij}=0$ 的弧称为零流弧，$f_{ij}>0$ 的弧称为非零流弧。

定义 4 —— 设 $f$ 为一个可行流，$v_s$ 是网络起点，$v_t$ 是网络终点，$\mu$ 是从起点到终点的一条链，若 $\mu$ 满足下列条件：

（1）所有前向弧均为非饱和弧。（2）所有后向弧均为非零流。

则称 $\mu$ 为关于可行流 $f$ 的一条增广链。

定义 5 —— 对于有向网络 $G=(V,A,C)$ ，若 $S$ 为 $V$ 的子集，$\overline{S}=V-S$ ，则称弧集合 ( S , S ‾ ) = { a ∣ a = ( u , v ) , u ∈ S , v ∈ S ‾ } (S,\overline{S})=\{a|a=(u,v),u\in S,v\in\overline{S}\} (S,S)={a∣a=(u,v),u∈S,v∈S} 为网络 $G$ 的一个截集，并将截集中所有弧容量之和称为截容量，简称截量。所有截集中截量最小的称为最小截，其容量为最小截量。

感觉这不就是割集的意思嘛，不过是在有向图中。比如下图，如果 S = { v 2 , v 3 , v 4 , v 5 , v 6 } S=\{v_2,v_3,v_4,v_5,v_6\} S={v2​,v3​,v4​,v5​,v6​} ，截集为 $\{(v_2,v_1),(v_3,v_1\}$ 。不能加上 $(v_1,v_4)$ ，它不是这个截集中的，因为它的起点不在集合 $S$ 中。

4.1.2 有关定理

定理 1 —— 若 $f^{\ast }$ 是网络 $G=(V,A,C)$ 上的可行流，则可行流 $f^{\ast }$ 为最大流的充要条件为 $G$ 中不存在关于 $f^{\ast }$ 的增广链 $\mu$ 。

定理 2（最大流量、最小截量定理） —— 任一网络 $G=(V,A,C)$ 中，从起点 $v_s$ 到终点 $v_t$ 的最大流的流量，等于分离 $v_s$ 与 $v_t$ 的最小截集的容量。

4.2 寻找最大流的标号法

寻找最大流的标号法，是由 Ford（福特）和 Fulkerson（福克尔逊）首先提出来的，所以又称 2F 算法。

2F 算法可以分为两大过程。首先是标号过程，检查是否存在增广链，如果不存在，现行流就是最大流；否则，进入调整过程，也叫增值过程。标号与调整过程如下。

（1）标号过程

先给起点 $v_s$ 标上 $(0,+\infty )$，不断其它点 $v_i,v_j$ （包括后向弧），此时有下列两种情况：

1. 在前向弧 $(v_i,v_j)$ 上，若 $f_{ij}<c_{ij}$ ，则给 $v_j$ 标号 $(v_i,l(v_j))$ 。其中， l ( v j ) = m i n { l ( v i ) , c i j − f i j } l(v_j)=min\{l(v_i),c_{ij}-f_{ij}\} l(vj​)=min{l(vi​),cij​−fij​} 。
2. 在后向弧 $(v_j,v_i)$ 上，若 $f_{ji}>0$ ，则给 $v_j$ 标号 $(-v_i,l(v_j))$ 。其中， l ( v j ) = m i n { l ( v i ) , f j i } l(v_j)=min\{l(v_i),f_{ji}\} l(vj​)=min{l(vi​),fji​} 。

重复上述步骤，一旦终点 $v_t$ 得到标号，表明得到一条增广链，进入调整过程。

若标号过程进行不下去，则算法结束，此时可行流即为最大流。

（2）调整过程

首先根据各点标号进行回溯，找出增广链。增广链的调整量 $\theta$ 为终点 $l(v_t)$ 。
令$$f_{ij}^{\prime }=\{\begin{array}{ll}{f}_{ij}+l(v_t),& (v_i,v_j)\in {\mu }^{+}\\ f_{ij}-l(v_t),& (v_i,v_j)\in {\mu }^{-}\\ f_{ij},& else\end{array}$$ 即现行流中的前向弧加上调整量，后向弧减去调整量，现行流外的流量不变。

对新流 $f_{ij}^{\prime }$ ，重新进行标号过程。

---

写在最后

最大流问题，相较于之前的最短路还是较为简单些的，不过这只是一个载体，后面结合了最小费用流可就不简单了。