离散数学-网络模型-(2)市公开课一等奖省赛课获奖课件_第1页
离散数学-网络模型-(2)市公开课一等奖省赛课获奖课件_第2页
离散数学-网络模型-(2)市公开课一等奖省赛课获奖课件_第3页
离散数学-网络模型-(2)市公开课一等奖省赛课获奖课件_第4页
离散数学-网络模型-(2)市公开课一等奖省赛课获奖课件_第5页
已阅读5页，还剩19页未读， 继续免费阅读

付费下载

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

离散数学黄晓宇HuangSir@第1页本讲内容网络模型基本概念最大流算法最大流最小割匹配第2页引例bc码头a炼油厂zed5324242求出从码头到炼油厂最大流量第3页定义一个传输网络是一个满足以下条件简单加权有向图一个源一个汇有向边(i,j)权Cij是非负数，称为容量一个网络流量是对每边赋流量值，该值不超出所在边容量。第4页定义（二）G是一个传输网络，Cij是(i,j)容量。G一个流量F赋予(i,j)值Fij，满足：Fij

≤Cij对非源点和收点i和j，有中间节点流出流量＝流入流量第5页定义（三）网络流量起点a流出流量＝终点z流入流量，这个流量称作流量F值网络流中关键问题：最大流量码头a

bc炼油厂zed5,33,22,24,22,24,32,1第6页超级源、汇w1bABd364c4323w2w32w1bABd364c4323aw3w2z∞∞∞∞∞第7页使用网络流表示问题P458：例10.1.9P459：习题1～7第8页最大流算法传输网络G一个最大流量是含有最大值流量，最大流可能存在多个；基本思想：从初始流量开始，重复增加，直至不能再增大。第9页通路p=(v0,v1,…,vn)，v0=a，vn=z是从a到z一条通路；假如在p中边e是从vi-1指向vi则称是定向，不然称是非定向第10页通路（a

z）第11页四种情况3，14，13，25，13，24，03，35，2第12页定义设P是网络G中从a到z通路，其中容量为C，流量为F,满足：对P中定向边(i,j),Fi,j<Ci,j对P中非定向边(i,j),0<Fi,jCi,j–Fi,j假如(i,j)一致定向边Xi,j=Fi,j假如(i,j)是非一致定向边第13页令∆=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流.第14页算法思想从流量0开始查找满足定理通路，假如不存在，结束，流量就是最大通路增加流量∆，goto2第15页输入：网络G，容量C，a,z,n输出：最大流量FProceduremax_flow(a,z,C,v,n)//v标识为(predecessor(v)/前趋结点，val(v)/结点v流量增量第16页第17页//没有新通路第18页//正向边第19页//反向边第20页第21页//增量F第22页abced5,03,02,0b4,02,04,02,0(-,

∞)(a,

3)(b,

2)(a,

5)(c,

2)abced5,03,22,2b4,02,04,22,0(-,

∞)(a,

1)(d,

2)(a,

5)(d,

2)(c,

2)第23页abced5,23,22,2b4,02,04,42,2(-,

∞)(a,

1)(a,

3)(d,

2)(e,

人人文库> 全部分类> 应用文书 > 作业报告

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论