离散数学-网络模型

1、离散数学离散数学黄晓宇黄晓宇HuangSHuangS本讲内容n 网络模型的基本概念网络模型的基本概念n 最大流算法最大流算法n 最大流最小割最大流最小割n 匹配匹配引例b bc码头码头a a 炼油厂炼油厂z ze ed d5 53 32 24 42 24 42 2求出从码头到炼油厂的最大流量求出从码头到炼油厂的最大流量定义n一个传输网络是一个满足下列条件的简一个传输网络是一个满足下列条件的简单加权有向图单加权有向图1. 1. 一个源一个源2.2. 一个汇一个汇3. 3. 有向边有向边(i,j(i,j) )的权的权 C Cij ij 是非负数，称为容量是非负数，称为容量n一个网络的流量是对每边赋

2、流量值，该一个网络的流量是对每边赋流量值，该值不超过所在边的容量。值不超过所在边的容量。定义（二）nG G是一个传输网络，是一个传输网络， C Cij ij是是 (i,j(i,j) )的容量。的容量。 G G的一个流量的一个流量F F 赋予赋予 (i,j(i,j) ) 值值F Fij ij，满足：，满足：nF Fij ij C Cij ijn对非源点和收点对非源点和收点ii和和j j，有，有iijjijFFn中间节点的流出流量中间节点的流出流量 流入流量流入流量定义（三）n网络流量网络流量n起点起点a a的流出流量终点的流出流量终点z z的流入流量，这个流的流入流量，这个流量称作流量量称作流量

3、F F的值的值n网络流中的核心问题：最大流量网络流中的核心问题：最大流量码头码头a a bc炼油厂炼油厂z zed5,33,22,24,22,24,32,1超级源、汇w1bABd364c4323w2w32w1bABd364c4323aw3w2z使用网络流表示问题P458：例10.1.9P459：习题17最大流算法n传输网络传输网络G G的一个最大流量是具有最大值的一个最大流量是具有最大值的流量，最大流可能存在多个；的流量，最大流可能存在多个；n基本思想：从初始流量开始，反复增加，基本思想：从初始流量开始，反复增加，直至不能再增大。直至不能再增大。通路np= (vp= (v0 0, v, v1

4、1, , , v, vn n) )，v v0 0=a=a，v vn n=z =z 是从是从a a到到z z的一条通路；的一条通路；n如果在如果在p p中边中边e e是从是从 v vi-1i-1 指向指向 v vi i 则称是定则称是定向的，否则称是非定向的向的，否则称是非定向的通路（az）四种情况3，14，13，25，13，24，03，35，2定义n设设P是网络是网络G中从中从 a 到到 z 的通路，其中容的通路，其中容量为量为 C，流量为，流量为 F, 满足：满足：I.对对P中定向的边中定向的边 (i,j), Fi,j Ci,jII. 对对P中非定向的边中非定向的边 (i,j), 0 Fi,

5、jCi,j Fi,j如果如果(i,j)一致定向的边一致定向的边Xi,j =Fi,j如果如果(i,j)是非一致定向的边是非一致定向的边n令 = mini Xi,j i,j= 1,.,n n定义 Fi,j*=Fi,j (i,j) 不在 P中Fi,j + (i,j)是P中定向的边 Fi,j - (i,j)是P中非定向的边 则F* = Fi,j* 是一个流量比 F 增值 d的流.算法思想1. 从流量0开始2. 查找满足定理的通路，如果不存在，结束，流量就是最大的3. 通路增加流量，goto 2n输入：网络G，容量C，a,z,nn输出：最大流量FnProcedure max_flow(a,z,C,v,n)n/ v的标记为的标记为 (predecessor(v)/前趋结点，前趋结点，val(v)/结点结点v的流量增的流量增量量/没有新的通路没有新的通路/正向边正向边/反向边反向边/增量增量F Fa bced5,03,02,0b4,02,04,02,0(-, )(a, 3)(b, 2)(a, 5)(c, 2)a bced5,03,22,2b4,02,04,22,0(-, )(a, 1)(d, 2)(a, 5)(d, 2)(c, 2)a bced5,23,2