文档介绍：网络流算法
高文宇
gwyy@
1
流网络
流网络 work G = (V, E) 是一个有向图,它的每一条边(u, v) ∈E 有一个非负的容量 capacity c(u, v) ≥ 0。若(u, v) ∉ E,我们规定 c(u, v) = 0。在流网络中有两个特殊的节点,即源点 s 和汇点 t。
2
流网络的特性
设流网络 G = (V, E) 具有容量函数 c,s 为源点 t 为汇点,G中的一个流flow 是一个实函数 f : V × V → R ,且满足以下特性:
Capacity constraint: For all u, v ∈ V, we require f (u, v) ≤ c(u, v).
Skew symmetry: For all u, v ∈ V, we require f (u, v) = - f (v, u).
Flow conservation: For all u ∈ V - {s, t}, we require: ∑f (u, v) = 0
3
流网络和流
求最大流:在不违背容量限制的条件下,把物质从源点传输到汇点的最大速率是多少。
4
求最大流的困难所在
贪心或随机的策略都可能导致先选择红色路径,则最终得到的流的大小最多为5。
5
:
设G = (V, E)是一个流网络,f 是G中的一个流,则有下列的等式成立:
1. For all X ⊆ V, we have f(X, X) = 0.
2. For all X, Y ⊆ V, we have f(X, Y) = - f (Y, X).
3. For all X, Y, Z ⊆ V with X ∩ Y = Ø, we have the sums f(X∪Y, Z) =f(X, Z) + f(Y, Z) and f(Z, X∪Y) = f (Z, X) + f(Z, Y).
7
思考题
-8,最大流与线性规划
-9,
8
Ford-Fulkerson方法
残留网络(work),残留容量:
残留容量cf (u, v) = c (u, v) - f (u, v) . 提供了一种途径,允许对所做选择进行“后悔”处理。
给定一个流网络G = (V, E) 和流 f,由f诱导的G的残留网络是Gf = (V, Ef), ,其中:Ef = {(u, v) ∈ V × V : cf(u, v) > 0} 。即,在残留网络中,每条边都容纳一个大于0的网络流。
9
增广路径
增广路径(Augmenting path)
给定流网络 G = (V, E) 和一个流 f,增广路径 p 是残留网络Gf 中一条从 s 到 t 的简单路径。
称能够沿一条增广路径 p的每条边传输的网络流的最大量为p的残留容量,定义如下:
cf (p) = min {cf(u, v) : (u, v) is on p}.
Corollary :Let G = (V, E) be a work, let f be a flow in G, and let p be an augmenting path in Gf. Let fp be defined as in equation (). Define a function f' : V × V → R by f' = f + fp. Then f' is a flow in G with value |f'| = |f| + |fp| > |f|.
10