Emends-Karp修改标号法: 在Ford- Fulkerson标号算法的第2步检查已标顶点时,采用“先标先查”规则。 例 1000Y31000 1000 v21000v4100016 ①先标先查规则,相当于执行广探法 ②先标先査规则执行的结果相当于求x到y的最短可增路(层层推进策略) ③ Emends-Kap修改标号法是有效算法弧容量是有理数时),其计算复杂性为O(vE2) §93求最大流的 Dinic算法 增量网络 定义9.3.1对于网络N=(V,x,y,A,C)和N上的一个可行流f,构造一个新的网络N(f=(V,x,y,A(f C),其中A(f)及容量函数C定义如下 (1)若(,v)∈A且f(u,v)<C(u,v),则(,v)∈A(f),且C(u,v)=C(u,yv)-f(,v) (2)若(l,v)∈A且f(u,v)>0,则(v,a)∈A(∫),且C'(v,a)=f(l,v) 这样构造的网络N(∫称为网络N关于流∫的增量网络。 例: 2(3) 网络N及其一个可行流∫,弧上括号 增量网络N 外数字为流量,括号内数字为容量。 注 (1)对应于N的每条饱和弧(,v),N(O中只有一条弧(v,4),c(v,u)=c(l,v)=f(l,v); 对应于N的每条零流弧(,v),N()中只有一条弧(u,y),c(u,v)=c(,v)=c(u,v)-f(u,v) 对应于N的每条非零流非饱和弧(u,v),N(f)中有两条弧(u,v)和(v,u),c(l,v)=c(u,v)-f(,v) c(v, u)=f(u, v) (2)N()中每条弧的容量恰为N中相应弧的流可增量。 (3)严格来讲,增量网络不符合前述网络的定义(无出度为0的点(源)和入度为0的点(汇),但因它是在 原网络N基础上定义的,有明显的源和汇的痕迹,因此我们仍将其看作网络,其中x和y分别为源和 汇,该网络上的一个可行流∫定义为满足Edmends－Karp 修改标号法： 在 Ford－Fulkerson 标号算法的第 2 步检查已标顶点时，采用“先标先查”规则。 例： 注： ① 先标先查规则，相当于执行广探法； ② 先标先查规则执行的结果相当于求 x 到 y 的最短可增路(层层推进策略)； ③ Edmends－Karp 修改标号法是有效算法(弧容量是有理数时)，其计算复杂性为 2 O( ) ν ⋅ε 。 §9.3 求最大流的 Dinic 算法 一、增量网络 定义 9.3.1 对于网络 N = (V, x, y, A, C)和 N 上的一个可行流 f，构造一个新的网络 N ( f )= (V, x, y, A( f ), C′ )，其中 A( f )及容量函数 C′ 定义如下： (1) 若( ) u,v A ∈ 且 f (,) (,) uv Cuv < ，则(,) ( ) uv A f ∈ ，且C uv Cuv f uv ′(,) (,) (,) = − ； (2) 若( ) u,v A ∈ 且 f uv (,) 0 > ，则(, ) ( ) vu A f ∈ ，且C vu f uv ′(, ) (, ) = 。 这样构造的网络 N ( f )称为网络 N 关于流 f 的增量网络。 例： 注： (1) 对应于 N 的每条饱和弧(u, v)，N ( f )中只有一条弧(v, u)，c vu cuv f uv ′(, ) (, ) (, ) = = ； 对应于 N 的每条零流弧(u, v)，N ( f )中只有一条弧(u, v)， c uv cuv cuv f uv ′(,) (,) (,) (,) = = − ； 对应于 N 的每条非零流非饱和弧(u, v)，N ( f )中有两条弧(u, v)和(v, u), c uv cuv f uv ′(,) (,) (,) = − , c vu f uv ′(, ) (, ) = 。 (2) N ( f )中每条弧的容量恰为 N 中相应弧的流可增量。 (3) 严格来讲，增量网络不符合前述网络的定义(无出度为 0 的点(源)和入度为 0 的点(汇))，但因它是在 原网络 N 基础上定义的，有明显的源和汇的痕迹，因此我们仍将其看作网络，其中 x 和 y 分别为源和 汇，该网络上的一个可行流 f 定义为满足 网络 N 及其一个可行流 f ，弧上括号 外数字为流量，括号内数字为容量。 2(2) 1(2) 2(3) 0(1) 2(3) 0(2) 1(3) x y 增量网络 N(f)。 2 1 1 1 1 2 2 x y 1 1 2 2 v3 v2 v4 v1 1000 1000 1000 1000 v5 x y v6 1000 1000 1000 1000 1