图与网络分析.ppt

1,运筹学,图与网络分析,第十章 图与网络,赵 玮,3,主要内容：,10.1 基本概念 10.2 最短路问题 （一）Bellman最优化原理 （二）Dijustra算法（双括号法） （三）通信线路布施问题 （四）设备更新问题 10.3 最小生成树 （一）基本概念与理论 （二）Kruskal算法（加边法、破圈法） （三）丢边法（破圈法）,4,主要内容：,10.4 最大流问题 （一）基本概念 （二）双标号算法 10.5 最小费用最大流 （一）基本概念 （二）求解算法,5, 10.1 基本概念,1 图 def1：一个无向图（简称为图）G是一个有序的二元组，记为G=(V, E)。其中 V=V1Vn称为G的点集合，E=(eij)称为G的边集合，evj为连接VV与Vj的边。,6,若N和E均为有限集合，则称为G为有限图，否则称无限图。 若G中既没有有限回路（圈），也没有两条边连接同一对点，则称G为简单图。如右图之（a），右图之（b）不是简单图。 若G为简单图，且G中每个点对之间均有一条边相连，则称G为完全图。如图（a）是简单图，但不是完全图。,图 a,图 b,7,def 2：一个有向图G是一个有序的二元组，记为G=(V, A)，其中V=(V1V2Vn)称为G的点集合，A=aij称为G的弧（有向边）集合，aij是以Vi指向Vj的一条弧。 |V|=n表示G中节点个数为n，此节点个数n也称为图G的阶 |A|=m表示有向图G中弧的个数为m 任一顶点相关联（连接）的边的数目称为该顶点的次数,8,2 连通图 def 3：在有向图G中,一个点和边的交替序列Vi eij VjVk ekl Vl 称为G中从点Vi到Vl的一条路，记为A，其中Vi为此路A的起点，Vj为路A的终点；若路A的起点与终点重合,则称A为回路；又若G中点Vi与Vj间存在一条路，则称点Vi与Vj是连通的；若G中任何二点都是连通的，则称G为连通图，或图G为连通的。在无向图中有对应的概念。,9,3 子图 def 4：设有两个图：G1= (V1, E1) ，G2= (V2, E2)若有 ，则称G1为G2的子图， 记作 ；若有 V1=V2而 ,则称图 G1= (V1, E1) 是图G2= (V2, E2)的生成子图（支撑 子图）。,10,例：下示图G1是图G的子图，图G2是图G的生成子图。,V1,V2,V4,（a）图G,（b）图G1,（c）图G2,11,4 赋权图（加权图）与网路 def 5：设G是一个图（或有向图），若对G的每一条边（或弧）eij都赋予一实数ij，称其为该边（弧）的权，则G连同其他弧上的权集合称为一个赋权图，记作G= (V, E, W) 或G= (V, A, W)，此中W=ij，ij为对应边（弧）eij的权。若G= (V, E, W) （或(V, A, W)）为赋权图，且在G的V中指定一个发点（常记为Vs）和一个收点（记为Vt），其余点称为中间点，则称这样指定了发点与收点的赋权图G为网络。,12, 10.2 最短路问题,def 6：设G =（V, A, W）为一个赋权有向图，Vs为指定发点，Vt为指定收点，其余为中间点，P为G中以Vs到Vt的一条有向路，则称 为路P的长度，若有 则称 为G中从Vs到Vt的最 短路， 为该最短路的长度（此中F为G中 所有从Vs到Vt的全体有向路的集合）。,13,最短路问题在企业厂址上选择，厂址布 局，设备更新，网络线路安装等工程设计与 企业管理中有重要应用。,14,（一）Bellman最优化原理,1 命题1：若P是网络G中从Vs到Vt的一条最小路，Vl是P中除Vs与Vt外的任何一个中间点，则沿P从Vs到Vl的一条路P1亦必是Vs到Vl的最小路。,Vs,V1,Vl,V2,Vt,P2,P1,15,证明（反证）： 若P1不是从Vs到Vl的最小路，则存在另一条 Vs 到Vl的路P2使W(P2)W(P1)，若记路P中从Vl到Vt的路为P3。则有W(P2) + W(P3)W(P1) + W(P3)=W(P)，此说明G中存在一条从Vs沿P2到Vl沿P3再到Vt的更小的一条路，这与P使G中从Vs到Vt的一条最小路矛盾。,16,2 算法思想： 设G中从Vs到Vt的最小路P：VsVjVkVt，则由上述命题知：P不仅是从Vs到Vt的最小路，而且从Vs到P中任意中间点的最短路也在P上，为此可采用如下求解思路： 为求得Vs到Vt的最短路，可先求得Vs到中间点的最短路，然后由中间点再逐步过渡到终点Vt。,17, 在计算过程中，需要把V中“经判断为最短路 P途径之点i”和“尚未判断是否为最短路P途径 之点j”区分开来，可设置集合I和J,前者归入 I，后者归入J，并令算法初始时，I中仅包含 Vs，其他点全在J中，然后随着求解过程的进 行，I中的点逐渐增加（相应J中的点逐渐减 少），直到终点Vt归入I（相应J=），此时 迭代结束。I称为已标号集合,J称为未标号集合。,18, 为区分中间点Vk是否已归入I中以及逆向求解最短路的方便，可在归入I中的点Vj上方给予双标号（lj, Vk），此中lj表示从Vs到Vj最短路的距离，而Vk则为从Vs到Vj最短路P中Vj的前一途径点。 为在计算机上实现上述求解思想，还需引入G中各点间一步可达距离阵D=(dij)nn，此中 |V|=n,19, 以下介绍的是适用于弧权为正值的有向网络中求最短有向路的Dijkstra算法，又称双括号法。事实上该算法亦适用于弧权为负值的有向网络求最短路问题。,20,由图G建立一步可达距离阵D=(dij)nn,给V1(Vs)括号(l1,Vk)=(0,s)给出已标号集合I和未标号集合J的元素,对于给定的I和J，确定集合A=aij |ViI，Vj J,计算距离,给Vk括号(lk ,Vh) lk=lh + Whk,I=I + Vk J=J Vk,A= 或 J,从Vt 逆向搜索双括号，可得最小路P途径各点及最小路距离,END,N,Y,（二）Dijkstra算法（双括号法）,图 一,21,例1（教材208页）求G的最短路， 图G形如下形。 解：利用上述Dijkstra算法步骤可得表一所示求 解过程，并有最短路P：V6 V4 V3 V1， 最短距离|P|=2+1+5=8。,5,1,2,图（一）,22,表一（例1 求解过程）,23,例2 求如下G之最小路,V1,V4,V2,V6,V8,V5,V7,3,3,3,V3,6,6,6,6,1,1,7,图 二,7,4,2,24,解,表 二,25,表三 （例2求解过程）,26,由表三知 V1 V8 最短路P1：V8 V6 V2 V1 最短路P2：V8 V6 V5 V3 V2 V1 最短路长 |P1|=2+7+4=13 |P2|=2+3+3+1+4=13,4,4,7,1,2,3,3,2,27,（三）通信线路布设问题（教材P209）,例3. 甲、乙两地之间的公路网络如图三，电信公司准备在甲、乙两地沿公路沿线架设一光缆线，问应如何架设此线路方案，以使光缆线路架设总长度最短？,图 三,28,解：本例之一步可达距离阵如,G=V,E,W,V=V1V2V3V4V5V6V7，本例G为无向图，求解过程见表四,W=,29,表四 （例3求解过程）,30, 由表四可得 最短路P： V7 V6 V5 V3 V1 最短距离 |P|=10+4+2+6=22 还可得到自V1（甲）到任一中间点之最短路，例如 V1 V4 最短路由表四可知为 P14 V4 V5 V3 V1 |P14|=18,6,2,4,10,31,（四）设备更新问题（教材P212）,例4. 某公司设备管理部门欲制定一个五年期某设备的更新计划，要求给出这五年中购置该设备的年份及购置新设备的使用年限。 在此五年中购置该设备的年初价格见表五，设备使用不同年限的维护费见表六。,32,表五 （单位：万元）,表六 （单位：万元/年）,33,解：设 Vi i年初购进一台新设备 aij i年初购进之新设备使用到第j年初（j-1年末） iji年初购进之新设备使用到第j年初（j-1年末） 之总费用 根据表五与表六之有关数据可计算 ij 详可 参见表七；由表七可得W阵如表八；由表八可得 有向图四；将表八可转换成一步可达阵如表九， 求解过程见表10。,34,表七 （W 计算过程）,35,36,表八 费用阵（单位：万元）,j,i,ij,37,图四 （设备更新有向图）,38,表 九,39,表10 设备更新求解过程,min,40,41,由表10可知最短费用流（相当于最短路） P： V6 V3 V1 | P| = 53万元 V4,42,结论： 公司五年期设备更新方案有两个：A与B，总费用均为53万元。 A 方案：第1年初购置设备使用到第3年初（第2年末），第3年初再购置新设备使用到第 5年末（第6年初） B 方案：第1年初购置设备使用到第4年初（第3年末），第4年初再购置新设备使用到第5年末（第6年初）,43,10.3 最小生成树,最小生成树在网络（电信网、公路网等）设计与企业管理中有重要应用。,44,（一）基本概念与理论,def 7：无圈的连通图（无向图）称为树，常 记为符号T。如图五的（a）为树，（b）有圈， （c）不连通，故（b）（c）均非树。,（a）,（b）,（c）,图 五,45,def 8：若T是图G的一个生成子图而且又是一 棵树，则称树T是图G的一个生成树（又称支 撑树）；又若树T=(V1,E1)为图 G=(V,E,W)的 一个生成树，令 称为树T的权 （或长度），则G中具最小权的生成树称为G 的最小生成树，亦即若有 则有 T* 为G 的最小生成树，此中F为G的全 体生成树的集合。,46,Th1：设T=(V,E)是|V| 3的一个无向图，则下列六个关于树的定义是等价的： T连通且无圈 T的任何两个顶点间均必有一条且仅有一条通 路相连 T连通且有n-1条边，此中n= |V| T有n-1条边且无圈，此中n= |V| T无圈，但在T中任两个不相邻的顶点间添加 一条边，则可构成一条回路 T连通，但去掉任一条边后就不连通，即树T 是连通且边数最小的图,47,（二）Kruskal算法（加边法，破圈法）,1. 算法思想： 由Th1(4)结论：若|V| = n ，则树T有n-1条边且 无圈 由def 8，最小生成树T*是具有最小权的生成树 故可E中各边按权大小排列设为W1 W2 Wm，对应？边依次为a1,a2, am，然后将 a1,a2, 依次进入集合S，直到获得S的生成树T 为止（树的判断可由Th1(4)结论），则此树T必 为最小生成树。,48,设G=(V,A,W)， |V| = n ， |A| = m S 待生成的集合 i S中进入最小生成树的边序号 j 逐个进入S的G的边序号 ei+1 S中进入最小生成树的边,表 11,49,对G中各边按权大小顺序排列，不妨设为W1 W2 Wm,填写Wj对应的各边aj 表11,S= ，i = 0，j=1,aj S构成回路？,|S| = n-1,ei+1=aj S=ei+1 S i=i +1 j=j+1,j=j+1,T*=S 打印T*,END,Y,Y,N,N,图 六,50,例5（教材P218） 某大学准备对其所属的 7 个学院办公室计算机联网这个网络的可能联通的途径如图七所示，图中V1，V7表示7个学院办公室，边eij为可能联网的途径。边上所赋的权数为这条路线的长度（单位：百米）。试设计一局域网既能联结七个学院办公室，又能使网络线路总长度为最短。,51,G=V,E,W, |V| =7, |E| = 11 W=(ij) ij见图 解：依据各边权自小到大排列建立表12，求解过程见表13，由表13得知最小生成树 T*=a1,a2,a3,a4,a5,a9 W(T*)=1+2+3+3+7=19,图七,表 12,52,表13 （例5求解过程）,53,例 6. 利用加边法求图八所示的无向图G之最小生成树,解：G=V,E,V， |V| = 5 |E| = 8,表 14,V1,V2,V5,V3,V4,1,2,2,3,4,4,4,2,图 八,54,表 15 （例6求解过程）,55,（三）丢边法（破圈法）,1. 算法原理： 丢边法与加边法相反，加边法是以不形成回路为准则将S=逐步加边以形成树，而由于按边权愈小愈优先加进去，故为最小生成树，而丢边法则是S= E以不形成回路为准则逐步丢边以形成树，由于是按边权愈大愈优先丢掉，故同样为最小生成树。,56,设G=(V,E,W)， |V| = n， |E| = m， S 待生成的集合（逐步丢边） i S中丢掉边的序号 j S中保留边的序号 ei+1 S中丢到的边 e1 S中丢到的边的全体（集合） fj+1 S中保留的边 D S中保留边的集合,57,由于边个数为m，树含边的个数为n-1，故丢 掉（形成回路）边的个数为 m-(n-1)=m-n+1，以 此为程序出口，标志着最小生成树形成 依次从大到小按列同例5表12。,58,G=(V,E,W)，|V| = n，|E| = m， S= E，i=0，j=0，E1=, D=,选S中最大权之边,S中是否有包含al 的一个回路,i=i +1 ei=al S= S -ei E1=E1ei,T*=S-E1 打印T*的边序列,j=j +1 fj=al D=Dfi+1,i m-n-1,END,N,N,Y,Y,图 九,59,例6. （同例5）用丢边法求解 求解过程见表16，由于m-n+1=11-(7-1)=5 故i=5时程序终止，由表知 T*=S-e1e5=a1,a2,a3,a4,a5,a9与前加边法求解 相同，详可参考教材P218的六个图。,60,表16 （例6求解价格）,5=i=m-n+1,61, 10.4 最大流问题,由前知，一个指定了收点和发点的赋权图 G 称为网络，在网络设计中研究网络的流量具有现实意义，如交通网络的车流流量，通信网络中的话务流量，金融网络中的现金流量，控制网络中的信息流量，供电网络中的电流流量等。人们也常常希望知道在既定网络中能允许通过的最大流量，以便对该网络的利用程序作出评价，这就是所谓的网络最大流问题。求解方法有双标号法，对偶图法等。,62,1网络中弧的容量与流量 def9：对于一个指定收、发点的赋权有向（无向）图或网络N（V，A，C），弧aijA的最大允许通过能力称为该弧的容量，记为cij（cij0），全体cij构成之集合记为C；而通过边aij的实际流量成为流量，记为fij，故有0fijcij。显然若fijcij则网络N在aij边将发生堵塞现象，这是人们希望能避免的现象。,（一）基本概念,63,2可行流与最大流 def10：设有网络N（V，A，C），称 f =fijaijA为网络N上的流函数，简称网 络流；满足如下条件的网络流称为可行流，其 中v（f）为网络N可行流的总流量（净流入量）。,64,（1）容量限制条件：,（2）流量守恒条件：,说明：进入节点vj的流量自节点vj流出的流量； fij0之零流亦满足上述条件，故零流以为可行流。,65,3顺向弧、逆向弧与可增路 def11：设f是网络N的一可行流，P是N中从vs到vt的一条路，对于路P途经的各弧，若弧的方向与路的方向相同，则称该弧为顺向弧，若弧的方向与路的方向相反，则称该弧为逆向弧。若在路P的一切顺向弧（vi，vj）上有fijcij，在路P的一切逆向弧（vj，vi）上有fji0，则称路 P是一条关于f的可增路。,66,说明： （1）由def 11得知：若在路P中，存在一条顺向弧（vi，vj）有fijcij（此时称弧为饱和弧），或者在路P中存在一条逆向弧（vj，vi）有fji0，则称路P为不可增路； （2）在图10所示的网络N中有一可行流f=fijaijA，用蓝字标记，红字标记各弧的容量cij。表17给出了四条从v1到v7的路是否可增路的判别理由。（此f满足流量守恒条件与容量限制条件，如,67,图 10,68,表 17,69,（3）可增路的内涵可通过下例得知 在图10之可行流f中，对于路 v1v2v5v3v6v7 途经的各弧中，若f12，f23增加一个单位流量，f35减少一个单位流量，利用流量守恒条件，可得一个如图11的新的可行流 ，并有v（ ）= 109 = v（f）。,图11,70,由上可知在def11中可增路要求顺向弧 fijcij之条件，实际上说明沿该弧（vi，vj）还 可提高流量 ijcijfij0，另一方面，为提 高流量v（f）还要求该路的逆向弧降低流量，而 fji0正说明了该逆向弧可降低fji个单位。,71,1算法思想（见图12）,图 12,（二）双标号算法,72,图13,N,Y,Y,N,2调整步骤 （见图13）,73,3标号与调整规则 （1）标号规则： 1o 若（vi，vj）为顺向弧，且fij0，则给vj标 号（vi，l（vj），其中l（vj） min（l（vi），fji）； 3o 若（vi，vj）为顺向弧但fijcij或（vi，vj） 为逆向弧但fji0，此时沿该弧的路线停止标号。,74,（2）调整规则： 1o 若（vi，vj）为顺向弧，则对pl路径的顺向弧作调整，其调整量ijfijl（v）； 2o 若（vi，vj）为逆向弧，则对pl途经的逆向弧作调整，其调整量jifjil（v）； 3o G中不在pl路上的各弧不作调整。,75,4例7（教材P219） 某石油公司拥有一管道网络，使用此管道网络可将石油从采地v1运往销地v7，由于各地的地质条件等不同，因而其管道直径有所不同，从而使各弧的容量cij（单位：万加仑/小时）不同，对于如图14所示的管道网络N（V，A，C），问每小时从v1往v7能运送多少加仑石油？,76,图 14,77,解1：若设弧（vi，vj）上的流量为fij，网络N上总流量为F，则可建立如下LP： max F f12 f14 f12 f23 f25 f14 f43 f46 f47 f23 f43 f35 f36 st f25 f35 f57 f36 f46 f67 f47 f57 f67 f12 f14 fijcij i16，j17 fij0 i16，j17,C阵,78,利用单纯形法可解得最大流： f*f125，f145，f232，f253， f432，f461，f472，f352， f362，f575，f673，v（f*）10,79,解2：（采用双标号法求最大流） 求解中寻找了五条可增路，其标号过程与增流过程见表18，表18中各可增路及其流量调整过程见图15。 求解结果与解1相同。,80,81,82,83,84,图15,85,表18 （例7求解过程）,已无可增路 END,86, 10.5 最小费用最大流,在很多网络（电信网络、运输网络、计算机网络）的分析与设计问题中，人们除关心网络的系统容量外还要考虑费用问题，以便建立一个高效、低耗的网络系统。这就是最小费用最大流问题的研究。,87,def12：设网络NV, A，除对每一弧aA规定了其容量c(a)外，还给定一个数b(a) 0称为弧a的单位流量费用，即有网络NV, A, c, b称其为带费用（代价）的网络。设f是N上的一个可行流（从vs到vt