Network Flow 网络流

1.理解最大流、任意流、最小割、任意割之间的关系；

2.掌握网络最大流问题和最小割问题及其求解算法，给出一个网络能求出它的最大流或者最小割，典型考题：作业1的第4题（解题过程要列出各条增广路径）。

Flow network 流网络

A flow network is a tuple G = (V, E, s, t, c).
流网络是一个元组 G = (V, E, s, t, c)

• Digraph (V, E) with source s ∈ V and sink t ∈ V. (assume all nodes are reachable from s)
  有向图 (V, E) 有源点 s ∈ V 和汇点 t ∈ V（假设所有节点从s可达）
• Capacity c(e) > 0 for each e ∈ E.
  E中每个边e拥有容量c(e)

Intuition. Material flowing through a transportation network; material originates at source and is sent to sink.
直觉：材料通过运输网络；材料从源头开始，然后被送到汇点。

问题 > Maximum-flow problem 最大流问题

Flow 流

Def. An st-flow (flow) f is a function that satisfies:
定义：一个st流（下称流）f是一个满足下面条件的函数：

• For each e ∈ E : [capacity]
  不超过边的容量
• For each v ∈ V – {s, t} : [flow conservation]
  除源点和汇点以外，点的流出与流入相等

The value of a Flow 流的值

Def. The value of a flow f is:
定义：流f的值是源点的流出-流入

Max-flow problem 最大流问题

Max-flow problem. Find a flow of maximum value.
最大流问题：找到值最大的流

算法 > Toward a max-flow algorithm 尝试求解最大流的算法

Greedy algorithm 贪心算法（失败）

・Start with f (e) = 0 for each edge e ∈ E.
・Find an s→t path P where each edge has f (e) < c(e).
・Augment flow along path P.
・Repeat until you get stuck.

Why the greedy algorithm fails 为什么贪心算法失败

Q. Why does the greedy algorithm fail?

A. Once greedy algorithm increases flow on an edge, it never decreases it.
答：因为贪心算法从来没有减少边的流量

Bottom line 关键

Need some mechanism to “undo” a bad decision.
需要一个机制“撤销”坏决策

★算法 > Ford–Fulkerson algorithm（Ford-Fulkerson算法求解最大流问题）

Residual network 剩余网络

Original edge 原始边 e

e = (u, v) ∈ E.
来自E的边e = (u, v)有两个属性：

• Flow f(e).
  流量f(e)
• Capacity c(e).
  容量c(e)

Reverse edge 反向边 e^reverse

e^reverse = (v, u).
反向边e^reverse = (v, u)（和原始边的节点不变，方向相反）

• “Undo” flow sent.
  用于撤销流出的流量

Residual capacity 剩余容量 c_f(e)

if e ∈ E, c_f(e) = c(e) - f(e)
如果是原始边，剩余容量等于容量-流量

if e^reverse ∈ E, c_f(e) = f(e)
如果是反向边，剩余容量等于流量

Residual network 剩余网络 G_f

G_f = (V, E_f , s, t, c_f ).
剩余网络G_f由顶点集V、剩余边集E_f、源点s、汇点t、剩余容量c_f组成

• E_f = {e : f (e) < c(e)} ∪ {e_reverse : f (e) > 0}.
  剩余边集E_f由 原始边中剩余容量大于0的边 和 反向边中剩余容量大于0的边 组成
• Key property: f ʹ is a flow in G_f iff f + f ʹ is a flow in G.
  关键属性：fʹ是G_f中的流 当且仅当 f + fʹ是G中的流（剩余网络中的流可以加到原始网络的流中，正向添加流量，反向减少流量，结果仍然是原始网络的流）

Augmenting path 增广路径

Def. An augmenting path is a simple s→t path in the residual network G_f .
定义：增广路径是剩余网络G_f中s→t的简单路径

Def. The bottleneck capacity of an augmenting path P is the minimum residual capacity of any edge in P.
定义：增广路径P的瓶颈容量是P中任何边的最小剩余容量

Key property. Let f be a flow and let P be an augmenting path in G_f.
关键属性：f是一个流，P是剩余网络G_f的增广路径
Then, after calling f ʹ ← AUGMENT(f, c, P), the resulting f ʹ is a flow and val( f ʹ) = val( f) + bottleneck(Gf, P).
f'为添加加入增广路径后的流，f'的值=f的值+增广路径P的瓶颈容量

Augmenting path theorem 增广路径定理

Augmenting path theorem. A flow f is a max flow iff no augmenting paths.
增广路径定理：流f是最大流当且仅当没有增广路径

Ford–Fulkerson algorithm (Ford–Fulkerson算法)

Ford–Fulkerson augmenting path algorithm.
Ford–Fulkerson增广路径算法：

• Start with f (e) = 0 for each edge e ∈ E.
  开始每条边的流量是0
• Find an s↝t path P in the residual network G_f .
  在剩余网络G_f中找到s↝t的路径P
• Augment flow along path P.
  将P加入流
• Repeat until you get stuck.
  重复直到剩余网络中没有s↝t的路径

问题 > Minimum-cut problem 最小割问题

Cut 割

Def. An st-cut (cut) is a partition (A, B) of the nodes with s ∈ A and t ∈ B.
定义：一个st割（下称割）是对节点的划分(A, B)，其中源点s在A中，汇点t在B中

Capacity 割的容量

Def. Its capacity is the sum of the capacities of the edges from A to B.
定义：割的容量是从A到B的边（从A流出的边）的容量之和

don’t include edges from B to A
不包括从B到A的边

Minimum-cut problem 最小割问题

Min-cut problem. Find a cut of minimum capacity.
最小割问题：找到最小容量的割

★Max-flow min-cut theorem 最大流和最小割定理

Relationship between flows and cuts 最大流和最小割的关系

Flow value lemma. Let f be any flow and let (A, B) be any cut. Then, the value of the flow f equals the net flow across the cut (A, B).
流值引理：设f为任意流，设(A, B)为任意割。则流f的值等于穿过割(A, B)的净流量（流出A的流量-流入A的流量）。

证明：

Weak duality. Let f be any flow and (A, B) be any cut. Then, val(f) ≤ cap(A, B).
弱对偶：设f为任意流，设(A, B)为任意割。流f的值小于等于割(A, B)的容量。

Certificate of optimality 最优性证明

Corollary. Let f be a flow and let (A, B) be any cut.
推论：设f为任意流，设(A, B)为任意割
If val(f) = cap(A, B), then f is a max flow and (A, B) is a min cut.
如果流f的值等于割(A, B)的容量，那么f是最大流，(A, B)是最小割

证明：
任意流的值小于等于割(A, B)的容量，又流f的值等于割(A, B)的容量，故f是最大流
任意割的值大于等于流f的值，又流f的值等于割(A, B)的容量，故(A, B)是最小割

Max-flow min-cut theorem 最大流和最小割定理

Max-flow min-cut theorem. Value of a max flow = capacity of a min cut. (strong duality)
最大流和最小割定理：最大流的值 = 最小割的容量（强对偶）

Pf. The following three conditions are equivalent for any flow f :
对于任意流f，以下三个条件等价

• i. There exists a cut (A, B) such that cap(A, B) = val(f).
  存在割(A, B)，它的容量等于流f的值
• ii. f is a max flow.
  f是最大流
• iii. There is no augmenting path with respect to f. (if Ford–Fulkerson terminates, then f is max flow)
  没有关于f的增广路径（如果Ford–Fulkerson算法结束，f是最大流）

[ i ⇒ ii ]
・This is the weak duality corollary.

[ ii ⇒ iii ] We prove contrapositive: ¬ iii ⇒ ¬ ii.
・Suppose that there is an augmenting path with respect to f.
・Can improve flow f by sending flow along this path.
・Thus, f is not a max flow.

[ iii ⇒ i ]
・Let f be a flow with no augmenting paths.
・Let A be set of nodes reachable from s in residual network Gf.
・By definition of A: s ∈ A.
・By definition of flow f: t ∉ A.

Capacity-scaling algorithm 容量缩放算法

Analysis of Ford–Fulkerson algorithm (when capacities are integral) 分析Ford–Fulkerson算法（当容量是整数时）

Assumption. Every edge capacity c(e) is an integer between 1 and C.
假设：每条边的c(e)容量是1到C之间的整数

Integrality invariant. Throughout Ford–Fulkerson, every edge flow f(e) and residual capacity c_f(e) is an integer.
整数性不变：在整个Ford–Fulkerson算法中，每条边的流量f(e)和剩余流量c_f(e)是整数。

Pf. By induction on the number of augmenting paths.
证明：通过对增广路径数量的归纳

Theorem. Ford–Fulkerson terminates after at most val(f *) ≤ n C augmenting paths, where f * is a max flow. (consider cut A = { s } (assumes no parallel edges))
定理：Ford–Fulkerson算法最多在val(f*)个增广路径后结束，f*是最大流，val(f*)是最大流的值，val(f *) ≤ n C（考虑割A只有一个顶点s，假设没有平行边）

Pf. Each augmentation increases the value of the flow by at least 1.
证明：每个增广路径至少使流的值增加1

Corollary. The running time of Ford–Fulkerson is O(m n C).
推论：Ford–Fulkerson算法的运行时间是O(m n C)

Pf. Can use either BFS or DFS to find an augmenting path in O(m) time.
证明：使用深度或广度优先遍历可以在O(m)时间内找到一条增广路径

Integrality theorem. There exists an integral max flow f *. (f(e) is an integer for every e)
整性定理：存在整数最大流f*（每条边的流量都是整数）

Pf. Since Ford–Fulkerson terminates, theorem follows from integrality invariant (and augmenting path theorem).
来自整数性不变（和增广路径定理）

Ford–Fulkerson: exponential example (Ford–Fulkerson算法的指数实例)

Q. Is generic Ford–Fulkerson algorithm poly-time in input size?
问：普通Ford–Fulkerson算法是多项式时间的吗？

A. No. If max capacity is C, then algorithm can take ≥ C iterations.
答：否。如果最大容量是C，算法可能花费大于等于C次迭代

Choosing good augmenting paths 选择好的增广路径

Use care when selecting augmenting paths.

• Some choices lead to exponential algorithms.
• Clever choices lead to polynomial algorithms.

Pathology. When edge capacities can be irrational, no guarantee that Ford–Fulkerson terminates (or converges to a maximum flow)!

Goal. Choose augmenting paths so that:

• Can find augmenting paths efficiently.
• Few iterations.

Choose augmenting paths with:

• Max bottleneck capacity (“fattest”).
• Sufficiently large bottleneck capacity.
• Fewest edges.

Capacity-scaling algorithm 容量缩放算法

Overview. Choosing augmenting paths with “large” bottleneck capacity. (though not necessarily largest)
概述：选择具有“大”瓶颈容量的增广路径（虽然不一定是最大的）

• Maintain scaling parameter Δ.
  维护一个缩放参数Δ

• Let G_f (Δ) be the part of the residual network containing only those edges with capacity ≥ Δ.
  让G_f(Δ)是剩余网络中仅包含那些具有容量≥Δ的边

• Any augmenting path in G_f(Δ) has bottleneck capacity ≥ Δ.
  G_f(Δ)中任何增广路径的瓶颈容量都≥ Δ

Proof of correctness 证明正确性

Analysis of running time 分析运行时间