newchap10.ppt

,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,H LP-DM,第,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,),的权,C,ij,是非负数，称为容量,例,10.1.2,网络模型,源,a,b,c,汇,z,e,d,5,3,2,b,4,2,4,一个网络的流量是对每边赋流量值，该值不超过所在边的容量。,2,定义,10.1.3,G,是一个传输网络，,C,ij,是,(,i,j,),的容量,G,的一个流量,F,赋予,(,i,j,),值,F,ij,满足,F,ij,C,ij,F,ij,F,j,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,F,ai,F,i,z,i i,流出源的流量,流入汇的流量,定义,10.1.6,F,ai,F,i,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,流量,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,是从,v,i-1,指向,v,i,则称是 一致定向的,否则称是非一致定向的,v,0,=a(source),v,n,=z(sink),Path P=(v,0,v,1,v,n,),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,F,10.3.9 Max flow,min cut,定理,C,（,S,的切割容量）,=F,当且仅当,F,i,j,=,C,i,j,i P,j P,F,i,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,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 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|,2,不存在完全匹配,计算机 和 磁盘,n,台计算机，,n,个磁盘驱动器,每台计算机和,m,台磁盘驱动器兼容,每台磁盘驱动器和,m,台计算机兼容,匹配,解,V,计算机,W,磁盘驱动器,每个顶点度为,m,设,S,v1,vk,是,V,的子集，,km,条边，如果,RS,w1,wj,RS,至多从,S,接受,jm,条边，,km,jm,k j,|S|,|R(S)|,OK,