运筹学最大流问题.ppt

§4最大流 定义 列出图示网络全部割 4-3、最大流-最小割定理 4-4、求最大流的标号算法 2. 调整过程 作 业 图 例14_A 例14_B 例14_C 四、最大匹配问题 例15 * 定义 有向连通图G=(V, E), G的每条边(vi , v j)[称作弧]上有 c i j 称为边的容量, 仅有一个入次为0的点v i 称为 中间点, 这样的网络G称为容量网络,常记为 G = ( V, E, C ) . 对任一G中的边 (vi , v j) 有流量 f i j , 称为集合 f = { f i j }为 网络G上的一个流。 称满足下列条件的流 f 为可行流： (1)容量限制条件: 对G中每条边(vi, vj), 有0≤fij ≤ cij; j k (2)平衡条件: 对中间点 v i , ∑ f i j = ∑ f k j (即中间点v i 的输入量与输出量相等). (即从v s 点发出总量等于v t与输入总量相等). i 对 收、发点 vi , vj , 有 ∑ f s i = ∑ f j t j 一、最大流有关概念 非负权, 发点(源), 一个入次为0的点vi 称为收点(汇), 其余的点称为 容量网络G=(V, E, C), vi , v j 收、发点, 若有 边集E’ 为E的子集, 将G分为两个子图G1,G2, 其顶点集合分别记S, ② E’’为E’的真子集, 而 G(V, E - E’’)仍连通, ① G(V, E-E’) 不连通; 则称E’为G的割集, 记 E ’ = ( S, S ). S, S∪S=V, S∩S=⊙, vi, vj 分属S, S, 满足 割集( S, S )中所有始点在S, 终点在S的边的容量之和, 称为割集容量, 记为 C( S, S ) . 一个流f={ f i j }, f i j =c i j , 则称流 f 对边(vi, vj)是饱和的. 边上数字为 c i j(f i j ) . 9(4) s v3 v4 v1 v2 7(5) 2(0) 9(9) 10(8) 8(8) 5(5) t V V s, v1, v2, v3, v4 t s, v1, v2, v4 s, v1, v2, v3 s, v2, v4 s, v1, v3 s, v1, v2 s, v2 s, v1 s v1, v2, v3, v4, t v2, v3, v4, t v1, v3, v4, t v3, v4, t v2, v4, t v1, v3, t v4, t v3, t (s,1) (s,2) (s,2) (1,2) (s,1) (1,3) (s,1) (2,4) (s,2) (4,t) (1,3) (2,4) (4,3) (1,2) (3,2) (3,t) (2,4) (3,t) (4,3) (4,t) (1,3) (3,t) 15 (4,t) 21 17 18 19 24 14 25 15 割 容量 定理 定理2 (最大流-最小割定理) 任一网络G中, 从vs 到 vt 的 定义 设 f 为网络G=(V, E, C)的任一可行流, 流量为W , (S, S )是分离 vs , vt 的任一割集, 则有 W≤C (S, S ). 容量网络G, 若μ为网络中从 vs 到 vt 的一条链, 给 μ定向为从 vs 到 vt , μ上的边凡与μ同向称为前向边, 凡 与μ反向的称为后向边，其集合分别用μ+和μ-表示, f 是 一个可行流, 如果满足 0 ≤ f i j c i j (vi , v j ) ∈μ+ c i j ≥ f i j 0 (vi , v j ) ∈μ- 则称μ为从 v s 到 v t 的(关于 f )的可增广链 . 最大流的流量等于分离 vs , vt 的最小割的容量. 推论 可行流f是最大流的充要条件是不存在从vs 到 vt 的(关于f 的)可增广链. 若vt得到标号, 说明存在一条可增广链, 转(第2步)调整过程. ⑴给发点vs以标号(0, +∞). ⑵选择一个已标号的顶点 vi , 对于vi ,的所有未给标号的邻 (a)若边(vj ,vi )∈E, 且 f j i 0 , 则令δj =min ( f j i , δj ) , 并给 v j 以标号( - v i , δj ). 1. 标号过程 (b)若边(vi ,vj )∈E, 且 f i j c i j 时, 令δj =min ( c i j - f i j , δi ) , 并给 v j 以标号( + v i , δj ). ⑶重复⑵直到收点 vt 被标号或不再有顶点可标号为止. 若vt未得到标号, 标号过程已无法继续, 说明 f 已是最大流.