DILinAV（3）：最大流与最小割

本文内容主要来自M. Nikos Paragios和M. Pawan Kumar的课程《Discrete Inference & Learning in Artificial Vision》的第3节“Maximum flow and minimum cut”。

最大流优化问题，在组合优化中历史悠久，并且有高效算法求解特定图的最大流。最大流算法可用于求解特定MRF或CRF的能量最小化问题。

超额函数

有向图：黑色的值表示容量$c$，红色的值表示流函数$f$的值（没有红色值的弧为0）。

有向图记为$\mathbf D=(\mathbf V,\mathbf A)$，弧$a$的容量（capacity）记为$c(a)$，函数$f$就是将$\mathbf A$映射为实数的流函数（flow function）。对映射函数$f$，顶点$v$的超额函数（excess function）或超额流表示输入值之和减去输出值之和，

\begin{equation} E_f(v) = \sum_{a\in \text{in-arcs}(v)}f(a) - \sum_{a\in \text{out-arcs}(v)}f(a)， \end{equation}

有时也记为$E_f(v) = f(\text{in-arcs}(v)) - f(\text{out-arcs}(v))$。上图中，$E_f(v_1)=1-4-3=-6$，$E_f(v_2)=10+4=14$。

顶点子集$\mathbf U$的超额函数记为

\begin{equation} E_f(\mathbf U) = \sum_{a\in \text{in-arcs}(\mathbf U)}f(a) - \sum_{a\in \text{out-arcs}(\mathbf U)}f(a)， \end{equation}

有时也记为$E_f(\mathbf U) = f(\text{in-arcs}(\mathbf U)) - f(\text{out-arcs}(\mathbf U))$。上图中，$E_f(\{v_1,v_2\})=1+10-3=8$（不计$v_1$和$v_2$之间的流量值）。事实上，子集的超额函数等于子集中顶点超额函数之和

\begin{equation} E_f(\mathbf U) = \sum_{v\in \mathbf U}E_f(v)。 \end{equation}

流与割

s-t流

流函数将$\mathbf A$映射为实数。有效的s-t流函数满足条件：

• $0\le \text{flow}(a)\le c(a)$，弧的流非负且不大于其容量；
• $\forall v\in V\backslash\{s,t\},\sum_{(u,v)\in\mathbf A}\text{flow}((u,v))=\sum_{(v,u)\in\mathbf A}\text{flow}((v,u))$，除$s$和$t$之外顶点的输入流等于输出流，也就是除$s$和$t$之外顶点的超额流都为0，$\forall v\in V\backslash\{s,t\},E_\text{flow}(v)=0$。

上图是有效的s-t流，而上上图不是。s-t流的值为$s$的输出流减去其输入流：

\begin{equation} -E_\text{flow}(s) = E_\text{flow}(t) = \sum_{(s,v)\in\mathbf A}\text{flow}((s,v)) - \sum_{(u,s)\in\mathbf A}\text{flow}((u,s))。 \end{equation}

也就是说，s-t流的值为$-E_\text{flow}(s)$或$E_\text{flow}(t)$。顶点$s$和$t$超额函数值不一定为0。顶点$s$称为源（source），$t$称为槽（sink）。$s$没有输入边，$t$没有输出边。上图中$-E_\text{flow}(s) = E_\text{flow}(t) = 1$。

s-t割

令$\mathbf U$是图$\mathbf D=(\mathbf V,\mathbf A)$中顶点$\mathbf V$的子集。图的割$\mathbf C$是满足如下条件弧的集合：

\[ (u,v)\in\mathbf A,\quad u\in\mathbf U,\quad v\in V\backslash\mathbf U， \]

也就是$\mathbf C=\text{out-arcs}(\mathbf U)$。对于s-t割，$s$总是$\mathbf U$的子集，而$t$绝不是其子集，也就是满足

\[ s\in\mathbf U,\quad t\in V\backslash\mathbf U。 \]

割$\mathbf C$的容量记为$\sum_{a\in\mathbf C}c(a)$。上图s-t割的容量为17。

流与割的关系

任意s-t流的值不超过任意s-t割$\mathbf C$的容量，证明如下：

\[ \begin{aligned} -E_\text{flow}(s) &= -\left(E_\text{flow}(s) + \sum_{v\in\mathbf U\backslash\{s\}}E_\text{flow}(v)\right)\\ &=-E_\text{flow}(\mathbf U)\\ &=\text{flow}(\text{out-arcs}(\mathbf U)) - \text{flow}(\text{in-arcs}(\mathbf U))\\ &\le\sum_{a\in\mathbf C}c(a)\quad (\mathbf C=\mathbf U) \end{aligned}。 \]

注意，除了$s,t$外顶点的超额流都为0。等号成立的条件是

\[ \text{flow}(a)= \left\{ \begin{aligned} &c(a),&&a\in\text{out-arcs}(\mathbf U)\\ &0,&&a\in\text{in-arcs}(\mathbf U) \end{aligned}。 \right. \]

最大流

最大流问题

由于$s$没有输入，最大流实际上就是最大化$\sum_{(s,v)\in\mathbf A}\text{flow}((s,v))$。按照此思路，尝试直接求解最大流：

1. 找到满足$\text{flow}(a)<c(a)$弧构成的s-t路径；
2. 沿着这些弧，通过最大可允许的流。

由于存在不同的路径，这样得到的不一定是最大流。上图所示，左边的到了最大流，右边由于$\{(s,v_1),(v_2,t)\}$弧饱和了，不能再增加路径，得到的不是最大流。

最大流算法（Ford-Fulkerson算法）

余图（residual graph）的顶点和原图一样，如上图右所示，它包含两类弧：（1）原图的未饱和弧；（2）原图$\text{flow}(a)>0$的弧的反向弧。由于连接$s$和$t$的反向弧不可能包含在s-t路径中，不必增加到$s$和离开$t$的反向弧¹。当原图流为0时，余图和不包含权值的原图相同。

基于余图的Ford-Fulkerson算法求最大流：

1. 建立原图流为0的余图；
2. 在余图中找出任意的s-t路径，并按该路径找出原图允许的最大流$K$：
   • 最大流$K$根据弧的容量减去已有的流；
   • 对余图的正向弧，原图的流加上$K$；
   • 对余图的反向弧，原图的流减去$K$。
3. 更新余图，重复上述过程，直到余图不存在s-t路径。

最大流最小割定理

在余图中，$s$可达的所有顶点构成的子集记为$\mathbf U$，显然$\mathbf U$中不包含$t$，否者还有s-t路径。对$\mathbf U$，以下关系成立：

1. $\forall a\in\text{out-arcs}(\mathbf U)$，必有$\text{flow}(a)=c(a)$，否则不饱和弧$a\;(0\leq\text{flow}(a) < c(a))$将在余图中连接更多的顶点，违背了$\mathbf U$是“$s$可达的所有顶点”。
2. $\forall a\in\text{in-arcs}(\mathbf U)$，必有$\text{flow}(a)=0$，否则$0 < \text{flow}(a) \leq c(a)$时存在反向弧，余图必定连接更多的顶点，违背了$\mathbf U$是“$s$可达的所有顶点”。

因此，根据流与割的关系可知，任意流不大于任意割，那么等号成立表明最大流等于最小割。最大流算法不仅找到了最大流，也找到了最小割。

参考资料