Skip to content

L010 流网络和最大流

流网络和最大流

「流网络」（flow network）是一个五元组，记作 \(G=\langle V,A,c,s,t\rangle\)，其中 \(V\) 和 \(A\) 分别是顶点和弧的有限集合，\(c:A\to \mathbb{R}_+\) 是「容量函数」（capacity function），\(c(a)\) 是弧 \(a\) 的「容量」（capacity），\(s\in V\) 是「源」（source），\(t\in V\) 是「汇」（sink），且 \(s\ne t\).

在流网络 \(G\) 中，「流」（flow）是一个函数 \(f:A\to \mathbb{R}\)，其中 \(f(a)\) 称作弧 \(a\) 的「流量」（flow）。所有弧的流量均为零的流称作「零流」（zero flow）。满足以下两点的流称作「可行流」（feasible flow）：

  • 「容量约束」（capacity constraint）：\(\forall a\in A,0\le f(a)\le c(a)\).
  • 「守恒约束」（conservation constraints）：\(\forall v\in V\setminus \{s,t\},f^-(v)=f^+(v)\)，其中 \(f^-(v)\) 和 \(f^+(v)\) 分别表示顶点 \(v\) 的「流入量」和「流出量」，定义如下：
\[ f^-(v)=\sum_{\langle u,v\rangle\in A}f(\langle u,v\rangle), f^+(v)=\sum_{\langle v,u\rangle\in A}f(\langle v,u\rangle) \]

对于可行流 \(f\)，汇的净流入量 \(f^-(t)-f^+(t)\) 称作 \(f\) 的「值」，记作 \(\mathrm{val}(f)\). 流网络中值最大的可行流称为「最大流」（maximum flow）。

对于流网络 \(G\) 和可行流 \(f\)，「剩余容量」（residual capacity）是一个函数 \(r:V\times V\to \mathbb{R}_+\)，\(r(u,v)\) 称作顶点 \(u\) 到顶点 \(v\) 的剩余容量，表示从 \(u\) 到 \(v\) 的容量的可增量，包含下述两项的和：

  • \(\langle u,v\rangle\) 的可增量：仅当弧 \(\langle u,v\rangle\) 存在时，为 \(c(\langle u,v\rangle)-f(\langle u,v\rangle)\)，否则计为零。
  • \(\langle v,u\rangle\) 的可减量：仅当弧 \(\langle v,u\rangle\) 存在时，为 \(f(\langle v,u\rangle)\)，否则计为零。

所有顶点间的剩余容量可以表示为一个赋权有向图，称作「剩余网络」（residual network），记作 \(G_f=\langle V,A_f, r\rangle\)，其中：

  • \(V\) 是顶点的有限集合，继承自 \(G\).
  • \(A_f\) 是弧的有限集合，\(\langle u,v\rangle\in A_f\text{ iff. }r(u,v)>0\).
  • \(r\) 是赋权函数，继承自剩余容量函数。

在剩余网络 \(G_f\) 中，\(s\)-\(t\) 有向路称作 \(f\)「增广路」（augmenting path），其经过的弧的最小权称为这条路的「可增量」（tolerance）。

Th.7.6 对于流网络 \(G\) 和可行流 \(f\)，\(f\) 是最大流当且仅当剩余网络 \(G_f\) 中不含 \(f\) 增广路。

Lem.7.4 对于流网络 \(G\)、可行流 \(f\)、顶点集 \(V\) 的划分 \(S,T(s\in S,t\in T)\)，所有尾在 \(S\) 中，头在 \(T\) 中的弧的流量和记作 \(f^+(S)\)；所有头在 \(S\) 中，尾在 \(T\) 中的弧的流量和记作 \(f^-(S)\)，则 \(f^+(s)-f^-(s)=f^+(S)-f^-(S)\).

所有尾在 \(S\)、头在 \(T\) 中的弧的集合称作 \(G\) 的「源汇割」（source-sink cut），记作 \(C_{S,T}\)，其中所有弧的容量和称作 \(C_{S,T}\) 的「容量」（capacity），记作 \(c(S,T)\).

Cor.7.2 对于流网络 \(G\)、可行流 \(f\)、源汇割 \(C_{S,T}\)，有 \(\mathrm{val}(f)\le c(S,T)\).

Th.7.7（最大流最小割定理）对于任何一个流网络，最大流的值等于所有源汇割的容量的最小值。

「福特-法尔克森算法」（Ford-Fulkerson algorithm）

【Algo.7.4】

「整数流」（integer flow）、「单位路径流」（unit path flow）。

「单源单汇流网络」（single-source single-sink network）、「多源多汇流网络」（multi-source multi-sink network）、「超源」（super-source）、「超汇」（super-sink）。