离散数学网络模型.pptVIP

离散数学 黄晓宇 HuangSir@ 本讲内容 网络模型的基本概念 最大流算法 最大流最小割 匹配 引例 定义 定义（二） 定义（三） 超级源、汇 使用网络流表示问题 P458：例10.1.9 P459：习题1～7 最大流算法 传输网络G的一个最大流量是具有最大值的流量，最大流可能存在多个； 基本思想：从初始流量开始，反复增加，直至不能再增大。 通路 p= (v0, v1, …, vn)，v0=a，vn=z 是从a到z的一条通路； 如果在p中边e是从 vi-1 指向 vi 则称是定向的，否则称是非定向的 通路（a?z） 四种情况 定义 设P是网络G中从 a 到 z 的通路，其中容量为 C，流量为 F, 满足： 对P中定向的边 (i,j), Fi,j Ci,j 对P中非定向的边 (i,j), 0 Fi,j Ci,j – Fi,j如果(i,j)一致定向的边 Xi,j = Fi,j如果(i,j)是非一致定向的边 令 ? = mini {Xi,j} i,j= 1,...,n 定义 Fi,j*= Fi,j (i,j) 不在 P中 Fi,j + ? (i,j)是P中定向的边 Fi,j - ? (i,j)是P中非定向的边 则F* = {Fi,j*} 是一个流量比 F 增值 ?d的流. 算法思想 从流量0开始 查找满足定理的通路，如果不存在，结束，流量就是最大的 通路增加流量?，goto 2 输入：网络G，容量C，a,z,n 输出：最大流量F Procedure max_flow(a,z,C,v,n) // v的标记为 (predecessor(v)/前趋结点，val(v)/结点v的流量增量 * * b c 码头a 炼油厂z e d 5 3 2 4 2 4 2 求出从码头到炼油厂的最大流量 一个传输网络是一个满足下列条件的简单加权有向图 一个源 一个汇 有向边(i,j)的权 Cij 是非负数，称为容量 一个网络的流量是对每边赋流量值，该值不超过所在边的容量。 G是一个传输网络， Cij是 (i,j)的容量。 G的一个流量F 赋予 (i,j) 值Fij，满足： Fij ≤ Cij 对非源点和收点i和j，有 中间节点的流出流量 ＝流入流量 网络流量 起点a的流出流量＝终点z的流入流量，这个流量称作流量F的值 网络流中的核心问题：最大流量 码头a b c 炼油厂z e d 5,3 3,2 2,2 4,2 2,2 4,3 2,1 w1 b A B d 3 6 4 c 4 3 2 3 w2 w3 2 w1 b A B d 3 6 4 c 4 3 2 3 a w3 w2 z ∞ ∞ ∞ ∞ ∞ 3，1 4，1 3，2 5，1 3，2 4，0 3，3 5，2 //没有新的通路 //正向边 //反向边 //增量F *