《离散数学-网络模型.ppt》由会员分享，可在线阅读，更多相关《离散数学-网络模型.ppt（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学离散数学黄晓宇黄晓宇本讲内容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,ji,j)的权的权 C Cij ij 是非负数，称为容量是非负数，称为容量n一个网络的流量是对每边赋流量值，该一个网络的流量是对每边赋流量值，该值不
2、超过所在边的容量。值不超过所在边的容量。定义（二）nG G是一个传输网络，是一个传输网络，C Cij ij是是 (i,ji,j)的容量。的容量。G G的一个流量的一个流量F F 赋予赋予 (i,ji,j)值值F Fij ij，满足：，满足：nF Fij ij C Cij ijn对非源点和收点对非源点和收点ii和和j j，有，有n中间节点的流出流量中间节点的流出流量 流入流量流入流量定义（三）n网络流量网络流量n起点起点a a的流出流量终点的流出流量终点z z的流入流量，这个流的流入流量，这个流量称作流量量称作流量F F的值的值n网络流中的核心问题：最大流量网络流中的核心问题：最大流量码头码头a
3、 a bc炼油厂炼油厂z zed5,33,22,24,22,24,32,1超级源、汇w1bABd364c4323w2w32w1bABd364c4323aw3w2z使用网络流表示问题P458：例P459：习题17最大流算法n传输网络传输网络G G的一个最大流量是具有最大值的一个最大流量是具有最大值的流量，最大流可能存在多个；的流量，最大流可能存在多个；n基本思想：从初始流量开始，反复增加，基本思想：从初始流量开始，反复增加，直至不能再增大。直至不能再增大。通路np=(vp=(v0 0,v,v1 1,v,vn n)，v v0 0=a=a，v vn n=z=z 是从是从a a到到z z的的一条通路；
4、一条通路；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,jCi,j Fi,j如果如果(i,j)一致定向的边一致定向的边Xi,j=Fi,j如果如果(i,j)是非一致定向的边是非一致定向的边n
5、令 =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,22,2b4,02,04,42,2(-,)(a,1)(a,3)(d,2)(e,2)a bced5,43,22,2b4,22,24,42,2(-,)(a,1)(a,1)