版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
离散数学黄晓宇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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 主播艺人合同范本
- 清洗电动车活动方案及流程
- 教科版五年级科学下册第四单元《热》背背默默知识点
- 2024年房地产销售述职报告样本(3篇)
- 2025届江苏省太仓市数学八年级第一学期期末教学质量检测试题含解析
- 2025届福建省厦门市五缘第二实验学校数学八上期末质量跟踪监视试题含解析
- 2024年岗位竞聘述职报告参考范本(三篇)
- 网络游戏开发与运营服务行业技术趋势分析
- 2025届河北省唐山市友谊中学八年级数学第一学期期末预测试题含解析
- 内蒙古通辽市开鲁县2025届数学八上期末质量跟踪监视模拟试题含解析
- 2.2合理利用网络-2024-2025学年八年级道德与法治上册单元练习(统编版)
- 小学中高年级课后服务 python编程教学 一阶第01课 认识python 课件
- 2024年全国一级造价师之建设工程造价管理考试高频题(附答案)
- 九年级物理上册 第十一章 简单机械和功 单元测试卷(苏科版 2024年秋)
- 国家基本公共卫生服务规范(第三版)65岁以上老年人健康管理服务培训课件
- 医疗软件采购协议模板
- 《集成电路版图设计》课程标准
- 建筑工地交通道路安全管理办法
- 2024年农产品食品质量安全检验员技能及理论知识考试题库(附含答案)
- 股东入股合作简单协议书范本
- 银行贷款受托支付合同范本
评论
0/150
提交评论