运筹学图与网络分析优秀PPT.ppt

运筹学运筹学 图与网与网络分析分析第一页，本课件共有115页1 图的基本概念v案例导引v图论中的图v图的矩阵描述第二页，本课件共有115页案例导引v图论是运筹学的一个重要分支，对其最早的研究可以追溯到著名的哥尼斯堡七桥问题(Konigsberg Bridges Problem)。18世纪，欧洲的哥尼斯堡城有一条流经全城的普雷戈尔河，河的两岸与河中两个小岛及两岛之间有七座桥彼此相通(如左图)。v当时人们关心这样的问题，即从陆地A,B,C,D中的任意地方出发，能否通过每座桥一次且仅通过一次，就能返回原出发地。第三页，本课件共有115页v1736年，瑞士数学家欧拉(E.Euler,1707-1783)当时正在圣彼得堡科学院工作，为俄罗斯女皇凯瑟琳服务。欧拉将这个问题抽象化，用含有4个点7条边的图形表示此问题(如右图)，发表依据几何位置的解题方法的论文，有效地解决了哥尼斯堡七桥问题。标志着欧拉创立了一个数学分枝，即后来人们所熟知的拓扑学(Topology)。v图论的第一部专著是匈牙利数学家O.Konig于1936出版的有限图与无限图的理论。第四页，本课件共有115页ABCDv哥尼斯堡七桥问题：在图中找一条经过每边一次且仅一次的路欧拉回路。ADBC由点和边组成由点和边组成第五页，本课件共有115页v环球旅行问题在图中找一条经过每个点一次且仅一次的路哈密尔顿回路。v中国邮路问题在图中找一条经过每边的最短路类似带权的欧拉回路。v货郎担问题在图中找一条经过每个点一次且仅一次的最短路带权的哈密尔顿回路。第六页，本课件共有115页图论中的图v图论中的图图论中的图：人们只关心有多少个点，这些点可以形成多少条边，它们的连接形式如何；不关心这些点的地理位置，边的长短和形状。第七页，本课件共有115页v设V=v1,v2,vn是n个元素的非空集合，E=e1,e2,em是m个元素的集合，若对于任意ejE，均有vs,vtV与之对应，则称VE为图图，记为G=(V,E)。v在G中，称vi为G的顶点顶点，ej为G的边边，并记ej=(vs,vt)=(vt,vs)，称vs,vt是ej的端点端点，ej是与vs,vt关联的边关联的边，称vs,vt为邻接的点邻接的点。v如果图中某一边的两个端点相同，则称为环环。如果图中的两边(或多边)具有相同的一对端点，则称为多重边多重边(或平行边)。无环和无多重边的图称为简单图简单图。第八页，本课件共有115页 例1：用图符号表示右图。解：(1)图G=(V,E)(2)V=v1,v2,v3,v4(3)E=e1,e2,e7，其中e1=(v1,v2)=(v2,v1)多重边e2=(v1,v2)=(v2,v1)多重边e3=(v2,v3)=(v3,v2)e4=(v3,v4)=(v4,v3)e5=(v1,v4)=(v4,v1)e6=(v1,v3)=(v3,v1)e7=(v4,v4)环第九页，本课件共有115页v与顶点v相关联的边数称为v的次数次数，记为d(v)。次数为零的点称为孤立点孤立点；次数为奇数的点为奇奇点点；次数为偶数的点称为偶点偶点；次数为1的点为悬挂点悬挂点；与悬挂点关联的边称为悬挂边悬挂边。v右图中各点的次数：d(v1)=4偶点d(v2)=3奇点d(v3)=4偶点d(v4)=1悬挂点d(v5)=0孤立点第十页，本课件共有115页v定理1 任一图中顶点次数之和等于边数的二倍，即d(vi)=2m。证明：次数表示与顶点相关联的边数，同一条边有两个邻接的点，即每一条边被邻接的点合计计算了2次，故次数之和等于边数的二倍。v定理2 任一图中奇点的个数必为偶数。证明：若奇点的个数是奇数，则这些顶点的次数之和必为奇数，所有顶点次数之和就是奇数，这与定理1矛盾。故奇点的个数必为偶数。第十一页，本课件共有115页v在图G中，从一个顶点出发，经过边、点、边、点、，最后到达某一点，称为G中的一条链链，用经过这条链的顶点或边表示。如上图中有一条链=(v1,v2,v3,v4)=(e2,e4,e6)。v若链中的顶点均是不同的，则称为初等链初等链；若链中所含的边均不相同，则称为简单链，简单链，也称为通路，通路，简称路路。上述链是初等链，也是简单链，是通路。第十二页，本课件共有115页v链=(v1,v2,vn)中，若v1=vn，则称此链为一个圈圈。若圈中的点都是不同的，则称为初等圈初等圈；若圈中所含的边均不相同，则称为简单圈简单圈。v在一个图中，若任意两点之间至少存在一条链，则称该图为连通图连通图，否则为不连通图不连通图。若有图G=(V,E)，取其全部或部分顶点V1，再取其全部或部分边E1，这里V1非空，且E1中的端点都在V1中，则称图G1=(V1,E1)为图G的子图子图。第十三页，本课件共有115页v设V=v1,v2,vn是n个元素的非空集合，A=a1,a2,am是m个元素的集合，若对于任一ajA，均有有序对(vs,vt)与之对应，则称VA为有向图有向图，记为D=(V,A)。称vi为顶点，aj为弧弧，记为aj=(vs,vt)，在不至于混淆时也称为边。v在有向图D中，从一个顶点出发，顺着弧的方向，经过弧、点、弧、点、，最后达到某一点，称为D中的一条单向链单向链或通路通路，简称路路，用经过这条单向链的顶点(或弧)表示。第十四页，本课件共有115页v在有向图中，顶点次数分为入次d-(vi)和出次d+(vi)，入次入次是以该顶点为终点的边数，出次出次是以该顶点为起点的边数。第十五页，本课件共有115页v例2：用符号表示右边的有向图。D=(V,A)，其中V=v1,v2,v3,v4,v5A=a1,a2,a3,a4,a5,a6,a7a1=(v1,v5)a2=(v5,v4)a3=(v1,v4)a4=(v3,v1)a5=(v1,v2)a6=(v2,v3)a7=(v1,v4)v1v2v3v4v5a1a2a3a4a5a6a7d-(v1)=1；d+(v1)=3d-(v2)=1；d+(v2)=1d-(v3)=1；d+(v3)=2d-(v4)=3；d+(v4)=0d-(v5)=1；d+(v5)=1第十六页，本课件共有115页v如果对于给定的图G=(V,E)的任意一边eE，有一实数W(e)与之对应，则称G为赋权图赋权图，称W(e)为边边e的权的权。v赋权图的应用比较广泛，如交通图中，权数可以是两点之间的单位运费、运能等；在工程网络图中，权数代表工序的时间。v设在赋权图中存在一条通路，则通路上所有边的权数之和称为这条通路的权通路的权。v对于一个有向图也可以定义权数使之成为有向有向赋权图赋权图。第十七页，本课件共有115页v一个连通图连同定义在其边集上的实数W(e)一起称为一个网络网络。v若一个网络的每条边均有方向，称为有向网络有向网络；每一条边均无方向，称为无向网络无向网络；若有些边有向，有些边无向，则称为混合网络混合网络。第十八页，本课件共有115页图的矩阵描述v无权图的邻接矩阵表示两顶点之间有边相连的记为1，无边相连的记为0，对角线位置数据记为0，这样就得到无权图的邻接矩阵，该矩阵一定是对称矩阵。v1v2v3v4v5终点v1v2v3v4v5起点v101100v210011v310001v401001v501110第十九页，本课件共有115页v赋权无向图的邻接矩阵表示两顶点之间有边相连的，写上其权数，无边相连的记为，对角线上的数字为0。赋权无向图对应的矩阵也是对称的。终点v1v2v3v4v5起点v1032v23054v3208v4502v54820v1v2v3v4v5423258第二十页，本课件共有115页v赋权有向图的邻接表示矩阵左侧第一列为各条弧的起点，在每一行中，以该点为起点，按弧的方向依次填上到各点的权数，如果不存在到该点的弧，则权数为。终点v1v2v3v4v5起点v1032v2054v3608v402v50v1v2v3v4v54232586第二十一页，本课件共有115页2 最小支撑树问题v树及其性质v图的支撑树(生成树)v最小支撑树问题v根树及其应用第二十二页，本课件共有115页树及其性质v树在现实中随处可见，如电话线架设、比赛程序、组织结构等。v树：连通的无圈的无向图称为树。第二十三页，本课件共有115页v树的性质v图G=(V,E)，p个点、q条边，下列说法是等价的(1)G是一个树(2)G连通，且恰有p-1条边(3)G无圈，且恰有p-1条边(4)G连通，但每舍去一边就不连通(5)G无圈，但每增加一边即得唯一一个圈(6)G中任意两点之间恰有一条链(简单链)第二十四页，本课件共有115页图的支撑树(生成树)v定义：设图T=(V,E)是图G=(V,E)的支撑子图，如果T是一个树，则称T是G的一个支撑树。v定理5：图G=(V,E)有支撑树的充分必要条件是G是连通的。第二十五页，本课件共有115页v找图中生成树的方法求支撑树的破圈法第二十六页，本课件共有115页v找图中生成树的方法求支撑树的避圈法深探法广探法第二十七页，本课件共有115页最小支撑树问题v赋权图(网络)：给定图G=(V,E),对G中的每一条边(vi,vj)，相应地有一个数wij，则称这样的图为赋权图。wij 称为边(vi,vj)上的权。v支撑树的权：若T=(V,E)是G的一个支撑树，E中的所有边的权之和称为支撑树的权，记为w(T)：w(T)=wij(其中(vi,vj)T)第二十八页，本课件共有115页v满足w(T*)=min(w(T)的树T*称为最小支撑树(最小树)。v求最小树的方法求最小树的避圈法求最小树的破圈法第二十九页，本课件共有115页根树及其应用v有向树中的根树在计算机科学、决策论中有很重要的应用v有向树：若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树有向树。v根树：有向树T，恰有一个结点入次为0，其余各点入次均为1，则称T为根树根树(又称外向树外向树)。根树中入次为0的点称为根根。根树中出次为0的点称为叶叶。入次和出次均大于0的点称为分枝点分枝点。由根到某一顶点vi的道路长度(设每边长度为1)，称为vi点的层次层次。第三十页，本课件共有115页v在根树中，若每个顶点的出次小于或等于M，称这棵树为M叉树叉树。v若每个顶点的出次恰好等于M或者零，则称这棵树为完全完全M叉树叉树。v当M=2时，称为二叉树二叉树、完全二叉树完全二叉树。第三十一页，本课件共有115页v如图所示的树是根树。其中根、分枝点、叶；各点层次都标注在树上。v这是一棵三叉树根叶分点枝第一层第三层第二层三叉树第三十二页，本课件共有115页v带权的二叉树T：令有s个叶子的二叉树T各叶子的权分别为pi，根到各叶子的距离(层次)为li(i=1,2,s)，这样二叉树T的总权数m(T)=pili。v满足总权数最小的二叉树称为最优二叉树最优二叉树(也称Huffman树)。vHuffman算法(D.A.Huffman最优二叉树算法)将s个叶子按权由小至大排序将二个具有最小权的叶子合并成一个分枝点，其权为两者之和，将新的分枝点作为一个叶子。转上一步，直到结束。第三十三页，本课件共有115页v例3：s=6，其权分别为4,3,3,2,2,1，求最优二叉树。123243365第三十四页，本课件共有115页123243396515123243396515第三十五页，本课件共有115页v例4：最优检索问题。使用计算机进行图书分类。现有五类图书共万册，其中有A类50万册，有B类20万册，C类5万册，D类10万册，E类15万册。问如何安排分检过程，可使总的运算(比较)次数最小？v解：构造一棵具有5个叶子的二叉树，其叶子的权分别为50,20,5,10,15。生成最优二叉树：C与D合并，之后与E合并，之后与B合并，之后与A合并。总权=5*4+10*4+15*3+20*2+50=195。分检过程：先将A类分检出来，然后分检B，然后分检E，最后分检D、C。第三十六页，本课件共有115页3 最短路问题v概述v最短路算法Dijkstra算法v最短路算法矩阵算法v最短路算法Floyd算法第三十七页，本课件共有115页概述v最短路问题最短路问题就是在一个网络中，给定一个起点，要求找出其到另一点的且权数最小的通路。最短路问题是网络分析中最重要的最优化问题之一。v最短路问题在实际分析中有广泛的应用，如管道铺设、运输路线选择、工厂布局等。v有些问题看起来与地理方位无关，但通过适当转化也可以将其归结为最短路问题，如设备更新问题等。第三十八页，本课件共有115页v最短路问题的一般描述：对D=(V,A)，aij=(vi,vj)，w(aij)=wij，P是从vs到vt的路，定义路P的权是P中所有弧的权的和，记为w(P)。最短路问题则成为求w(P0)=min(w(P)|P)。路P0的权称为从vs到vt的距离，记为：d(vs,vt)。第三十九页，本课件共有115页最短路算法Dijkstra算法v最短路的标号算法是由E.D.Dijkstra于1959年提出的，也称Dijkstra算法，是目前公认的求解最短路问题的较好算法，但此算法要求网络中边的权wij0。第四十页，本课件共有115页vDijkstra算法步骤：(1)从起点出发，依次寻找与起点距离最近的相邻点，并以此最短距离作为该点的标号，每次寻找一个点。(2)若已经计算出起点到若干点S=v1,v2,vi的最短距离，在找下一点时，要充分考虑到与S集合中的点的每一邻接点的可能，也就是说要考虑S集合中的每一点到其他点的距离，从中选出最短距离点。(3)重复上述过程，直到终点的标号被找到，则终止计算，找出最短路。第四十一页，本课件共有115页v例5：设有一批货物要从v1运到v7，每一边上的数字代表该段路线的长度，求最短的运输路线。v4v2v1v3v6v5v714425316227第四十二页，本课件共有115页序号 与S关联边距离集合S标号(0)d(v1)=0v1d(v1)=0(1)(v1,v2)(v1,v3)k12=d(v1)+l(v1,v2)=0+1=1k13=d(v1)+l(v1,v3)=0+4=4v1,v2d(v2)=1v1(2)(v1,v3)(v2,v3)(v2,v4)(v2,v5)(v2,v6)k13=d(v1)+l(v1,v3)=0+4=4k23=d(v2)+l(v2,v3)=1+2=3k24=d(v2)+l(v2,v4)=1+4=5k25=d(v2)+l(v2,v5)=1+7=8k26=d(v2)+l(v2,v6)=1+5=6v1,v2,v3d(v3)=3v2(3)(v2,v4)(v2,v5)(v2,v6)(v3,v6)k24=d(v2)+l(v2,v4)=1+4=5k25=d(v2)+l(v2,v5)=1+7=8k26=d(v2)+l(v2,v6)=1+5=6k36=d(v3)+l(v3,v6)=3+1=4v1,v2,v3,v6d(v6)=4v3第四十三页，本课件共有115页序号 与S关联边 距离集合S标号(4)(v2,v4)(v2,v5)(v6,v5)(v6,v7)k24=d(v2)+l(v2,v4)=1+4=5k25=d(v2)+l(v2,v5)=1+7=8k65=d(v6)+l(v6,v5)=4+3=7k67=d(v6)+l(v6,v7)=4+6=101,2,3,6,4d(v4)=5v2(5)(v4,v5)(v2,v5)(v6,v5)(v6,v7)k45=d(v4)+l(v4,v5)=5+2=7k25=d(v2)+l(v2,v5)=1+7=8k65=d(v6)+l(v6,v5)=4+3=7k67=d(v6)+l(v6,v7)=4+6=101,2,3,6,4,5d(v5)=7v4,v6(6)(v5,v7)(v6,v7)k57=d(v5)+l(v5,v7)=7+2=9k67=d(v6)+l(v6,v7)=4+6=101,2,3,6,4,5,7d(v7)=9v5v最短运输路线：(1)v1-v2-v4-v5-v7或(2)v1-v2-v3-v6-v5-v7v最短距离=d(v7)=9第四十四页，本课件共有115页最短路算法Dijkstra算法(PT标号)v(1)对源vs标以永久P标号：P(vs)=0；对其他顶点标以临时T标号：T(u)=。v(2)检查所有从P标号顶点到T标号顶点的弧。重新计算所有T标号的顶点的值T(v)=min(T(v),P(u)+c(u,v)v(3)计算T(v)=min(T(i)，标号P(v)，记录对应uv(4)重复(2)-(3)，直到全部顶点为P标号。最短路采用反向追踪；最短距离=P(vt)。第四十五页，本课件共有115页k123456710*21*1433*25864584*355*271067*4,61079*511 11111111111111111111111111111111111最短运输路线:(1)1-2-4-5-7;(2)1-2-3-6-5-7最短距离:d=9第四十六页，本课件共有115页最短路算法矩阵算法v最短路的矩阵算法是将图表达成矩阵形式，然后用矩阵表计算出最短路。v矩阵算法的基本思路与标号算法的基本思路一致。只不过一个标注在表上另一个标注在图上；标注在表上的便于计算机处理，标注在图上的直观第四十七页，本课件共有115页v矩阵算法的步骤：(1)将图表示成矩阵形式(2)确定起点行，标号为0，划去相应列(3)在已标号行且未划去的元素中，找出最小元素aij，圈起来，划去第j列，第j行标号aij，把第j行中未划去的各元素都加上aij(4)重复(3)，如果各行均已获得标号(或终点已经获得标号)，则终止计算。利用反向追踪，获得自起始点到各点的最短路；对应标号即为最短距离。第四十八页，本课件共有115页v例6：对上述例子利用矩阵算法求最短的运输路线。v解答：(1)先根据图完成矩阵表示。v1v2v3v4v5v6v7v1014v2102475v34201v4402v572032v651306v7260第四十九页，本课件共有115页v1v2v3v4v5v6v70v1014v2102475v34201v4402v572032v651306v7260v(2)找到起始点v1，第1行标号0，划去第1列第五十页，本课件共有115页v(3)在已标号行(第1行)且未划去的元素中(1,4)，寻找最小的元素(即为a12=1)。完成下列4项：圈：将a12圈起来；划：划去第2列；标：第2行标号1；加：第2行未划去的元素都加上1v1v2v3v4v5v6v70v10141v2102+14+17+15+1v34201v4402v572032v651306v7260第五十一页，本课件共有115页v(4)重复(3)。在已标号行(第1-2行)且未划去的元素中(4,3,5,8,6)，寻找最小的元素(即为a23=3)。完成下列4项：圈：将a23圈起来；划：划去第3列；标：第3行标号3；加：第3行未划去的元素都加上3v1v2v3v4v5v6v70v10141v21035863v34201+3v4402v572032v651306v7260第五十二页，本课件共有115页v(5)重复(3)。在已标号行(第1-3行)且未划去的元素中(5,8,6,4)，寻找最小的元素(即为a36=4)。完成下列4项：圈：将a36圈起来；划：划去第6列；标：第6行标号4；加：第6行未划去的元素都加上4v1v2v3v4v5v6v70v10141v21035863v34204v4402v5720324v6513+406+4v7260第五十三页，本课件共有115页v(6)重复(3)。在已标号行(第1-3,6行)且未划去的元素中(5,8,7,10)，寻找最小的元素(即为a24=5)。完成下列4项：圈：将a24圈起来；划：划去第4列；标：第4行标号5；加：第4行未划去的元素都加上5v1v2v3v4v5v6v70v10141v21035863v342045v4402+5v5720324v6517010v7260第五十四页，本课件共有115页v(7)重复(3)。在已标号行(第1-4,6行)且未划去的元素中(8,7,7)，寻找最小的元素(即为a45=a65=7)。完成下列4项：圈：将a45和a65圈起来；划：划去第5列；标：第5行标号7；加：第5行未划去的元素都加上7v1v2v3v4v5v6v70v10141v21035863v342045v44077v572032+74v6517010v7260第五十五页，本课件共有115页v(8)重复(3)。在已标号行(第1-6行)且未划去的元素中(9,10)，寻找最小的元素(即为a57=9)。完成下列4项：圈：将a57圈起来；划：划去第7列；标：第7行标号9；加：第7行未划去的元素都加上9(全部划完)v1v2v3v4v5v6v70v10141v21035863v342045v44077v5720394v65170109v7260第五十六页，本课件共有115页最短路算法Floyd算法v某些问题中，要求网络上任意两点之间的最短路，这类问题可以用Dijkstra算法依次改变起点的办法计算，但很繁琐。Floyd算法可以直接求取任意两点间最短路。vFloyd算法又称为弗洛伊德算法，插点法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特弗洛伊德命名。该法由Floyd于1962年完成(Robert W.Floyd:Algorithm 97:Shortest path,Communications of the ACM,1962年第5卷第6期)。第五十七页，本课件共有115页vFloyd算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。vFloyd算法的时间复杂度为O(n3)，空间复杂度为O(n2)。vFloyd算法，也有专业书籍称Floyd-Warshall算法(Floyd-Warshall Algorithm)。第五十八页，本课件共有115页vFloyd算法(1)输入权矩阵D(0)=D=(dij)nn，dij取值为如果(vi,vj)E，则dij=lij为vi到vj的距离如果(vi,vj)不属于E，则dij=(2)计算D(k)=(dij(k)nn，其中dij(k)=min(dij(k-1),dis(k-1)+dsj(k-1)(3)D(n)=(dij(n)nn中元素dij(n)就是vi到vj的最短路长。若D(p)=D(p-1)则也可结束。v迭代步长p根据公式2p-1n-12p估计第五十九页，本课件共有115页例7：利用Floyd算法求上例中最短路。v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 014v1 013585v2 102475v2 1024639v3 4201v3 3206417D(0)=v4 402D(1)=v4 5460254v5 72032v5 8642032v6 51306v6 5315305v7 260v7 974250111 1111111111111111111111111 111 111111111111111111111111v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 0135749v1 0135749v2 1024638v2 1024638v3 3206416v3 3206416D(2)=v4 5460254D(3)=v4 5460254v5 7642032v5 7642032v6 4315305v6 4315305v7 9864250v7 9864250第六十页，本课件共有115页v例8：若某地7个村庄之间的交通道路如图所示。旁边数字为各村庄之间道路的长度。试求各村之间的最短距离。12345672223344456771第六十一页，本课件共有115页解答03470345711 13303243032458430574305569D(0)=72026D(1)=52502364520147452013710211563102642013896320111 1111111111111111111111 111 11111111111111111111103457810034578103032457303245743055684305568D(2)=5250235D(3)=525023574520137452013856310285631021078532010785320第六十二页，本课件共有115页例9：用Floyd算法计算有向图的最短路12345678910728612122424565104626884第六十三页，本课件共有115页若v1v4方向不变，则结果如下12345678910108862042301072408D(0)=560212604712058064962041050111111 111 111 111 111 111 111 111 111 111 111第六十四页，本课件共有115页1234567891010886151010204141162731301072640812D(1)=56100286181660410871812140511981289064962960410175100111111 111 111 111 111 111 111 111 111 111 111第六十五页，本课件共有115页12345678910108861510101420182041411627131131301072156121040821121816D(2)=56101802861210616250134108718221712130511982712218906492762129604102327221718510160111111 111 111 111 111 111 111 111 111 111 111第六十六页，本课件共有115页12345678910108861510101420182041411627131131301072156121043943033821121816D(3)=5610180286121063135162501341087182217121305119827311221890649273162129604102327221718510160111111 111 111 111 111 111 111 111 111 111 111第六十七页，本课件共有115页12345678910108861510101420182041411627131131301072156121043943033821121816D(4)=5610180286121063135162501341087182217121305119827311221890649273162129604102327221718510160111111 111 111 111 111 111 111 111 111 111 111第六十八页，本课件共有115页若v1v4方向改变，则结果如下12345678910108818151010142018220041411627131131613010721561210461414021816121816D(4)=5246101802861210622303016250134108723182217121305119818262612218906491220206212960410282327221718510160111111 111 111 111 111 111 111 111 111 111 111第六十九页，本课件共有115页若v4v1容量为-6，则结果如下1234567891010881815101014201828041411627131134120107214612104-622094481412D(4)=512610180286121061018181625013410871118191712130511986141412218906490886152960410162324221718510160111111 111 111 111 111 111 111 111 111 111 111第七十页，本课件共有115页4 最大流问题v基本概念v最大流算法1标号算法v最大流算法2改进标号算法v最大流算法3最小截集法v最大流算法4线性规划(Excel求解)第七十一页，本课件共有115页基本概念v给定一个有向图D=(V,A)，如果对于每一条弧a=(vi,vj)A，均有一个非负实数cij=c(vi,vj)=c(a)C与之对应，称c(a)为弧a的容容量量；v称V中入次为0出次大于0的顶点vs为源源(发点发点)，v称入次大于0出次为0的顶点vt为汇汇(收点收点)，v入次和出次均大于0的顶点为中间顶点中间顶点，v则称这个图为容量网络容量网络，有时也根据运输情况称为运输网络，简称网络，记为N=(V,A,C,vs,vt)。第七十二页，本课件共有115页v一般地，如果网络N=(V,A,C,vs,vt)中，定义在弧集A上的一个函数f满足：(1)对于任意一条弧(vi,vj)，都有0fijcij；(2)对于中间顶点vk，fik=fkj；(3)对于源vs和汇vt，存在fsj=fit=Vf，v则称f为N的一个网络流网络流，简称流流，称Vf为f的流流量量。v对于给定的运输网络，一个十分实际的问题是如何求得该网络中流量最大的网络流，简称最大流最大流。第七十三页，本课件共有115页v设是从源vs到汇vt的一条链，定义的方向是从vs到vt。称上与同向的弧为前向弧前向弧，记前向弧的集合为+，称上与反向的弧为反向弧反向弧，记反向弧的集合为-。v设是网络N中从源vs到汇vt的一条链，f是N的一个网络流，若对于任一a+，f(a)0，则称是网络N中关于流f的一条增广链增广链。第七十四页，本课件共有115页v设是网络N中关于流f的一条增广链，可以采用如下方法改进流f使流量Vf增大。v(1)令=minc(a)-f(a)|a+,f(a)|a-v(2)作g(a)=f(a)+,a+f(a)-,a-f(a),其他v得到g一定满足网络流的三个条件，所以g仍然为N中的网络流，而Vg=Vf+Vf，流量增大。第七十五页，本课件共有115页最大流算法1标号算法v(1)给出初始流f=0v(2)令l(vs)=+，S=vs，B=，T=V-Sv(3)考察S-B中的顶点u若vT，前向弧(u,v)满足f(u,v)0，给顶点v标号u,-,l(v)，其中l(v)=minl(u),f(v,u)，并将v吸纳入S第七十六页，本课件共有115页v(4)若对所有vT，前向弧(u,v)和反向弧(v,u)均检查完毕，将检查完的顶点u并入B，转(3)v(5)若vt进入S，则必然存在从vs到vt的增广链，反向追踪得到，且=l(vt)，令g(a)=f(a)+，a+f(a)-，a-f(a)，其他vVg=Vf+，转(2)v(6)若S-B=，vt不能进入S，则f已是网络最大流第七十七页，本课件共有115页最大流算法2改进标号算法v(1)对弧的容量加以改进。每一条弧a=(u,v)起点端标上流量c(u,v)，终点端标上0；若为双向弧，则都标上c(u,v)。v(2)寻找增广链。找出一条从源vs到汇vt的路，要求这条路上每一条弧顺流方向的容量都大于0。存在，转(3)；不存在，停止，最大流Vf=。v(3)计算=minc(u,v)|a=(u,v)v(4)修改标号。对上每个弧都修改其标号：顺流容量减少，逆流容量增加。返回(2)第七十八页，本课件共有115页最大流算法3最小截集法v(1)设vsV1,vtV2,V1V2=,V1V2=Vv(2)计算fi=c(u,v)(uV1,vV2,(u,v)E)v(3)调整V1和V2，转(2)v(4)遍历各种组合，Vf=min(fi)v上述有关最小截集法是基于最大流量最小截集定理：最大流量=最小截集容量第七十九页，本课件共有115页最大流算法4线性规划v设过弧a=(i,j)的流量是f(i,j)，容量c(i,j)。则必有0f(i,j)c(i,j)。v又由于顶点可以分成三类：(1)源vs，netflow(s)=f(s,j)-f(i,s)max(2)汇vt，netflow(t)=f(t,j)-f(i,t)(3)中间顶点vk，netflow(k)=f(k,j)-f(i,k)=0v故应有网络最大流的线性规划模型如下vmax f=f(s,i)f(k,j)-f(i,k)=0 (kV,kvs,kvt)f(i,j)c(i,j)f(i,j)0第八十页，本课件共有115页例101234564482214679第八十一页，本课件共有115页解答1最小截集序号V1V2c(u,v)fiY Vf(1)12,3,4,5,6 c(1,2)=4；c(1,3)=8128(2)1,23,4,5,6c(2,3)=4；c(2,4)=4c(2,5)=1；c(1,3)=8 17(3)1,32,4,5,6c(1,2)=4；c(3,4)=2c(3,5)=28 Y(4)1,2,34,5,6c(2,4)=4；c(2,5)=1c(3,4)=2；c(3,5)=29(5)1,2,3,45,6c(2,5)=1；c(3,5)=2c(4,6)=710(6)1,2,3,54,6c(2,4)=4；c(3,4)=2c(5,4)=6；c(5,6)=921(7)1,2,3,4,5 6c(4,6)=7；c(5,6)=916第八十二页，本课件共有115页解答2线性规划(Excel求解)ABCDEFGH1 From To Caption FlowNodes NetFlow Condition2124418 3138420 04234030 05244440 06251050 0734226-8 8352294677105461115691=SUMIF($A$2:$A$11,F2,$D$2:$D$11)-SUMIF($B$2:$B$11,F2,$D$2:$D$11)第八十三页，本课件共有115页5 最小费用最大流v网络D=(V,A,C)的每一个弧(vi,vj)A，除了容量cij=c(vi,vj)外，还给定单位流量的费用bij=b(vi,vj)0。所谓最小费用最大流问题就是要求一个最大流f，使流的总输送费用b(f)=bijfij取极小值。v对增广链，若调整流量=1，那么新可行流f的费用比原可行流f的费用增加b(f)-b(f)=bij(fij-fij)|(i,j)+-bij(fij-fij)|(i,j)-=bij|(i,j)+-bij|(i,j)-第八十四页，本课件共有115页v可以证明，若f是流量为v(f)的所有可行流中费用最小者，而是关于f的所有增广链中费用最小的增广链，那么沿着去调整f，得到的可行流f就是流量为v(f)的所有可行流中的最小费用流。当f是最大流时，就是最小费用最大流。v由于bij0，所以f=0必定是流量为0的最小费用流。这样，总可以从f=0开始，寻找对应于v(f)的最小费用流。设已知f是流量v(f)的最小费用流，余下的问题是如何寻找关于f的最小费用增广链。第八十五页，本课件共有115页v构造一个赋权有向图W(f)，其顶点是原网络D的顶点，而把D中每一条弧(vi,vj)变成两个相反的弧(vi,vj)和(vj,vi)，定义W(f)中的权wij为bij,若fij0+,fij=0v于是在网络D中寻求关于f的最小费用增广链就等价于在赋权有向图W(f)中寻求从vs到vt的最短路。第八十六页，本课件共有115页最小费用最大流算法v(1)若在第k-1步中得到最小费用流f(k-1)，则构造赋权有向图W(f(k-1)v(2)寻求从vs到vt的最短路。若不存在，则f(k-1)就是最小费用最大流；否则转(3)v(3)在原网络D中得到增广链，对f(k-1)调整量为=minmin(cij-fij(k-1)|+,min(fij(k-1)|-，得到新的可行流f(k)。令fij(k)=fij(k-1)+，(i,j)+fij(k-1)-，(i,j)-fij(k-1)，(i,j)不属于v(4)重复上述步骤第八十七页，本课件共有115页例11v求如下网络D的最小费用最大流。弧旁数字为(bij,cij)。vsv2v3vtv1(4,1