You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

算法 | 网络流 - Network Flow

. 3 min read

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 the
value 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