最大流（Maximum Flow）

一个菜倔强的取经之路。
为了知识的严谨性，本文相关的定义是按照算法导论(第三版) copy and paste。我的理解和总结会适当的添加在这些定义后面用来帮助大家理解。我认为一些重要东西都已经加粗和高光标记了。本文算是对这一块内容的学习总结，如有错误欢迎大家指正，交流。

1.流网络和流（Flow networks and flows）

首先我们来看看流网络和流的定义。

流网络(Flow networks):

G = ( V ， E ) G=(V，E) G=(V，E) 是一个有向图，图中每条边 ( u , v ) ∈ E (u,v) \in E (u,v)∈E 有一个非负的 容量值(Capacity) c ( u , v ) ≥ 0 c(u,v) \geq 0 c(u,v)≥0。如果边集合 E E E 包含一条边 ( u , v ) (u,v) (u,v)，则图中不存在反方向的边 ( v , u ) (v,u) (v,u)。如果 ( u , v ) ∉ E (u,v) \notin E (u,v)∈/​E，则为方便起见，定义 c ( u , v ) = 0 c(u,v)=0 c(u,v)=0，并且在图中不允许自循环(self-loop)。

在流网络中，我们需要区分两个节点: 源结点(Source) s s s 和 汇点(Sink) t t t。对于每个节点 v ∈ V v \in V v∈V，流网络都包含一条路径 s → v → t s \rightarrow v \rightarrow t s→v→t。因此, 流网络图是连通的，并且由于除源结点外的每个结点都至少有一条进入的边，我们有 ∣ E ∣ ≥ ∣ V ∣ − 1 |E| \geq |V|-1 ∣E∣≥∣V∣−1。

流(Flow):

设 G = ( V ， E ) G=(V，E) G=(V，E) 为一个流网络，其容量函数为 c c c。 设 s s s 为网络的源结点， t t t 为汇点. G G G 中的 流 是一个实值函数 f : V × V → R f: V \times V \rightarrow \mathbb {R} f:V×V→R，并且需要满足下面两条性质:

容量限制(Capacity constraint):

对于所有的结点 u , v ∈ V u,v \in V u,v∈V，要求 0 ≤ f ( u , v ) ≤ c ( u , v ) 0 \leq f(u,v) \leq c(u,v) 0≤f(u,v)≤c(u,v)。理解容量限制很简单，举个栗子，比方说电梯限载1000kg，你上去如果超重了=。=它肯定就报警不走了。所以放在流网络图上也是一样，这条边上的流量值 f ( u , v ) f(u,v) f(u,v) 不可以超过这条边的容量值 c ( u , v ) c(u,v) c(u,v)。

流量守恒(Flow conservation):

对于所有的结点 u ∈ V − { s , t } u \in V -\{s, t\} u∈V−{ s,t}，要求

∑ v ∈ V f ( v , u ) = ∑ v ∈ V f ( u , v ) \sum_{v \in V}f(v,u) = \sum_{v \in V}f(u,v) v∈V∑​f(v,u)=v∈V∑​f(u,v)
我对于流量守恒的理解就是进入一个结点的流量必须等于离开这个结点的流量。（可能有偏差，算法导论中的解释都提到了进出结点的速率，我也不太清楚怎么解释。）

当 ( u , v ) ∉ E (u,v) \notin E (u,v)∈/​E 时，从结点 u u u 到结点 v v v 之间没有流，因此 f ( u , v ) = 0 f(u,v)=0 f(u,v)=0。我们称非负数值 f ( u , v ) f(u,v) f(u,v) 为从结点 u u u 到结点 v v v 的流. 一个流 f f f 的值 ∣ f ∣ |f| ∣f∣ 定义如下:

∣ f ∣ = ∑ v ∈ V f ( s , v ) − ∑ v ∈ V f ( v , s ) |f| = \sum_{v \in V}f(s,v) - \sum_{v \in V}f(v,s) ∣f∣=v∈V∑​f(s,v)−v∈V∑​f(v,s)
也就是说，流 f f f 的值是从源结点流出的总流量减去流入源节点的总流量。( ∣ f ∣ |f| ∣f∣ 表示流的值，不是绝对值或者基数值)。通常来说，一个流网络不会有任何进入源结点的边，因此上面这个公式的求和项 ∑ v ∈ V f ( v , s ) \sum_{v \in V}f(v,s) ∑v∈V​f(v,s) 值为0，所以当我们计算流的值时，只需计算源结点流出的总流量即可。

在这里这两个 " f " "f" "f" 可能会有点绕，其实很简单， f ( u , v ) f(u,v) f(u,v) 是"流量" ; ∣ f ∣ |f| ∣f∣ 是"流的值"。 前者就是标记在图的每条边旁边的 f ( u , v ) / c ( u , v ) f(u,v)/c(u,v) f(u,v)/c(u,v) 中的 f ( u , v ) f(u,v) f(u,v)，后者则需要前者和上面这个公式计算得到。

接下来继续举一个算法导论中的栗子。


图(a)是一个流网络 G = ( V , E ) G= (V,E) G=(V,E)。在该流网络中，Vancouver 是源结点 s s s，Winnipeg 是汇点 t t t，中间途径多个城市，但是城市之间的运载量有限，每条边标明的是不同城市之间的货运容量。图(b)是 G G G 中的一个流 f f f， f = 19 f=19 f=19 (Hint:11+8)。每条边上的数字内容是 f ( u , v ) / c ( u , v ) f(u,v)/c(u,v) f(u,v)/c(u,v)，这里 “/” 只起到分隔作用，并无数学意义。

反平行(Antiparallel):

同样还是这个例子，这次我们稍做一点改变。如果我们假定货运公司要从 v 1 v_1 v1​运10个单位的货物到 v 2 v_2 v2​，这时候会出现一个问题，边 ( v 1 , v 2 ) (v_1,v_2) (v1​,v2​) 和 边 ( v 2 , v 1 ) (v_2,v_1) (v2​,v1​)用时存在，我们称这两条边为 反平行。那就违反了我们之前的定义，所以我们需要将这条边转换成等价的两条边，并且再新增加一个结点 v ′ v' v′，如下图所示：

超级源结点&超级汇点:

当我们面对的最大流问题含有多个源结点和多个汇点时，我们可以将网络转换为一个只有一个源结点和一个汇点的普通流网络。转换方法就是加入一个 超级源结点 s s s 和 超级汇点 t t t。如下图所示:

接下一篇算法笔记（Chapter26）———最大流（Maximum Flow）之Ford-Fulkerson