网络流(一)-最大流与最小割问题

问题定义

Flow Networks (流网络)

流网络指一个符合以下特征的有向图 G = (V,E):

每条边关联一个非负数，即边的容量，记为 $c_e$
存在单一源点 (source node) $s\in V$：产生流量的点
存在单一汇点 (sink node) $t\in V$：吸收流量的点

一般的，我们假设流网络满足：没有边进入源点，没有边离开汇点。每个结点至少存在一条边与之相连。

Flow (流)

s-t 流是一个函数 $f: E\rightarrow \mathbb{R}^+$, 值 $f(e)$ 表示边 $e$ 携带的流量。一个流需要满足两个性质

容量条件 (Capacity conditions): \[\forall e\in E, 0\le f(e)\le c_e\]
守恒条件 (Conservation conditions): \[\forall v\in V, v\neq s,t, \sum_{e\text{ into }v}f(e) = \sum_{e\text{ out of }v}f(e)\]

为了使记号简洁，我们定义

\[ f^{\text{out}}(v) = \sum_{e\text{ out of }v}f(e),\ f^{\text{in}}(v) = \sum_{e\text{ into }v}f(e) \]

自然的，对于点集 $S\subseteq V, f^{\text{out}}(S) = \sum_{e\text{ out of }S}f(e),\ f^{\text{in}}(S) = \sum_{e\text{ into }S}f(e)$。

一个流 $f$ 的值, 记作 $v(f)$，定义为源点产生的流量:

\[ v(f) = \sum_{e\text{ out of } s}f(e) = f^\text{out} (s) \]

The Maximum-Flow Problem (最大流问题)

定义：给定一个流网络：有向图 $G=(V,E)$ 与每条边的容量 $c_e$，找出一个具有最大值的流 $f$ #### Cut (分割)

s-t 割是点集 $V$ 的一个划分 $(A,B), s\in A, t\in V$。一个分割 $(A,B)$ 的容量 $c(A,B)$ ，定义为从 A 出来的所有边的容量之和：

\[ c(A,B) = \sum_{e \text{ out of }A} c_e \]

The Minimum-Cut Problem (最小割问题)

定义：给定一个流网络：有向图 $G=(V,E)$ 与每条边的容量 $c_e$，找出一个具有最小容量的分割 $(A,B)$

The Residual Graph (剩余图)

给定流网络 $G$ 及 $G$ 上的流 $f$，定义 $G$ 关于 $f$ 的剩余图 $G_f$ ：

$G_f$ 中的顶点集与 $G$ 中的顶点集相同
对于 $G$ 中的每条边 $e = (u,v)$ ，若 $f(e) < c_e$，则还有 $c_e-f(e)$ 的剩余流量。$G_f$ 中包含边 $e = (u,v)$ ，其容量为 $c_e-f(e)$。这种边称为前向边 (forward edges).
对于 $G$ 中的每条边 $e = (u,v)$ ，若 $f(e) > 0$，则流中有 $f(e)$ 的流可以 “撤销”。$G_f$ 中包含边 $e' = (v,u)$ ，其容量为 $f(e)$。这种边称为后向边 (backward edges).

直观的理解，剩余图定义了在当前流状态下每条边可以操作的流量：在初始流网络中剩余的流量可以继续使用，以及使用的流量则可以 “撤销” ：使用一条反向的边运输流量。

定义一条边的剩余流量 (residual capacity) 为这条边在剩余图中的流量。

最大流最小割定理

定理

在任意的流网络中，最大的 s-t 流的值等于最小的 s-t 割的容量。

割提供了流的上界

直观

从直观上理解流与割，最大流指的是流量从源点流到汇点，可以同时流出的最大容量。而割将网络分成了两部分，使得从源点到汇点的流量必须从 $A$ 穿出到达 $B$ 。因此从源点流到汇点可以同时流出的容量受到从 $A$ 到 $B$ 的所有边容量之和的限制。

换句话说，对于任意的 s-t 割，它的容量 $c(A,B)$ 是所有 s-t 流值 $v(f) $ 的上界。

证明

定理 1：令 $f$ 是任意的 s-t 流，$(A,B)$ 是任意 s-t 割，有 $v(f) = f^\text{out}(A)-f^\text{in}(A)$

证明：有 $f^\text{in}(s) = 0$ , 且对于 $A$ 中除 $s$ 之外的点 $v$: $f^\text{out}(v)-f^\text{in}(v) = 0$

\[ \begin{align*} v(f) &= f^\text{out}(s)-f^\text{in}(A)\\\\ &= f^\text{out}(s)-f^\text{in}(s)\\\\ &= f^\text{out}(s)-f^\text{in}(s) + \sum_{v\in A-\{s\}}(f^\text{out}(v)-f^\text{in}(v) )\\\\ &= \sum_{v\in A}(f^\text{out}(v)-f^\text{in}(v) )\\\\ &= f^\text{out}(A)-f^\text{in}(A ) \end{align*} \]

同样的， 定理 2：令 $f$ 是任意的 s-t 流，$(A,B)$ 是任意 s-t 割，有 $v(f) = f^\text{in}(B)-f^\text{out}(B)$

定理 3：令 $f$ 是任意的 s-t 流，$(A,B)$ 是任意 s-t 割，有 $v(f)\le c(A,B)$

证明：

\[ \begin{align*} v(f) &=f^\text{out}(A)-f^\text{in}(A) \\\\ &\le f^\text{out}(A) = \sum_{e \text{ out of }A}f(e)\\\\ &\le \sum_{e \text{ out of }A}c_e=c(A,B) \end{align*} \]

最大流等于最小割

定理 4：如果 $f^*$ 是使得在剩余图 $G_{f^*}$ 中没有 s-t 路径的一个 s-t 流，则 $G$ 中存在一个 s-t 割 $(A^*, B^*)$ 使得 $v(f) = c(A^*,B^*)$. 因此，$f^*$ 是 $G$ 上的一个最大流, $(A^*, B^*)$ 是 $G$ 上的一个最小割。

证明：令 $A^*$ 为 $G_{f^*}$ 中存在一条 s-v 路径的所有点 $v$ 的集合，$B^* = V-A^*$

显然有：$sA^, tB^ $，因此 $(A^*, B^*)$ 是 $G$ 上的一个 s-t 分割。
设 $e = (u,v)$ 是 $G$ 中的一条边，满足 $u\in A^*, v\in B^*$, 则有 $f(e) = c _ e$: 若 $f(e) < c_e$, 则 $G_{f^*}$ 中有一条容量为 $c _ e-f(e)$ 的前向边 $e = (u,v)$；由于 $u\in A^*$, $G_{f^*}$ 中存在一条 s-u 路径，将e接上这条路径，则得到 $G_{f^*}$ 中一条 s-v 路径，与 $v\in B^*$ 矛盾。
设 $e' = (u',v')$ 是 $G$ 中的一条边，满足 $u'\in B^*, v'\in A^*$, 则有 $f(e') = 0$: 若 $f(e')>0$, 则 $G_{f^*}$ 中有一条容量为 $f(e')$ 的后向边 $e'' = (v',u')$；由于 $v'\in A^*$, $G_{f^*}$ 中存在一条 s-v’ 路径，将 e” 接上这条路径，则得到 $G_{f^*}$ 中一条 s-u’ 路径，与 $u'\in B^*$ 矛盾。

因此，所有从 $A^*$ 出发的边 $f(e) = c_e$，所有进入 $A^*$ 的边 $f(e) = 0$

\[ \begin{align*} v(f^*) &=f^\text{out}(A^*)-f^\text{in}(A^*) \\\\ &= \sum_{e \text{ out of }A^*}f(e) - \sum_{e \text{ into }A^*}f(e)\\\\ &= \sum_{e \text{ out of }A^*}c_e\\\\ &=c(A^*,B^*) \end{align*} \]

由定理 3，任意的 s-t 流 $f$ ，任意 s-t 割 $(A,B)$ ，有 $v(f)\le c(A,B)$ ，因此 $f^*$ 是 $G$ 上的一个最大流。否则，若存在一个有更大值的流 $f’$ ，则 $f’$ 的值超过 s-t 割 $(A^*, B^*)$ 的容量，与定理3矛盾。同理，$(A^*, B^*)$ 是 $G$ 上的一个最小割。

即，在任意的流网络中，最大的 s-t 流的值等于最小的 s-t 割的容量。

对偶解释

前面分析最大流最小割的过程应该很熟悉的有一种对偶的气息（

它们确实互为对偶问题，这里有两种形式的线性规划。【这里假设容量均为整数，即为整数规划问题】

第一种形式

最大流问题的线性规划

\[ \begin{align*} \max \ & v\\\\ \text{s.t.}\sum _ {e\text{ out of } s}f(e) & = v\\\\ \sum _ {e\text{ into } t}f(e) & = v\\\\ \sum_{e\text{ into } v} f(e) - \sum_{e\text{ out of } v} f(e) &=0, \forall v\in V-\{s,t\} \\\\ f(e)&\le c _ e,\forall e\in E\\\\ f(e)&\ge 0,\forall e\in E\\\\ \end{align*} \]

可以得到它的对偶问题为

\[ \begin{align*} \min \ & \sum_{e\in E} c_ey_e\\\\ \text{s.t.}\ u_i-u_j+y_e &\ge 0, e=(i,j)\in E\\\\ -u_s+u_t&=1\\\\ y_e&\ge 0 \end{align*} \]

[有点难。。。但慢慢算还是可以的: ) ]

观察一下这个对偶规划：

系数矩阵是一个全幺模矩阵，故最优解均为整数【见整数规划】
目标函数与 $u_i$ 无关，约束与 $u_i$ 孤立的值无关，而与 $u_i, u_j$ 的差值相关。故简单令 $u_s = 0$ 不改变问题本身。

接下来证明这个规划实际上就是最小割问题：（详细证明请阅读参考资料 4）

给定 $G$ 的一个s-t分割 $(A,B)$，可以得到一个对偶规划的可行解：
- 当 $iA,u_i = 0 $，当 $iB,u_i = 1 $
- 当 $e=(u,v), u\in A, v\in B, y_e = 1$, 否则，$y_e = 0$
可以验证这是一个可行解。且最小割问题即为该问题的最优解。
给定对偶规划的一个整数可行解，可以得到 $G$ 的一个s-t分割 $(A,B)$：对于变量 $y_e, e = (i,j)$, 只需满足 $u_i-u_j+y_e \ge 0, y_e\ge 0$, 由于目标函数为 $\min \sum_{e\in E} c_ey_e$, 可以得到 \[y_e= \max\{0,u_j-u_i\}\]，由 $u_s = 0, u_t = 1$, 对每条从 s 到 t 的路径，至少有一个 $y_e>0, y_e\ge 1$ 。将图中 $y_e>0$ 的边删去，令 $A$ 为图中存在一条 s-v 路径的所有点 $v$ 的集合, 且 $A$ 中的点 $ u_i = 0$。令 $B = V-A$ 中的点 $u_j = 1$。令删去的边 $y_e =$1。则此时目标函数值即为分割的容量，且小于等于原来的整数可行解。

互补松弛性

根据对偶定理中的互补松弛性，对于最优解：最大流与最小割

当 $y_e = 1$ 需满足 $f(e) = c_e$
当 $u_i-u_j+y_e>0$ (即 $e$ 是从B出发到A的边), 需满足 $f(e) = $0

与前面的证明对应起来了w

第二种形式

最大流问题的线性规划

\[ \begin{align*} \max &\sum_{p\in P}x_p\\\\ \text{s.t.}\ \sum_{p\in P:e\in p} x_p&\le c_e,& \forall e \in E\\\\ x_p&\ge 0, &\forall p \in P \end{align*} \]

其中 $p$ 表示所有从 s 到 t 的路径，一条边可以被多条路径使用，共同分配它的容量。第一个约束指的是对每条边，经过它的路径的流量之和不超过自身的容量。

它的对偶问题为：

\[ \begin{align*} \min &\sum_{e\in E}c_ey_e\\\\ \text{s.t.}\ \sum_{e\in p} y_e&\ge 1,&\forall p\in P\\\\ y_e&\ge 0, &\forall e\in E \end{align*} \]

我们同样可以证明这个规划是最小割问题的规划。(参考资料3)其中， $y_e = 1$ 表示它是一条从 $A$ 到 $B$ 的边。

这种形式可以更好的理清对偶的关系，但是好像不好解（x

参考资料：

《Algorithm Design》Jon Kleinberg， Eva Tardos， Chapter 7

wiki: 最大流最小割定理

http://theory.stanford.edu/~trevisan/cs261/lecture15.pdf

https://www3.diism.unisi.it/~agnetis/mincutENG.pdf