Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离散数学,黄晓宇,第一页，共24页。,离散数学黄晓宇第一页，共24页。,1,本讲内容,网络模型的基本概念,最大流算法,最大流最小割,匹配,第二页，共24页。,本讲内容网络模型的基本概念第二页，共24页。,2,引例,b,c,码头,a,炼油厂,z,e,d,5,3,2,4,2,4,2,求出从码头到炼油厂的最大流量,第三页，共24页。,引例bc码头a 炼油厂zed5324242求出从码头到炼油厂,3,定义,一个传输网络是一个满足下列条件的简单加权有向图,一个源,一个汇,有向边(i,j)的权 C,ij,是非负数，称为容量,一个网络的流量是对每边赋流量值，该值不超过所在边的容量。,第四页，共24页。,定义一个传输网络是一个满足下列条件的简单加权有向图第四页，共,4,定义（二）,G是一个传输网络，C,ij,是(i,j)的容量。G的一个流量F 赋予(i,j)值F,ij,，满足：,F,ij,C,ij,对非源点和收点i和j，有,中间节点的流出流量 流入流量,第五页，共24页。,定义（二）G是一个传输网络，Cij是(i,j)的容量。,5,定义（三）,网络流量,起点a的流出流量终点z的流入流量，这个流量称作流量F的值,网络流中的核心问题：最大流量,码头a,b,c,炼油厂z,e,d,5,3,3,2,2,2,4,2,2,2,4,3,2,1,第六页，共24页。,定义（三）网络流量码头a bc炼油厂zed5,33,22,2,6,超级源、汇,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,第七页，共24页。,超级源、汇w1bABd364c4323w2w32w1bABd,7,使用网络流表示问题,P459：习题17,第八页，共24页。,使用网络流表示问题第八页，共24页。,8,最大流算法,传输网络G的一个最大流量是具有最大值的流量，最大流可能存在多个；,基本思想：从初始流量开始，反复增加，直至不能再增大。,第九页，共24页。,最大流算法传输网络G的一个最大流量是具有最大值的流量，最大流,9,通路,p=(v,0,v,1,v,n,)，v,0,=a，v,n,=z 是从a到z的一条通路；,如果在p中边e是从 v,i-1,指向 v,i,则称是定向的，否则称是非定向的,第十页，共24页。,通路p=(v0,v1,vn)，v0=a，vn=z,10,通路（a,z）,第十一页，共24页。,通路（az）第十一页，共24页。,11,四种情况,3，1,4，1,3，2,5，1,3，2,4，0,3，3,5，2,第十二页，共24页。,四种情况3，14，13，25，13，24，03，35，2第十,12,定义,设P是网络G中从 a 到 z 的通路，其中容量为 C，流量为 F,满足：,对P中定向的边(i,j),F,i,j,C,i,j,对P中非定向的边(i,j),0 F,i,j,C,i,j,F,i,j,如果(i,j)一致定向的边,X,i,j,=,F,i,j,如果(i,j)是非一致定向的边,第十三页，共24页。,定义设P是网络G中从 a 到 z 的通路，其中容量为 C，流,13,令 =mini X,i,j,i,j=1,.,n,定义 F,i,j,*=,F,i,j,(i,j)不在 P中,F,i,j,+,(i,j)是P中定向的边,F,i,j,-,(i,j)是P中非定向的边,则F*=F,i,j,*是一个流量比 F 增值 d的流.,第十四页，共24页。,令 =mini Xi,j i,j=1,.,n,14,算法思想,从流量0开始,查找满足定理的通路，如果不存在，结束，流量就是最大的,通路增加流量,，goto 2,第十五页，共24页。,算法思想从流量0开始第十五页，共24页。,15,输入：网络G，容量C，a,z,n,输出：最大流量F,Procedure max_flow(a,z,C,v,n),/v的标记为(predecessor(v)/前趋结点，val(v)/结点v的流量增量,第十六页，共24页。,输入：网络G，容量C，a,z,n第十六页，共24页。,16,第十七页，共24页。,第十七页，共24页。,17,/没有新的通路,第十八页，共24页。,/没有新的通路第十八页，共24页。,18,/正向边,第十九页，共24页。,/正向边第十九页，共24页。,19,/反向边,第二十页，共24页。,/反向边第二十页，共24页。,20,第二十一页，共24页。,第二十一页，共24页。,21,/增量F,第二十二页，共24页。,/增量F第二十二页，共24页。,22,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),第二十三页，共24页。,a bced5,03,02,0b4,02,04,02,0(-,23,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),第二十四页，共24页。,a bced5,23,22,2b4,02,04,42,2(-,24,