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
