离散数学-网络模型.ppt_第1页
离散数学-网络模型.ppt_第2页
离散数学-网络模型.ppt_第3页
离散数学-网络模型.ppt_第4页
离散数学-网络模型.ppt_第5页
已阅读5页，还剩20页未读， 继续免费阅读

下载本文档

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

文档简介

离散数学 黄晓宇 本讲内容 网络模型的基本概念最大流算法最大流最小割匹配 引例 b c 求出从码头到炼油厂的最大流量 定义 一个传输网络是一个满足下列条件的简单加权有向图一个源一个汇有向边 i j 的权Cij是非负数 称为容量一个网络的流量是对每边赋流量值 该值不超过所在边的容量 定义 二 G是一个传输网络 Cij是 i j 的容量 G的一个流量F赋予 i j 值Fij 满足 Fij Cij对非源点和收点i和j 有 中间节点的流出流量 流入流量 定义 三 网络流量起点a的流出流量 终点z的流入流量 这个流量称作流量F的值网络流中的核心问题 最大流量 超级源 汇 使用网络流表示问题 P458 例10 1 9P459 习题1 7 最大流算法 传输网络G的一个最大流量是具有最大值的流量 最大流可能存在多个 基本思想 从初始流量开始 反复增加 直至不能再增大 通路 p v0 v1 vn v0 a vn z是从a到z的一条通路 如果在p中边e是从vi 1指向vi则称是定向的 否则称是非定向的 通路 a z 四种情况 3 1 4 1 3 2 5 1 3 2 4 0 3 3 5 2 定义 设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 是非一致定向的边 令 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开始查找满足定理的通路 如果不存在 结束 流量就是最大的通路增加流量 goto2 输入 网络G 容量C a z n输出 最大流量FProceduremax flow a z C v n v的标记为 predecessor v 前趋结点 val v 结点v的流量增量 没有新的通路 正向边 反向边
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论