newchap10.ppt

1、第10 章 网 络 模 型,离散数学,国外计算机科学教材序列 离散数学(第6版) Richard Johnsonbaugh 石纯一 等译 电子工业出版社,主题,网络模型 通过一个网络的最大流量问题 系统优化，资源分配和人员分配,10.1 网络模型,码头a,b,c,炼油厂z,e,d,5,3,2,b,4,2,4,求出从码头到炼油厂的最大流量,2,定义 10.1.1,一个传输网络是一个满足下列条件的简单加权有向图 一个源 一个汇 有向边(i,j)的权 Cij 是非负数，称为容量,例10.1.2 网络模型,源a,b,c,汇z,e,d,5,3,2,b,4,2,4,一个网络的流量是对每边赋流量值，该值不超

2、过所在边的容量。,2,定义10.1.3,G是一个传输网络， Cij是 (i,j)的容量 G的一个流量F 赋予 (i,j) 值Fij 满足 Fij Cij Fij Fj I 流入流出 流量守恒 i i,10.1.4,码头a,b,c,炼油厂z,e,d,5,3,3,2,2,2,b,4,2,2,2,4,3,Fad = 3 流入流出 Fdc+Fde =3,2,1,定理10.1.5, Fai Fi z i i 流出源的流量 流入汇的流量,定义 10.1.6, Fai Fi z i i 称作流量F的值。,10.1.7,码头a,b,c,炼油厂z,e,d,5,3,3,2,2,2,b,4,2,2,2,4,3,流量

3、F的值 5 求G的最大流量，即使F值最大。,2,1,例 10.1.8,w1,b,A,B,d,3,6,4,c,4,3,2,3,w2,w3,超级源、汇,w1,b,A,B,d,3,6,4,c,4,3,2,3,a,w3,w2,z,10.2 最大流量算法,G ： 传输网络 G的一个最大流量是具有最大值的流量 可能存在多个 基本概念：从初始流量0开始 重复增加,通路,p= (v0, v1, , vn), v0=a, vn=z 是从a到z的一条通路 如果在p中边e是从 vi-1 指向 vi 则称是 一致定向的 否则称是非一致定向的,v0 = a (source) vn = z (sink) Path P =

4、 (v0, v1, vn),10.2.1,3，1,2，1,4，1,3，2,2，2,4，2,4种情况,4种情况,例10.2.2,3，1,4，1,3，2,5，1,3，2,4，0,3，3,5，2,定理10.2.3,设P是网络G中从 a 到 z 的通路， 其中容量为 C， 流量为 F, 满足： a) 对P中一致定向的边 (i,j), Fi,j Ci,j b)对P中非一致定向的边 (i,j), 0 Fi,j 令 Xi,j = Ci,j Fi,j 如果(i,j)一致定向的边 = Fi,j 如果(i,j)是非一致定向的边,定理10.2.3,令 = mini Xi,j i,j= 1,.,n 定义 Fi,j*=

5、 Fi,j (i,j) 不在 P中 Fi,j + (i,j)是P中一致定向的边 Fi,j - (i,j)是P中非一致定向的边 则F* = Fi,j* 是一个流量比 F 增值 d的流.,算法思想,从流量0开始 查找满足定理的通路，如果不存在，结束，流量就是最大的 通路增加流量，goto 2,算法 10.2.4,输入： 网络G， 容量C，a, z,n 输出 ：最大流量F Procedure max_flow(a,z,C,v,n) / v的标记为 (predecessor(v)/前趋结点， val(v)/结点v的流量增量）,没有新的通路,v,w,Cvw, Fvw,正向边,Fvw,反向边,构造通路,增

6、量F,10.2.5-1,a,b,c,z,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),10.2.5-2,a,b,c,z,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),10.2.5-3,a,b,c,z,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),10.2.5-4,a,b,c,z,e,d,5,4,3,2,2,2,b,

7、4,2,2,2,4,4,2,2,(-, ),(a, 1),(a, 1),10.2.6-1,a,b,c,z,e,d,4,2,3,2,4,4,2,0,2,0,5,4,(-, ),(a, 1),(a, 1),(-, ),3,2,(b, 1),f,(f, 1),(e, 1),4,2,10.2.6-2,a,b,c,z,e,d,4,2,3,3,4,4,2,1,2,1,5,4,3,2,f,4,1,10.2.6-3,a,b,c,z,e,d,4,3,3,3,4,4,2,2,2,2,5,4,3,3,f,4,1,10.3 最大流最小切割,G网络 F是算法终止时的网络流量。 P被标记的结点集合a P P =未被标记的

8、集合z P 切割S = (v,w) | v P, w P 切割S 的容量 C = Ci,j 其中 (i,j) S,10.3.2,a,b,c,z,e,d,4,2,3,3,4,4,2,0,2,1,5,4,3,2,f,4,1,P=a,b,d, P=c,e,f,z,Theorem 10.3.7,给定S C （S的切割容量） F,10.3.9 Max flow, min cut 定理,C（S的切割容量） = F 当且仅当 Fi,j = Ci,j i P, j P Fi,j = 0 i P 且 j P 此时, F 最大 ，S最小,10.3.10,a,b,c,z,e,d,5,4,3,2,2,2,b,4,2,

9、2,2,4,4,2,2,(-, ),(a, 1),(a, 1),C=6,F=6,10.3.11,定理 算法10.2.4结束时生成一个最大流量，如果P和P是算法结束时被标记和未被标记的结点的集合，则切割容量C是最小的。,10.4 匹配,一个集合中的元素匹配另一个集合中的元素的问题 网络最大流问题,8.4.1匹配,4 个人A, B, C ，D 申请5个工作 Jk, 1 k 5.边表示能胜任的工作，给每人找一工作,10.4.2,G 有向图, V ，W 顶点集合，边从 V 到W G的一个匹配是边的集合E，E不含共同顶点。 最大匹配，包含最多边的E,完全匹配,对于任何 v V有 (v,w) E ， w

10、W.,10.4.4 匹配网络,增加超级源a，超级汇z，每条边赋予容量1,定理 10.4.5,G 有向二部图 匹配网络的流量给出G的一个匹配，v V和w W匹配，当且仅当(v,w) 的流量为1 最大流量对应于最大匹配 值为|V|的流量对应于完全匹配,最大匹配,G有向偶图 顶点集合 V， W S V R（S） w W | v S, (v, w)是G的边 假定G有一个完全匹配，则 |S| | R（S）| 反之亦然？ （by Philip Hall）,Hall 婚姻定理,G 有向图, V ，W 顶点集合，边从 V 到W S V R（S） w W | v S, (v, w)是G的边，则 G存在完全匹配 iff |S| |R(S)| for all S V.,例10.4.4,S=A,B,D, R(S)=J2, 5 3 2 不