算法 | 网络流 - Network Flow

Network Flow

Flow network.

  • Abstraction for material flowing through the edges.
  • G = (V, E) = directed graph, no parallel edges. 【简单图】
  • Two distinguished nodes: s = source, t = sink.
  • c(e) = capacity of edge e.

Def:

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_\text{e out of A} c(e)$

只考虑 A -> B ,不考虑 反向

Minimum Cut Problem

Min s-t cut problem. Find an s-t cut of minimum capacity.

Def:

An s-t flow is a function that satisfies:

  • For each e ∈ E: $0 \leq f(e) \leq c(e)$ [capacity]
  • For each v ∈ V – {s, t}: $\sum_\text{e in to v} f(e) = \sum_\text{e out of v} f(e)$ [conservation]

The value of a flow f is: $v(f) = \sum_\text{e out of s} f(e)$

最终从 s 到 t 的值

Maximum Flow Problem

Max flow problem. Find s-t flow of maximum value

Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut.Then, the net flow sent across the cut is equal to the amount leaving s.$$\sum_\text{e out of A} f(e) - \sum_\text{e in to A}f(e) = v(f)$$**Weak duality.** Let f be any flow, and let (A, B) be any s-t cut. Then thevalue of the flow is at most the capacity of the cut.

容量限制,不能超过

Corollary:

Let f be any flow, and let (A, B) be any cut.

If v(f) = cap(A, B), then f is a max flow and (A, B) is a min cut.

切的时候,消耗需要考虑容积,此处最大流意味着没有更小的容积段

Residual Graph

Original 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:$$\begin{equation}c_f(e)=\left{\begin{array}{lr}\text{c(e) - c(f),}&\quad\text{if e ∈ E,}\f(e) &\quad if e^R ∈ E.\end{array}\right.\end{equation}$$

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}$.

Def:

  • An augmenting path is a simple s->t path in the residual graph $G_f$

其中一条有效流

  • The bottleneck capacity of an augmenting path P is the minimum residual capacity of any edge in P.

Key property. Let f be a flow and let P be an augmenting path in $G_f$,then after calling $f' \leftarrow Augment(f,c,P)$, the resulting f’ is flow and$$v(f’) = v(f) + bottleneck(G_f,P)$$

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

Choosing Good Augmenting Paths

Bipartite Matching