《离散数学-网络模型.ppt》由会员分享，可在线阅读，更多相关《离散数学-网络模型.ppt（24页珍藏版）》请在装配图网上搜索。
1、离散数学 黄晓宇 HuangS 本讲内容 网络模型的基本概念 最大流算法 最大流最小割 匹配 引例 b c 码头 a 炼油厂 z e d 5 3 2 4 2 4 2 求出从码头到炼油厂的最大流量 定义 一个传输网络是一个满足下列条件的简 单加权有向图 1. 一个源 2. 一个汇 3. 有向边 (i,j)的权 Cij 是非负数，称为容量 一个网络的流量是对每边赋流量值，该 值不超过所在边的容量。 定义（二） G是一个传输网络， Cij是 (i,j)的容量。 G 的一个流量 F 赋予 (i,j) 值 Fij，满足： Fij Cij 对非源点和收点 i和 j，有 i ijj ij FF 中间节点的流
2、出流量 流入流量 定义（三） 网络流量 起点 a的流出流量终点 z的流入流量，这个流 量称作流量 F的值 网络流中的核心问题：最大流量 码头 a b c 炼油厂 z e d 5,3 3,2 2,2 4,2 2,2 4,3 2,1 超级源、汇 w1 b A B d 3 6 4 c 4 3 2 3 w2 w3 2 w1 b A B d 3 6 4 c 4 3 2 3 a w3 w2 z 使用网络流表示问题 P458：例 10.1.9 P459：习题 1 7 最大流算法 传输网络 G的一个最大流量是具有最大值 的流量，最大流可能存在多个； 基本思想：从初始流量开始，反复增加， 直至不能再增大。 通路
3、 p= (v0, v1, , vn)， v0=a， vn=z 是从 a到 z 的一条通路； 如果在 p中边 e是从 vi-1 指向 vi 则称是定 向的，否则称是非定向的 通路（ az） 四种情况 3， 1 4， 1 3， 2 5， 1 3， 2 4， 0 3， 3 5， 2 定义 设 P是网络 G中从 a 到 z 的通路，其中容 量为 C，流量为 F, 满足： I. 对 P中定向的边 (i,j), Fi,j Ci,j II. 对 P中非定向的边 (i,j), 0 Fi,j Ci,j Fi,j如果 (i,j)一致定向的边 Xi,j = Fi,j如果 (i,j)是非一致定向的边 令 = mini
4、 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的流 . 算法思想 1. 从流量 0开始 2. 查找满足定理的通路，如果不存在，结 束，流量就是最大的 3. 通路增加流量 ， goto 2 输入：网络 G，容量 C， a,z,n 输出：最大流量 F Procedure max_flow(a,z,C,v,n) / v的标记为 (predecessor(v)/ 前趋结点， val(v)/结点 v的流量增 量 /没有新的通路
5、 /正向边 /反向边 /增量 F a b c e d 5,0 3,0 2,0 b 4,0 2,0 4,0 2,0 (-, ) (a, 3) (b, 2) (a, 5) (c, 2) a b c e d 5,0 3,2 2,2 b 4,0 2,0 4,2 2,0 (-, ) (a, 1) (d, 2) (a, 5) (d, 2) (c, 2) a b c e d 5,2 3,2 2,2 b 4,0 2,0 4,4 2,2 (-, ) (a, 1) (a, 3) (d, 2) (e, 2) a b c e d 5,4 3,2 2,2 b 4,2 2,2 4,4 2,2 (-, ) (a, 1) (a, 1)
离散数学-网络模型.ppt
