运筹学 图与网络分析

运筹学图与网络分析第1页，共115页，2023年，2月20日，星期四1图的基本概念案例导引图论中的图图的矩阵描述第2页，共115页，2023年，2月20日，星期四案例导引图论是运筹学的一个重要分支，对其最早的研究可以追溯到著名的哥尼斯堡七桥问题(KonigsbergBridgesProblem)。18世纪，欧洲的哥尼斯堡城有一条流经全城的普雷戈尔河，河的两岸与河中两个小岛及两岛之间有七座桥彼此相通(如左图)。当时人们关心这样的问题，即从陆地A,B,C,D中的任意地方出发，能否通过每座桥一次且仅通过一次，就能返回原出发地。第3页，共115页，2023年，2月20日，星期四1736年，瑞士数学家欧拉(E.Euler,1707-1783)当时正在圣彼得堡科学院工作，为俄罗斯女皇凯瑟琳服务。欧拉将这个问题抽象化，用含有4个点7条边的图形表示此问题(如右图)，发表《依据几何位置的解题方法》的论文，有效地解决了哥尼斯堡七桥问题。标志着欧拉创立了一个数学分枝，即后来人们所熟知的拓扑学(Topology)。图论的第一部专著是匈牙利数学家O.Konig于1936出版的《有限图与无限图的理论》。第4页，共115页，2023年，2月20日，星期四ABCD哥尼斯堡七桥问题：在图中找一条经过每边一次且仅一次的路——欧拉回路。ADBC由点和边组成第5页，共115页，2023年，2月20日，星期四环球旅行问题在图中找一条经过每个点一次且仅一次的路——哈密尔顿回路。中国邮路问题在图中找一条经过每边的最短路——类似带权的欧拉回路。货郎担问题在图中找一条经过每个点一次且仅一次的最短路——带权的哈密尔顿回路。第6页，共115页，2023年，2月20日，星期四图论中的图图论中的图：人们只关心有多少个点，这些点可以形成多少条边，它们的连接形式如何；不关心这些点的地理位置，边的长短和形状。第7页，共115页，2023年，2月20日，星期四设V={v1,v2,…,vn}是n个元素的非空集合，E={e1,e2,…,em}是m个元素的集合，若对于任意ej∈E，均有vs,vt∈V与之对应，则称V∪E为图，记为G=(V,E)。在G中，称vi为G的顶点，ej为G的边，并记ej=(vs,vt)=(vt,vs)，称vs,vt是ej的端点，ej是与vs,vt关联的边，称vs,vt为邻接的点。如果图中某一边的两个端点相同，则称为环。如果图中的两边(或多边)具有相同的一对端点，则称为多重边(或平行边)。无环和无多重边的图称为简单图。第8页，共115页，2023年，2月20日，星期四

例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)环第9页，共115页，2023年，2月20日，星期四与顶点v相关联的边数称为v的次数，记为d(v)。次数为零的点称为孤立点；次数为奇数的点为奇点；次数为偶数的点称为偶点；次数为1的点为悬挂点；与悬挂点关联的边称为悬挂边。右图中各点的次数：d(v1)=4偶点d(v2)=3奇点d(v3)=4偶点d(v4)=1悬挂点d(v5)=0孤立点第10页，共115页，2023年，2月20日，星期四定理1

任一图中顶点次数之和等于边数的二倍，即Σd(vi)=2m。证明：次数表示与顶点相关联的边数，同一条边有两个邻接的点，即每一条边被邻接的点合计计算了2次，故次数之和等于边数的二倍。定理2

任一图中奇点的个数必为偶数。证明：若奇点的个数是奇数，则这些顶点的次数之和必为奇数，所有顶点次数之和就是奇数，这与定理1矛盾。故奇点的个数必为偶数。第11页，共115页，2023年，2月20日，星期四在图G中，从一个顶点出发，经过边、点、边、点、…，最后到达某一点，称为G中的一条链，用经过这条链的顶点或边表示。如上图中有一条链μ=(v1,v2,v3,v4)=(e2,e4,e6)。若链中的顶点均是不同的，则称为初等链；若链中所含的边均不相同，则称为简单链，也称为通路，简称路。上述链μ是初等链，也是简单链，是通路。第12页，共115页，2023年，2月20日，星期四链μ=(v1,v2,…,vn)中，若v1=vn，则称此链为一个圈。若圈中的点都是不同的，则称为初等圈；若圈中所含的边均不相同，则称为简单圈。在一个图中，若任意两点之间至少存在一条链，则称该图为连通图，否则为不连通图。若有图G=(V,E)，取其全部或部分顶点V1，再取其全部或部分边E1，这里V1非空，且E1中的端点都在V1中，则称图G1=(V1,E1)为图G的子图。第13页，共115页，2023年，2月20日，星期四设V={v1,v2,…,vn}是n个元素的非空集合，A={a1,a2,…,am}是m个元素的集合，若对于任一aj∈A，均有有序对(vs,vt)与之对应，则称V∪A为有向图，记为D=(V,A)。称vi为顶点，aj为弧，记为aj=(vs,vt)，在不至于混淆时也称为边。在有向图D中，从一个顶点出发，顺着弧的方向，经过弧、点、弧、点、…，最后达到某一点，称为D中的一条单向链或通路，简称路，用经过这条单向链的顶点(或弧)表示。第14页，共115页，2023年，2月20日，星期四在有向图中，顶点次数分为入次d-(vi)和出次d+(vi)，入次是以该顶点为终点的边数，出次是以该顶点为起点的边数。第15页，共115页，2023年，2月20日，星期四例2：用符号表示右边的有向图。D=(V,A)，其中V={v1,v2,v3,v4,v5}A={a1,a2,a3,a4,a5,a6,a7}a1=(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第16页，共115页，2023年，2月20日，星期四如果对于给定的图G=(V,E)的任意一边e∈E，有一实数W(e)与之对应，则称G为赋权图，称W(e)为边e的权。赋权图的应用比较广泛，如交通图中，权数可以是两点之间的单位运费、运能等；在工程网络图中，权数代表工序的时间。设在赋权图中存在一条通路，则通路上所有边的权数之和称为这条通路的权。对于一个有向图也可以定义权数使之成为有向赋权图。第17页，共115页，2023年，2月20日，星期四一个连通图连同定义在其边集上的实数W(e)一起称为一个网络。若一个网络的每条边均有方向，称为有向网络；每一条边均无方向，称为无向网络；若有些边有向，有些边无向，则称为混合网络。第18页，共115页，2023年，2月20日，星期四图的矩阵描述无权图的邻接矩阵表示两顶点之间有边相连的记为1，无边相连的记为0，对角线位置数据记为0，这样就得到无权图的邻接矩阵，该矩阵一定是对称矩阵。v1v2v3v4v5终点v1v2v3v4v5起点v101100v210011v310001v401001v501110第19页，共115页，2023年，2月20日，星期四赋权无向图的邻接矩阵表示两顶点之间有边相连的，写上其权数，无边相连的记为∞，对角线上的数字为0。赋权无向图对应的矩阵也是对称的。终点v1v2v3v4v5起点v1032∞∞v230∞54v32∞0∞8v4∞5∞02v5∞4820v1v2v3v4v5423258第20页，共115页，2023年，2月20日，星期四赋权有向图的邻接表示矩阵左侧第一列为各条弧的起点，在每一行中，以该点为起点，按弧的方向依次填上到各点的权数，如果不存在到该点的弧，则权数为∞。终点v1v2v3v4v5起点v1032∞∞v2∞0∞54v3∞60∞8v4∞∞∞02v5∞∞∞∞0v1v2v3v4v54232586第21页，共115页，2023年，2月20日，星期四2最小支撑树问题树及其性质图的支撑树(生成树)最小支撑树问题根树及其应用第22页，共115页，2023年，2月20日，星期四树及其性质树在现实中随处可见，如电话线架设、比赛程序、组织结构等。树：连通的无圈的无向图称为树。第23页，共115页，2023年，2月20日，星期四树的性质图G=(V,E)，p个点、q条边，下列说法是等价的(1)G是一个树(2)G连通，且恰有p-1条边(3)G无圈，且恰有p-1条边(4)G连通，但每舍去一边就不连通(5)G无圈，但每增加一边即得唯一一个圈(6)G中任意两点之间恰有一条链(简单链)第24页，共115页，2023年，2月20日，星期四图的支撑树(生成树)定义：设图T=(V,E’)是图G=(V,E)的支撑子图，如果T是一个树，则称T是G的一个支撑树。定理5：图G=(V,E)有支撑树的充分必要条件是G是连通的。第25页，共115页，2023年，2月20日，星期四找图中生成树的方法求支撑树的破圈法第26页，共115页，2023年，2月20日，星期四找图中生成树的方法求支撑树的避圈法深探法广探法第27页，共115页，2023年，2月20日，星期四最小支撑树问题赋权图(网络)：给定图G=(V,E),对G中的每一条边(vi,vj)，相应地有一个数wij，则称这样的图为赋权图。wij称为边(vi,vj)上的权。支撑树的权：若T=(V,E’)是G的一个支撑树，E’中的所有边的权之和称为支撑树的权，记为w(T)：w(T)=Σwij(其中(vi,vj)∈T)第28页，共115页，2023年，2月20日，星期四满足w(T*)=min(w(T))的树T*称为最小支撑树(最小树)。求最小树的方法求最小树的避圈法求最小树的破圈法第29页，共115页，2023年，2月20日，星期四根树及其应用有向树中的根树在计算机科学、决策论中有很重要的应用有向树：若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树。根树：有向树T，恰有一个结点入次为0，其余各点入次均为1，则称T为根树(又称外向树)。根树中入次为0的点称为根。根树中出次为0的点称为叶。入次和出次均大于0的点称为分枝点。由根到某一顶点vi的道路长度(设每边长度为1)，称为vi点的层次。第30页，共115页，2023年，2月20日，星期四在根树中，若每个顶点的出次小于或等于M，称这棵树为M叉树。若每个顶点的出次恰好等于M或者零，则称这棵树为完全M叉树。当M=2时，称为二叉树、完全二叉树。第31页，共115页，2023年，2月20日，星期四如图所示的树是根树。其中根、分枝点、叶；各点层次都标注在树上。这是一棵三叉树根叶分点枝第一层第三层第二层三叉树第32页，共115页，2023年，2月20日，星期四带权的二叉树T：令有s个叶子的二叉树T各叶子的权分别为pi，根到各叶子的距离(层次)为li(i=1,2,…,s)，这样二叉树T的总权数m(T)=Σpili。满足总权数最小的二叉树称为最优二叉树(也称Huffman树)。Huffman算法(D.A.Huffman最优二叉树算法)将s个叶子按权由小至大排序将二个具有最小权的叶子合并成一个分枝点，其权为两者之和，将新的分枝点作为一个叶子。转上一步，直到结束。第33页，共115页，2023年，2月20日，星期四例3：s=6，其权分别为4,3,3,2,2,1，求最优二叉树。123243365第34页，共115页，2023年，2月20日，星期四123243396515123243396515第35页，共115页，2023年，2月20日，星期四例4：最优检索问题。使用计算机进行图书分类。现有五类图书共∞万册，其中有A类50万册，有B类20万册，C类5万册，D类10万册，E类15万册。问如何安排分检过程，可使总的运算(比较)次数最小？解：构造一棵具有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。第36页，共115页，2023年，2月20日，星期四3最短路问题概述最短路算法——Dijkstra算法最短路算法——矩阵算法最短路算法——Floyd算法第37页，共115页，2023年，2月20日，星期四概述最短路问题就是在一个网络中，给定一个起点，要求找出其到另一点的且权数最小的通路。最短路问题是网络分析中最重要的最优化问题之一。最短路问题在实际分析中有广泛的应用，如管道铺设、运输路线选择、工厂布局等。有些问题看起来与地理方位无关，但通过适当转化也可以将其归结为最短路问题，如设备更新问题等。第38页，共115页，2023年，2月20日，星期四最短路问题的一般描述：对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)。第39页，共115页，2023年，2月20日，星期四最短路算法——Dijkstra算法最短路的标号算法是由E.D.Dijkstra于1959年提出的，也称Dijkstra算法，是目前公认的求解最短路问题的较好算法，但此算法要求网络中边的权wij≥0。第40页，共115页，2023年，2月20日，星期四Dijkstra算法步骤：(1)从起点出发，依次寻找与起点距离最近的相邻点，并以此最短距离作为该点的标号，每次寻找一个点。(2)若已经计算出起点到若干点S={v1,v2,…,vi}的最短距离，在找下一点时，要充分考虑到与S集合中的点的每一邻接点的可能，也就是说要考虑S集合中的每一点到其他点的距离，从中选出最短距离点。(3)重复上述过程，直到终点的标号被找到，则终止计算，找出最短路。第41页，共115页，2023年，2月20日，星期四例5：设有一批货物要从v1运到v7，每一边上的数字代表该段路线的长度，求最短的运输路线。v4v2v1v3v6v5v714425316227第42页，共115页，2023年，2月20日，星期四序号与S关联边距离集合S标号(0)d(v1)=0{v1}d(v1)=0(1)(v1,v2)(v1,v3)k12=d(v1)+l(v1,v2)=0+1=1k13=d(v1)+l(v1,v3)=0+4=4{v1,v2}d(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=6{v1,v2,v3}d(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=4{v1,v2,v3,v6}d(v6)=4v3第43页，共115页，2023年，2月20日，星期四序号与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=10{1,2,3,6,4}d(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=10{1,2,3,6,4,5}d(v5)=7v4,v6(6)(v5,v7)(v6,v7)k57=d(v5)+l(v5,v7)=7+2=9k67=d(v6)+l(v6,v7)=4+6=10{1,2,3,6,4,5,7}d(v7)=9v5最短运输路线：(1)v1-v2-v4-v5-v7或(2)v1-v2-v3-v6-v5-v7最短距离=d(v7)=9第44页，共115页，2023年，2月20日，星期四最短路算法——Dijkstra算法(PT标号)(1)对源vs标以永久P标号：P(vs)=0；对其他顶点标以临时T标号：T(u)=∞。(2)检查所有从P标号顶点到T标号顶点的弧。重新计算所有T标号的顶点的值T(v)=min(T(v),P(u)+c(u,v))(3)计算T(v)=min(T(i))，标号P(v)，记录对应u(4)重复(2)-(3)，直到全部顶点为P标号。最短路采用反向追踪；最短距离=P(vt)。第45页，共115页，2023年，2月20日，星期四k123456710*∞∞∞∞∞∞21*14∞∞∞∞33*2586∞4584*3∞55*271067*4,61079*51111111111111111111111111111111111111最短运输路线:(1)1-2-4-5-7;(2)1-2-3-6-5-7最短距离:d=9第46页，共115页，2023年，2月20日，星期四最短路算法——矩阵算法最短路的矩阵算法是将图表达成矩阵形式，然后用矩阵表计算出最短路。矩阵算法的基本思路与标号算法的基本思路一致。只不过一个标注在表上另一个标注在图上；标注在表上的便于计算机处理，标注在图上的直观第47页，共115页，2023年，2月20日，星期四矩阵算法的步骤：(1)将图表示成矩阵形式(2)确定起点行，标号为0，划去相应列(3)在已标号行且未划去的元素中，找出最小元素aij，圈起来，划去第j列，第j行标号aij，把第j行中未划去的各元素都加上aij(4)重复(3)，如果各行均已获得标号(或终点已经获得标号)，则终止计算。利用反向追踪，获得自起始点到各点的最短路；对应标号即为最短距离。第48页，共115页，2023年，2月20日，星期四例6：对上述例子利用矩阵算法求最短的运输路线。解答：(1)先根据图完成矩阵表示。v1v2v3v4v5v6v7v1014∞∞∞∞v2102475∞v3420∞∞1∞v4∞4∞02∞∞v5∞7∞2032v6∞51∞306v7∞∞∞∞260第49页，共115页，2023年，2月20日，星期四v1v2v3v4v5v6v70v1014∞∞∞∞v2102475∞v3420∞∞1∞v4∞4∞02∞∞v5∞7∞2032v6∞51∞306v7∞∞∞∞260(2)找到起始点v1，第1行标号0，划去第1列第50页，共115页，2023年，2月20日，星期四(3)在已标号行(第1行)且未划去的元素中(1,4)，寻找最小的元素(即为a12=1)。完成下列4项：圈：将a12圈起来；划：划去第2列；标：第2行标号1；加：第2行未划去的元素都加上1v1v2v3v4v5v6v70v1014∞∞∞∞1v2102+14+17+15+1∞v3420∞∞1∞v4∞4∞02∞∞v5∞7∞2032v6∞51∞306v7∞∞∞∞260第51页，共115页，2023年，2月20日，星期四(4)重复(3)。在已标号行(第1-2行)且未划去的元素中(4,3,5,8,6)，寻找最小的元素(即为a23=3)。完成下列4项：圈：将a23圈起来；划：划去第3列；标：第3行标号3；加：第3行未划去的元素都加上3v1v2v3v4v5v6v70v1014∞∞∞∞1v2103586∞3v3420∞∞1+3∞v4∞4∞02∞∞v5∞7∞2032v6∞51∞306v7∞∞∞∞260第52页，共115页，2023年，2月20日，星期四(5)重复(3)。在已标号行(第1-3行)且未划去的元素中(5,8,6,4)，寻找最小的元素(即为a36=4)。完成下列4项：圈：将a36圈起来；划：划去第6列；标：第6行标号4；加：第6行未划去的元素都加上4v1v2v3v4v5v6v70v1014∞∞∞∞1v2103586∞3v3420∞∞4∞v4∞4∞02∞∞v5∞7∞20324v6∞51∞3+406+4v7∞∞∞∞260第53页，共115页，2023年，2月20日，星期四(6)重复(3)。在已标号行(第1-3,6行)且未划去的元素中(5,8,7,10)，寻找最小的元素(即为a24=5)。完成下列4项：圈：将a24圈起来；划：划去第4列；标：第4行标号5；加：第4行未划去的元素都加上5v1v2v3v4v5v6v70v1014∞∞∞∞1v2103586∞3v3420∞∞4∞5v4∞4∞02+5∞∞v5∞7∞20324v6∞51∞7010v7∞∞∞∞260第54页，共115页，2023年，2月20日，星期四(7)重复(3)。在已标号行(第1-4,6行)且未划去的元素中(8,7,7)，寻找最小的元素(即为a45=a65=7)。完成下列4项：圈：将a45和a65圈起来；划：划去第5列；标：第5行标号7；加：第5行未划去的元素都加上7v1v2v3v4v5v6v70v1014∞∞∞∞1v2103586∞3v3420∞∞4∞5v4∞4∞07∞∞7v5∞7∞2032+74v6∞51∞7010v7∞∞∞∞260第55页，共115页，2023年，2月20日，星期四(8)重复(3)。在已标号行(第1-6行)且未划去的元素中(9,10)，寻找最小的元素(即为a57=9)。完成下列4项：圈：将a57圈起来；划：划去第7列；标：第7行标号9；加：第7行未划去的元素都加上9(全部划完)v1v2v3v4v5v6v70v1014∞∞∞∞1v2103586∞3v3420∞∞4∞5v4∞4∞07∞∞7v5∞7∞20394v6∞51∞70109v7∞∞∞∞260第56页，共115页，2023年，2月20日，星期四最短路算法——Floyd算法某些问题中，要求网络上任意两点之间的最短路，这类问题可以用Dijkstra算法依次改变起点的办法计算，但很繁琐。Floyd算法可以直接求取任意两点间最短路。Floyd算法又称为弗洛伊德算法，插点法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。该法由Floyd于1962年完成(RobertW.Floyd:Algorithm97:Shortestpath,CommunicationsoftheACM,1962年第5卷第6期)。第57页，共115页，2023年，2月20日，星期四Floyd算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd算法的时间复杂度为O(n3)，空间复杂度为O(n2)。Floyd算法，也有专业书籍称Floyd-Warshall算法(Floyd-WarshallAlgorithm)。第58页，共115页，2023年，2月20日，星期四Floyd算法(1)输入权矩阵D(0)=D=(dij)n×n，dij取值为如果(vi,vj)∈E，则dij=lij为vi到vj的距离如果(vi,vj)不属于E，则dij=∞(2)计算D(k)=(dij(k))n×n，其中dij(k)=min(dij(k-1),dis(k-1)+dsj(k-1))(3)D(n)=(dij(n))n×n中元素dij(n)就是vi到vj的最短路长。若D(p)=D(p-1)则也可结束。迭代步长p根据公式2p-1≤n-1≤2p估计第59页，共115页，2023年，2月20日，星期四例7：利用Floyd算法求上例中最短路。

v1v2v3v4v5v6v7v1v2v3v4v5v6v7

v1014∞∞∞∞v1013585∞

v2102475∞v21024639

v3420∞∞1∞v33206417D(0)=v4∞4∞02∞∞D(1)=v45460254

v5∞7∞2032v58642032

v6∞51∞306v65315305

v7∞∞∞∞260v7∞9742501111111111111111111111111111111111111111111111111111111v1v2v3v4v5v6v7v1v2v3v4v5v6v7v10135749v10135749v21024638v21024638v33206416v33206416D(2)=v45460254D(3)=v45460254v57642032v57642032v64315305v64315305v79864250v79864250第60页，共115页，2023年，2月20日，星期四例8：若某地7个村庄之间的交通道路如图所示。旁边数字为各村庄之间道路的长度。试求各村之间的最短距离。12345672223344456771第61页，共115页，2023年，2月20日，星期四解答0347∞∞∞03457111330324∞∞3032458430∞57∞4305569D(0)=72∞02∞6D(1)=5250236∞4520147452013∞∞7∞10211563102∞∞∞642013896320111111111111111111111111111111111111111111111111103457810034578103032457303245743055684305568D(2)=5250235D(3)=525023574520137452013856310285631021078532010785320第62页，共115页，2023年，2月20日，星期四例9：用Floyd算法计算有向图的最短路12345678910728612122424565104626884第63页，共115页，2023年，2月20日，星期四若v1→v4方向不变，则结果如下1234567891010886∞∞∞∞∞∞2∞04∞∞∞2∞∞∞3∞∞01072∞∞∞∞4∞∞∞0∞8∞∞∞∞D(0)=5∞6∞∞02∞12∞∞6∞∞∞∞∞0∞4∞∞7∞∞∞∞12∞05∞∞8∞∞∞∞∞∞∞0649∞∞∞6∞2∞∞0410∞∞∞∞∞∞5∞∞0111111111111111111111111111111111111第64页，共115页，2023年，2月20日，星期四1234567891010886151010∞∞∞2∞041411627∞∞3∞1301072∞6∞∞4∞∞∞0∞8∞12∞∞D(1)=5∞610∞028618166∞∞∞∞∞0∞41087∞18∞∞1214051198∞∞∞12∞890649∞∞∞6∞2960410∞∞∞∞17∞510∞0111111111111111111111111111111111111第65页，共115页，2023年，2月20日，星期四12345678910108861510101420182∞04141162713113∞130107215612104∞∞∞0∞821121816D(2)=5∞61018028612106∞∞∞162501341087∞1822171213051198∞27∞1221890649∞27∞6212960410∞2327221718510160111111111111111111111111111111111111第66页，共115页，2023年，2月20日，星期四12345678910108861510101420182∞04141162713113∞130107215612104∞3943033821121816D(3)=5∞61018028612106∞3135162501341087∞1822171213051198∞27311221890649∞27316212960410∞2327221718510160111111111111111111111111111111111111第67页，共115页，2023年，2月20日，星期四12345678910108861510101420182∞04141162713113∞130107215612104∞3943033821121816D(4)=5∞61018028612106∞3135162501341087∞1822171213051198∞27311221890649∞27316212960410∞2327221718510160111111111111111111111111111111111111第68页，共115页，2023年，2月20日，星期四若v1→v4方向改变，则结果如下12345678910108818151010142018220041411627131131613010721561210461414021816121816D(4)=5246101802861210622303016250134108723182217121305119818262612218906491220206212960410282327221718510160111111111111111111111111111111111111第69页，共115页，2023年，2月20日，星期四若v4→v1容量为-6，则结果如下1234567891010881815101014201828041411627131134120107214612104-622094481412D(4)=512610180286121061018181625013410871118191712130511986141412218906490886152960410162324221718510160111111111111111111111111111111111111第70页，共115页，2023年，2月20日，星期四4最大流问题基本概念最大流算法1——标号算法最大流算法2——改进标号算法最大流算法3——最小截集法最大流算法4——线性规划(Excel求解)第71页，共115页，2023年，2月20日，星期四基本概念给定一个有向图D=(V,A)，如果对于每一条弧a=(vi,vj)∈A，均有一个非负实数cij=c(vi,vj)=c(a)∈C与之对应，称c(a)为弧a的容量；称V中入次为0出次大于0的顶点vs为源(发点)，称入次大于0出次为0的顶点vt为汇(收点)，入次和出次均大于0的顶点为中间顶点，则称这个图为容量网络，有时也根据运输情况称为运输网络，简称网络，记为N=(V,A,C,vs,vt)。第72页，共115页，2023年，2月20日，星期四一般地，如果网络N=(V,A,C,vs,vt)中，定义在弧集A上的一个函数f满足：(1)对于任意一条弧(vi,vj)，都有0≤fij≤cij；(2)对于中间顶点vk，Σfik=Σfkj；(3)对于源vs和汇vt，存在Σfsj=Σfit=Vf，则称f为N的一个网络流，简称流，称Vf为f的流量。对于给定的运输网络，一个十分实际的问题是如何求得该网络中流量最大的网络流，简称最大流。第73页，共115页，2023年，2月20日，星期四设μ是从源vs到汇vt的一条链，定义μ的方向是从vs到vt。称μ上与μ同向的弧为前向弧，记前向弧的集合为μ+，称μ上与μ反向的弧为反向弧，记反向弧的集合为μ-。设μ是网络N中从源vs到汇vt的一条链，f是N的一个网络流，若对于任一a∈μ+，f(a)<c(a)，对于任一a∈μ-，f(a)>0，则称μ是网络N中关于流f的一条增广链。第74页，共115页，2023年，2月20日，星期四设μ是网络N中关于流f的一条增广链，可以采用如下方法改进流f使流量Vf增大。(1)令θ=min{c(a)-f(a)|a∈μ+,f(a)|a∈μ-}(2)作g(a)=f(a)+θ,a∈μ+f(a)-θ,a∈μ-f(a),其他得到g一定满足网络流的三个条件，所以g仍然为N中的网络流，而Vg=Vf+θ>Vf，流量增大。第75页，共115页，2023年，2月20日，星期四最大流算法1——标号算法(1)给出初始流f=0(2)令l(vs)=+∞，S={vs}，B=φ，T=V-S(3)考察S-B中的顶点u若v∈T，前向弧(u,v)满足f(u,v)<c(u,v)，给顶点v标号[u,+,l(v)]，其中l(v)=min{l(u),c(u,v)-f(u,v)}，并将v吸纳入S若v∈T，弧(v,u)满足f(v,u)>0，给顶点v标号[u,-,l(v)]，其中l(v)=min{l(u),f(v,u)}，并将v吸纳入S第76页，共115页，2023年，2月20日，星期四(4)若对所有v∈T，前向弧(u,v)和反向弧(v,u)均检查完毕，将检查完的顶点u并入B，转(3)(5)若vt进入S，则必然存在从vs到vt的增广链μ，反向追踪得到μ，且θ=l(vt)，令g(a)=f(a)+θ，a∈μ+f(a)-θ，a∈μ-f(a)，其他Vg=Vf+θ，转(2)(6)若S-B=φ，vt不能进入S，则f已是网络最大流第77页，共115页，2023年，2月20日，星期四最大流算法2——改进标号算法(1)对弧的容量加以改进。每一条弧a=(u,v)起点端标上流量c(u,v)，终点端标上0；若为双向弧，则都标上c(u,v)。(2)寻找增广链μ。找出一条从源vs到汇vt的路μ，要求这条路上每一条弧顺流方向的容量都大于0。μ存在，转(3)；μ不存在，停止，最大流Vf=Σθ。(3)计算θ=min{c(u,v)|a=(u,v)∈μ}(4)修改标号。对μ上每个弧都修改其标号：顺流容量减少θ，逆流容量增加θ。返回(2)第78页，共115页，2023年，2月20日，星期四最大流算法3——最小截集法(1)设vs∈V1,vt∈V2,V1∩V2=φ,V1∪V2=V(2)计算fi=∑c(u,v)(u∈V1,v∈V2,(u,v)∈E)(3)调整V1和V2，转(2)(4)遍历各种组合，Vf=min(fi)上述有关最小截集法是基于最大流量最小截集定理：最大流量=最小截集容量第79页，共115页，2023年，2月20日，星期四最大流算法4——线性规划设过弧a=(i,j)的流量是f(i,j)，容量c(i,j)。则必有0≤f(i,j)≤c(i,j)。又由于顶点可以分成三类：(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)=0故应有网络最大流的线性规划模型如下maxf=∑f(s,i)∑f(k,j)-∑f(i,k)=0(k∈V,k≠vs,k≠vt)f(i,j)≤c(i,j)f(i,j)≥0第80页，共115页，2023年，2月20日，星期四例101234564482214679第81页，共115页，2023年，2月20日，星期四解答1——最小截集序号V1V2c(u,v)fiYVf(1)12,3,4,5,6c(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)=817(3)1,32,4,5,6c(1,2)=4；c(3,4)=2c(3,5)=28Y(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,56c(4,6)=7；c(5,6)=916第82页，共115页，2023年，2月20日，星期四解答2——线性规划(Excel求解)ABCDEFGH1FromToCaptionFlowNodesNetFlowCondition212441831384200423403005244440062510500734226-88352294677105461115691=SUMIF($A$2:$A$11,F2,$D$2:$D$11)-SUMIF($B$2:$B$11,F2,$D$2:$D$11)第83页，共115页，2023年，2月20日，星期四5最小费用最大流网络D=(V,A,C)的每一个弧(vi,vj)∈A，除了容量cij=c(vi,vj)外，还给定单位流量的费用bij=b(vi,vj)≥0。所谓最小费用最大流问题就是要求一个最大流f，使流的总输送费用b(f)=∑bijfij取极小值。对增广链μ，若调整流量θ=1，那么新可行流f’的费用比原可行流f的费用增加b(f’)-b(f)=[∑bij(fij’-fij)|(i,j)∈μ+]-[∑bij(fij’-fij)|(i,j)∈μ-]=[∑bij|(i,j)∈μ+]-[∑bij|(i,j)∈μ-]第84页，共115页，2023年，2月20日，星期四可以证明，若f是流量为v(f)的所有可行流中费用最小者，而μ是关于f的所有增广链中费用最小的增广链，那么沿着μ去调整f，得到的可行流f’就是流量为v(f’)的所有可行流中的最小费用流。当f’是最大流时，就是最小费用最大流。由于bij≥0，所以f=0必定是流量为0的最小费用流。这样，总可以从f=0开始，寻找对应于v(f)的最小费用流。设已知f是流量v(f)的最小费用流，余下的问题是如何寻找关于f的最小费用增广链。第85页，共115页，2023年，2月20日，星期四构造一个赋权有向图W(f)，其顶点是原网络D的顶点，而把D中每一条弧(vi,vj)变成两个相反的弧(vi,vj)和(vj,vi)，定义W(f)中的权wij为bij,若fij<cij+∞,fij=cij定义W(f)中的权wji为-bij,fij>0+∞,fij=0于是在网络D中寻求关于f的最小费用增广链就等价于在赋权有向图W(f)中寻求从vs到vt的最短路。第86页，共115页，2023年，2月20日，星期四最小费用最大流算法(1)若在第k-1步中得到最小费用流f(k-1)，则构造赋权有向图W(f(k-1))(2)寻求从vs到vt的最短路。若不存在，则f(k-1)就是最小费用最大流；否则转(3)(3)在原网络D中得到增广链μ，对f(k-1)调整量为θ=min[min(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)不属于μ(4)重复上述步骤第87页，共115页，2023年，2月20日，星期四例11求如下网络D的最小费用最大流。弧旁数字为(bij,cij)。vsv2v3vtv1(4,10)(1,8)(2,5)(1,7)(6,2)(3,10)(2,4)第88页，共115页，2023年，2月20日，星期四解答(1)取f(0)=0为初始可行流。(2)构造赋权有向图W(f(0))，并求出从vs到vt的最短路：vs-v2-v1-vt，距离d=4。(3)原图中与这条最短路相应的增广链μ={vs,v2,v1,vt}。(4)在μ上调整。θ=min(8,5,7)=5，计算fij(1)。转(2)vsv2v3vtv14121632W(f(0))vsv2v3vtv10555000f(1),v(f(1))=5第89页，共115页，2023年，2月20日，星期四(5)构造赋权有向图W(f(1))，并求出从vs到vt的最短路：vs-v1-vt，距离d=5(6)原图中与这条最短路相应的增广链μ={vs,v1,vt}(7)在μ上调整。θ=min(10,2)=2，计算fij(2)。转(2)vtvsv2v3v12557000f(2),v(f(2))=7vsv2v3vtv141-21632W(f(1))-1-1第90页，共115页，2023年，2月20日，星期四(8)构造赋权有向图W(f(2))，并求出从vs到vt的最短路：vs-v2-v3-vt，距离d=6(9)原图中与这条最短路相应的增广链μ={vs,v2,v3,vt}(10)在μ上调整。θ=min(3,10,4)=3，计算fij(3)。转(2)vtvsv2v3v12857033f(3),v(f(3))=10vsv2v3vtv141-2632W(f(2))-1-1-4第91页，共115页，2023年，2月20日，星期四(11)构造赋权有向图W(f(3))，并求出从vs到vt的最短路：vs-v1-v2-v3-vt，距离d=7(12)原图与这条最短路相应的增广链μ={vs,v1,v2,v3,vt}(13)在μ上调整。θ=min(1,7,1)=1，计算fij(4)。转(2)vtvsv2v3v13847044f(4),v(f(4))=11vsv2v3vtv14-2632W(f(3))-1-1-4-2-3第92页，共115页，2023年，2月20日，星期四(14)构造赋权有向图W(f(4))，发现没有从vs到vt的最短路，停止计算。故f(4)为最小费用最大流。结论：最小费用Cost=3*4+8*1+4*2+4*3+4*2+7*1=55最大流f=3+8=7+4=11vsv2v3vtv14-263W(f(4))-1-1-4-2-32第93页，共115页，2023年，2月20日，星期四最小费用最大流的线性规划解法ABCDEFGHI1FromToCaptionFlowCostNodesNetFlowCondition2vsv11034vs11113vsv2881v1004v1v3206v2005v1vt771v3006v2v1542vt-117v2v310438v3vt442955(1)Max(2)Min第94页，共115页，2023年，2月20日，星期四最小费用最大流改进算法(1)对弧(vi,vj)的标注(cij,bij)加以改进靠近vi一端的标号(cij,bij)靠近vj一端的标号(0,-bij)原弧变为边，无方向(2)以bij为权(靠近vi端的cij>0)寻找最短路μ，若无则停止计算调整量pf=min{cij|(i,j)∈μ}调整：vi端cij变为cij-pf，vj端的cij变为cij+pf重复本节各步骤(3)结果与初始图比较得到流量图和总费用第95页，共115页，2023年，2月20日，星期四例12：计算上图的最小费用最大流。解答：(1)重新标号，得到无向图(2)以bij为权，计算最短路μ={s,2,1,t}vsv2v3vtv1(10,4)(8,1)(5,2)(7,1)(2,6)(10,3)(4,2)(0,-4)(0,-1)(0,-2)(0,-3)(0,-6)(0,-1)(0,-2)第96页，共115页，2023年，2月20日，星期四(3)pf=min(8,5,7)=5(4)调整标号(5)计算最短路μ={s,1,t}vsv2v3vtv1(10,4)(3,1)(0,2)(2,1)(2,6)(10,3)(4,2)(0,-4)(5,-1)(5,-2)(0,-3)(0,-6)(5,-1)(0,-2)第97页，共115页，2023年，2月20日，星期四(6)pf=min(10,2)=2(7)调整标号(8)计算最短路μ={s,2,3,t}vsv2v3vtv1(8,4)(3,1)(0,2)(0,1)(2,6)(10,3)(4,2)(2,-4)(5,-1)(5,-2)(0,-3)(0,-6)(7,-1)(0,-2)第98页，共115页，2023年，2月20日，星期四(9)pf=min(3,10,4)=3(10)调整标号(11)计算最短路μ={s,1,2,3,t}vsv2v3vtv1(8,4)(0,1)(0,2)(0,1)(2,6)(7,3)(1,2)(2,-4)(8,-1)(5,-2)(3,-3)(0,-6)(7,-1)(3,-2)第99页，共115页，2023年，2月20日，星期四(12)pf=min(8,5,7,1)=1(13)调整标号(14)不存在最短路，停止结论：Cost=12+8+8+12+7+8=55；f=3+8=11vsv2v3vtv1(7,4)(0,1)(1,2)(0,1)(2,6)(6,3)(0,2)(3,-4)(8,-1)(4,-2)(4,-3)(0,-6)(7,-1)(4,-2)第100页，共115页，2023年，2月20日，星期四6中国邮递员问题一笔划