定义 1（容量网络）

一个 容量网络 是一个四元组 \(N = \langle V, E, c, s, t \rangle\)，其中：

• \(N = \langle V, E \rangle\) 是有向连通图，记 \(n = |V|\)，\(m = |E|\)
• \(c: E \to \mathbb{R}^{+}\) 是边的 容量 函数
• \(s \in V\) 称作 发点（源），\(t \in V\) 称作 收点（汇）
• 其余顶点称作 中间点

定义 2（可行流）

设 \(f: E \to \mathbb{R}^{+}\)，若满足下述条件，则称 \(f\) 为 \(N\) 上的一个 可行流：

1. 容量限制：\(\forall \langle i, j \rangle \in E\)，\(f(i, j) \le c(i, j)\)
2. 平衡条件：\(\forall i \in V - \{ s, t \}\)，

定义 3（流量）

可行流 \(f\) 的 流量 \(v(f)\) 定义为从 \(s\) 流出的净流量：

等价地，\(v(f)\) 也是流入 \(t\) 的净流量。

定义 4（最大流问题）

给定容量网络 \(N\)，求使 \(v(f)\) 最大的可行流 \(f\)，即求解：

定义 5（割集）

设容量网络 \(N = \langle V, E, c, s, t \rangle\)，\(A \subset V\) 且 \(s \in A\)，\(t \in V - A\)，称

为 \(N\) 的 割集，其容量定义为

引理 1

设 \(f\) 是任一可行流，\((A, V - A)\) 是任一割集，则

即流量等于 从 \(A\) 到 \(V - A\) 的流量减去从 \(V - A\) 到 \(A\) 的流量。

引理 2

设 \(f\) 是任一可行流，\((A, V - A)\) 是任一割集，则

引理 3

设 \(f\) 是一个可行流，\((A, V - A)\) 是一个割集。如果

则 \(f\) 是 最大流，\((A, V - A)\) 是 最小割集。

定义 6（增广链相关概念）

设容量网络 \(N = \langle V, E, c, s, t \rangle\)，\(f\) 是 \(N\) 上的一个可行流。

1. \(N\) 中流量等于容量的边称作 饱和边，流量小于容量的边称作 非饱和边
2. 流量等于 \(0\) 的边称作 零流边，流量大于 \(0\) 的边称作 非零流边
3. 不考虑边的方向，\(N\) 中从顶点 \(i\) 到 \(j\) 的一条边不重复的路径称作 \(i\)-\(j\) 链。链中与链方向一致的边称作 前向边，与链方向相反的边称作 后向边
4. 如果链中所有前向边都是非饱和的，所有后向边都是非零流的，则称这条链为 \(i\)-\(j\) 增广链

定理 1（增广链定理）

可行流 \(f\) 是最大流当且仅当不存在关于 \(f\) 的 \(s\)-\(t\) 增广链。

定理 2（最大流最小割集定理）

最大流的流量等于最小割集的容量。

即，若 \(f^*\) 是最大流，\((A^*, V - A^*)\) 是最小割集，则

定义 7（辅助网络）

设容量网络 \(N = \langle V, E, c, s, t \rangle\)，\(f\) 是 \(N\) 上的一个可行流。关于 \(f\) 的 辅助网络 \(N(f) = \langle V, E(f), ac, s, t \rangle\)，其中：

• 前向边集：\(E^{+}(f) = \{ \langle i, j \rangle \mid \langle i, j \rangle \in E \text{ 且 } f(i, j) < c(i, j) \}\)
• 后向边集：\(E^{-}(f) = \{ \langle j, i \rangle \mid \langle i, j \rangle \in E \text{ 且 } f(i, j) > 0 \}\)
• 边集：\(E(f) = E^{+}(f) \cup E^{-}(f)\)
• 辅助容量：

\(N(f)\) 也是一个容量网络。

引理 4

在辅助网络 \(N(f)\) 中，\(s\)-\(t\) 增广链与 \(N\) 中关于 \(f\) 的 \(s\)-\(t\) 增广链一一对应。

定义 8（分层辅助网络）

按广度优先搜索 \(N(f)\) 中 \(s\)-\(t\) 最短路，按到 \(s\) 的距离 \(d\) 对顶点分层。

分层辅助网络 \(AN(f) = \langle V(f), AE(f), ac, s, t \rangle\)，其中：

定义 9（极大流与流通量）

1. 前向增广链：关于 \(f\) 的不含后向边的增广链
2. 极大流：不存在前向增广链的可行流。最大流必是极大流，但极大流不一定是最大流
3. 中间点 \(i\) 的流通量 \(\theta(i)\)：以 \(i\) 为终点的边的容量之和与以 \(i\) 为始点的边的容量之和中的小者

引理 5

在 Dinic 算法第 5 步得到的 \(AN(f)\) 中，\(s\) 的流通量等于 \(t\) 的流通量。

引理 6

在每个阶段结束时，\(g\) 是 \(AN(f)\) 中的极大流。

引理 7

在每个阶段，\(AN(f + g)\) 中 \(s\)-\(t\) 距离大于前一个阶段 \(AN(f)\) 中 \(s\)-\(t\) 距离。约定，当不存在 \(s\)-\(t\) 最短路径时，规定其距离为 \(+\infty\)。

定理 3（Dinic 算法的正确性与复杂度）

Dinic 算法得到的 \(f\) 是最大流，且算法在 \(O(n^3)\) 步内终止。

定义 10（容量-费用网络）

一个 容量-费用网络 是一个五元组 \(N = \langle V, E, c, w, s, t \rangle\)，其中 \(\langle V, E, c, s, t \rangle\) 是容量网络，\(w: E \to \mathbb{R}\) 是边的 费用 函数。

可行流 \(f\) 的 费用 定义为：

最小费用流问题

给定容量-费用网络 \(N\) 和目标流量 \(v_0\)，求流量为 \(v_0\) 的 费用最小 的可行流。

定义 11（容量-费用网络的辅助网络）

设容量-费用网络 \(N = \langle V, E, c, w, s, t \rangle\)，关于可行流 \(f\) 的辅助网络 \(N(f) = \langle V, E(f), ac, aw, s, t \rangle\)，其中辅助容量 \(ac\) 同定义 7，辅助费用为：

引理 8

设 \(f\) 是容量-费用网络 \(N\) 上的可行流，\(g\) 是辅助网络 \(N(f)\) 上的可行流，令 \(f' = f + g\)，则

定义 12（圈流）

设 \(C\) 是 \(N\) 中边不重复的回路，\(C\) 上的 圈流 \(h_C\) 定义如下：

• \(\forall \langle i, j \rangle \in E(C)\)，\(h_C(i, j) = d\)
• \(\forall \langle i, j \rangle \in E - E(C)\)，\(h_C(i, j) = 0\)

其中 \(d > 0\) 是 \(h_C\) 的 环流量。

圈流的性质

1. \(h_C\) 为可行流，且 \(v(h_C) = 0\)，\(w(h_C) = d \cdot w(C)\)
2. 设 \(f\) 是 \(N\) 上的一个可行流，\(h_C\) 是 \(N(f)\) 上的一个圈流，则 \(f + h_C\) 仍是 \(N\) 上的可行流，且 \(v(f + h_C) = v(f)\)，\(w(f + h_C) = w(f) + aw(h_C)\)

命题 1（负回路与最短路径）

赋权有向图 \(D = \langle V, E, w \rangle\) 中任意两点之间都有最短路径或不存在路径，当且仅当 \(D\) 中不含负回路。

等价地说，若 \(D\) 中存在负回路 \(C\)，\(i\) 是 \(C\) 上的一个顶点，那么从 \(i\) 到 \(j\) 的路径可以先重复走 \(C\) 若干次再到 \(j\)，路径的权可以任意小。

定义 13（带需求的流通）

给定带需求的流通图 \(N = \langle V, E, c, S, T \rangle\)，\(\forall v \in V\) 存在需求 \(d_v\)。所有发点集合为 \(S\)，所有收点集合为 \(T\)：

• 收点：\(d_v > 0\)，表示 \(v\) 对流有 \(d_v\) 的需求
• 发点：\(d_v < 0\)，表示 \(v\) 有 \(-d_v\) 的供给
• 中间点：\(d_v = 0\)，\(v\) 不是发点和收点

所有容量和需求都是整数。

命题 2（必要条件）

如果存在一个带需求 \(\{ d_v \}\) 的可行流通，那么

命题 3

\(G'\) 没有大于 \(D\) 的 \(s^*\)-\(t^*\) 流。因为 \(c(\{s^*\}, V \cup \{t^*\}) = D\)。

定义 14（Hitchcock 运输问题）

有 \(m\) 个产地 \(A_1, A_2, \ldots, A_m\) 和 \(n\) 个销地 \(B_1, B_2, \ldots, B_n\)：

• \(A_i\) 的产量为 \(a_i\)
• \(B_j\) 的销量为 \(b_j\)
• 从 \(A_i\) 到 \(B_j\) 的单位运费为 \(w_{ij}\)

假设 产销平衡，即 \(\sum_{i=1}^{m} a_i = \sum_{j=1}^{n} b_j\)。求总运费最小的调运方案。

问题描述

图像分割的目标是将一幅图片的 前景 与 背景 分离，对每个像素进行"前景 / 背景"的标记。

容量分配

• 对边 \(e = \langle s, i \rangle\)，令 \(c_e = a_i\)
• 对边 \(e = \langle i, t \rangle\)，令 \(c_e = b_i\)
• 对邻居边 \(e = \langle j, i \rangle\) 和 \(e' = \langle i, j \rangle\)，令 \(c_e = c_{e'} = p_{ij}\)

穿过割 \((A', B')\) 的边分成三类：

• 边 \(\langle s, j \rangle\)，\(j \in B'\)：贡献 \(a_j\)
• 边 \(\langle i, t \rangle\)，\(i \in A'\)：贡献 \(b_i\)
• 边 \(\langle i, j \rangle\)，\(i \in A'\)，\(j \in B'\)：贡献 \(p_{ij}\)

割的容量为：

注意到：

而

因此 最大化 \(q(A, B)\) 等价于最小化割容量 \(c(A', B')\)！

图像分割算法

1. 建立像素邻居图 \(G\)
2. 将 \(G\) 转化成容量网络 \(G'\)
3. 求解 \(G'\) 的最小割 \((A', B')\)
4. 前景为 \(A' - \{s\}\)，背景为 \(B' - \{t\}\)

核心知识点