算法设计与分析笔记0x09 —— 网络流

Max-flow and Ford-Fulkerson Algorithm

  • 网络流是一个有向图,源点s,汇点t
  • 每条边流量f(e)不能超过容量c(e)
  • 守恒: 指向结点的流量之和($\sum_{e\,in\,to\, v}f(e)=\sum_{e\,out\,of\,v}f(e)$)等于流出结点的流量之和 (except source and sink points)
  • 流的值: 流出源点的流量综合 $v(f)=\sum_{e\,out\,of\,s}f(e)$.
  • Max flow problem 找到 s-t flow 使其流的值最大
  • Greedy algorithm: 局部最优, 非全局最优.
    • Start with f(e) = 0 for all 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.

Residual Graph

Origin edge e = (u, v) ∈ E.

  • Flow f(e), capacity c(e).

Residual edge

  • “Undo” flow sent.
  • $e = (u, v)$ and $e^R = (v, u)$.
  • Residual capacity:
    • $c_f(e)=c(e)-f(e)$, if $e\in E$
    • $c_f(e)=f(e)$, if $e^R\in E$

Residual graph $G_f=(V,E_f)$.

  • Residual edges with positive residual capacity.
  • $E_f = {e : f(e) < c(e)} \cup {e^R : f(e) > 0}$. When edge weights zero, reverse it.

Augmenting Path(增广路径) A simple s-t path P in the residual graph $G_f$.

Bottleneck capacity of an augmenting path P is the minimum residual capacity of any edge in P

Ford-Fulkerson Algorithm

  • Start with f(e) = 0 for all edge e ∈ E.
  • Find an augmenting path P in the residual graph $G_f$.
  • Augment flow along path P.
  • Repeat until you get stuck.

Max-flow and Min-cut

Cuts

  • An s-t cut is a partition (A, B) of V with s ∈ A and t ∈ B.
  • The capacity of a cut (A,B) is $cap(A,B)=\sum_{e\,out\,of\,A}c(e)$.

Min s-t cut problem 找到最小 s-t cut

Flow value lemma 进流量-出流量=流的值
$$\sum_{e\,out\,of\,A}f(e)-\sum_{e\,in\,to\,A}f(e)=v(f)$$
Pf.

  • $v(f)=\sum_{e\,out\,of\,s}f(e)$
  • $=\sum_{v\in A}(\sum_{e\,out\,of\,v}f(e)-\sum_{e\,in\,to\,v}f(e))$
  • $=\sum_{e\,out\,of\,A}f(e)-\sum_{e\,in\,to\,A}f(e)$

Weak duality 任意流的值小于等于任意cut的值。$v(f)\leq cap(A,B)$
Pf.

  • $v(f)=\sum_{e\,out\,of\,A}f(e)-\sum_{e\,in\,to\,A}f(e)$
  • $\leq \sum_{e\,out\,of\,A}f(e)$
  • $\leq \sum_{e\,out\,of\,A}c(e)$
  • $=cap(A,B)$

Max-Flow Min-Cut Theorem

Augmenting path theorem Flow f is a max flow iff there are no augmenting paths.
Max-flow min-cut theorem The value of the max flow is equal to the value of the min cut.

Proof strategy We prove both simultaneously by showing the equivalence of the following three conditions for any flow f:

  • (i) There exists a cut (A, B) such that v(f) = cap(A, B).
  • (ii) Flow f is a max flow.
  • (iii) There is no augmenting path relative to f.

(i) => (ii) This was the corollary to weak duality lemma.

(ii) => (iii) We show contrapositive.

  • If there exists an augmenting path, then we can improve f by sending flow along path.

(iii) => (i)

  • Let f be a flow with no augmenting paths.
  • Let A be set of vertices reachable from s in residual graph.
  • By definition of A, s ∈ A.
  • By definition of f, t ∉ A.
  • $v(f)=\sum_{e\,out\,of\,A}f(e)-\sum_{e\,in\,to\,A}f(e)$
  • $= \sum_{e\,out\,of\,A}c(e)$
  • $=cap(A,B)$

Choose Good Augmenting Path

  • Assumption: all capacities are integers between 1 and C.
  • Integrality theorem: If all capacities are integers, then there exists a max flow f for which every flow value f(e) is an integer.
  • The algorithm terminates in at most v(f*) <= nC iterations.
  • Running time of Ford-Fulkerson is O(mnC). m edges n nodes

Choose augmenting paths with:

  • Max bottleneck capacity.
  • Fewest number of edges.
  • Sufficiently large bottleneck capacity.

Capacity Scaling

Intuition. Choosing path with high bottleneck capacity

  • Maintain scaling parameter $\Delta$.
  • Let $G_f(\Delta)$ be the subgraph of the residual graph consisting of only arcs with capacity at least $\Delta$.

Lemma 1 The outer while loop repeats $1 + \lfloor log_2 C\rfloor$ times.

  • Pf. Initially $C/2 < \Delta \leq C$. $\Delta$ decreases by a factor of 2 each iteration.

Lemma 2 Let f be the flow at the end of a $\Delta$-scaling phase. Then the value of the maximum flow is at most $v(f) + m\Delta$.

  • Pf.
    • We show that at the end of a $\Delta$-phase, there exists a cut (A, B) such that $cap(A, B)\leq v(f) + m\Delta$.
    • Choose A to be the set of nodes reachable from s in $G_f(\Delta)$.
    • By definition of A, s ∈ A.
    • By definition of f, t ∉ A.
    • $v(f)=\sum_{e\,out\,of\,A}f(e)-\sum_{e\,in\,to\,A}f(e)$
    • $\geq \sum_{e\,out\,of\,A}(c(e)-\Delta)-\sum_{e\,in\,to\,A}\Delta$
    • $=\sum_{e\,out\,of\,A}c(e)-\sum_{e\,out\,of\,A}\Delta-\sum_{e\,in\,to\,A}\Delta$
    • $\geq cap(A,B)-m\Delta$

Lemma 3 There are at most 2m augmentations per scaling phase.

  • Let f be the flow at the end of the previous scaling phase.
  • Lemma 2 => $v(f*) \leq v(f) + m(2\Delta)$.
  • Each augmentation in a $\Delta$-phase increases v(f) by at least $\Delta$.

Theorem The scaling max-flow algorithm finds a max flow in $O(m log C)$ augmentations. It can be implemented to run in $O(m^2 logC)$ time.

Leave a Reply

Your email address will not be published.