《运筹学第三之图与网络分析课件.pptx》由会员分享，可在线阅读，更多相关《运筹学第三之图与网络分析课件.pptx（100页珍藏版）》请在三一办公上搜索。
1、图与网络分析(Graph Theory and Network Analysis),图与网络的基本知识,最短路问题,树及最小树问题,最大流问题,最小费用最大流问题,哥尼斯堡“七桥”难题,一笔画问题,问题：一个游者怎样才能一次连续走过这七座桥且每座桥只走一次，回到原出发点。,欧拉用A,B,C,D四点表示河的两岸和小岛，用两点间的联线表示桥。七桥问题变为：,从A,B,C,D任一点出发，能否通过每条边一次且仅一次，再回到该点?,一、图与网络的基本知识（一）、图与网络的基本概念,图1,图2,4.一条边的两个端点如果相同,称此边为环。,6.不含环和多重边的图称为简单图，含有多重边的图称为多重图。,8.有
2、向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。,5.两个点之间多于一条边的，称为多重边.,7.每一对顶点间都有边相连的无向简单图称为完全图。,有n个顶点的无向完全图记作Kn,次为零的点称为弧立点，次为1的点称为悬挂点。连结悬挂点的边称为悬挂边。次为奇数的点称为奇点，次为偶数的点称为偶点。,定理2 任何图中，次为奇数的顶点必为偶数个。,有向图中,所有顶点的入次之和等于所有顶点的出次之和,定理1 任何图中，顶点次数的总和等于边数的2倍。,图3,一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图都可以分为若干个连通子图，每一个子图称为原图的一个分图。,v4,v6,e2
3、,e1,e3,e4,e5,e6,e7,e8,e9,e10,图4,例,权矩阵为：,邻接矩阵为：,二、树及最小树问题 已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。,1、连通且不含圈的无向图称为树。,树中次为1的点称为树叶，次大于1的点称为分支点。,一个图G 有生成树的充要条件是G 是连通图。,用破圈法求出下图的一个生成树。,（一）破圈法,（二）避圈法,某六个城市之间的道路网如下图所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最短。,求最小树的方法：,一、破圈法：在给定连通图G中，任取一圈，去掉一条最大权边（若有两条或两条以上的
4、权均是最大权边，则任意去掉其中一条），在余图中任取一圈，去掉一条最大权边，重复下去，直到余图中无圈为止，即得到图G的最小树。,二、避圈法：在给定连通图G中，任取权值最小的一条边，在未选边中选一条权值最小的边，要求所选边与已选边不构成圈，重复下去，直到不存在与已选边不构成圈的边为止，已选边与顶点构成的图T即为所求的最小树。,v1,v2,v3,v4,v5,1,4,2,3,1,3,5,2,破圈法求最小树：,v1,v2,v3,v4,v5,1,4,2,3,1,3,5,2,避圈法求最小树：,三、最短路问题,最短路问题是重要的优化问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管道铺设、线路安排、厂
5、区布局、设备更新等，而且经常被作为一个基本工具，用于解决其他的优化问题。,Dijkstra标号法,例：如图所示是某地区交通运输示意图，问从v1出发，经那条路线到达v8,才能使总行程最短?,例2、用Dijkstra算法求下图从v1到v6的最短路。,解（1）首先给v1以P标号，给其余所有点T标号。,（2）,（3）,（4）,（5）,（6）,（7）,（8）,（9）,（10）,反向追踪得v1到v6的最短路为：,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,求从1到8的最短路径,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4
6、,6,8,2,X=1,w1=0,min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4,p4=1,p4=1,p1=0,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,4,min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4,p2=2,p1=0,p4=1,p2=2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,min c13,c23,c25,c47=min 0+3,2
7、+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6,p6=3,p2=2,p4=1,p1=0,p6=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7,p7=3,p2=2,p4=1,p1=0,p6=3,p7=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min c23,c25,c75,c78=min 2+6,2+
8、5,3+3,3+8=min 8,7,6,11=6X=1,2,4,5,6,7,p5=6,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8X=1,2,3,4,5,6,7,p3=8,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4
9、,6,7,min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=10X=1,2,3,4,5,6,7,8,p8=10,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,8,1到8的最短路径为1，4，7，5，8，长度为10。,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,求从V1 到 V8 的最短路线。,由此看到，此方法不仅求出了从V1 到 V8 的最短路长，同时也求出了从V
10、1 到 任意一点 的最短路长。将从V1 到 任一点的最短路权标在图上，即可求出从V1 到 任一点的最短路线。本例中V1 到 V8 的最短路线是：v1 v2 v5 v6 v8,（二）、逐次逼近法算法的基本思路与步骤：首先设任一点vi到任一点vj都有一条弧。显然，从v1到vj的最短路是从v1出发，沿着这条路到某个点vi再沿弧(vi,vj)到vj。则v1到vi的这条路必然也是v1到vi的所有路中的最短路。设P1j表示从v1到vj的最短路长，P1i表示从v1到vi的最短路长，则有下列方程：开始时，令 即用v1到vj的直接距离做初始解。从第二步起，使用递推公式：求，当进行到第t步，若出现则停止计算，即为
11、v1到各点的最短路长。,例2、,求图中v1到各点的最短路,（0，0）,（v3，-5）,（v1，-2）,（v3，-7）,（v2，-3）,（v4，-5）,（v3，-1）,（v6，6）,例3、求：5年内，哪些年初购置新设备，使5年内的总费用最小。解：（1）分析：可行的购置方案（更新计划）是很多的，如：1）每年购置一台新的，则对应的费用为：11+11+12+12+13+5+5+5+5+5=84 2)第一年购置新的，一直用到第五年年底，则总费用为：11+5+6+8+11+18=59 显然不同的方案对应不同的费用。,（2）方法：将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。求解步骤：1）画
12、赋权有向图：设 Vi 表示第i年初，(Vi,Vj)表示第i 年初购买新设备用到第j年初（j-1年底），而Wi j 表示相应费用，则5年的一个更新计划相当于从V1 到V6的一条路。2）求解（标号法）,W12=11+5=16W13=11+5+6=22W14=11+5+6+8=30W15=11+5+6+8+11=41W16=11+5+6+8+11+18=59,W23=11+5=16 W24=11+5+6=22W25=11+5+6+8=30 W26=11+5+6+8+11=41,W45=12+5=17 W46=12+5+6=23W56=13+5=18,W34=12+5=17W35=12+5+6=23W
13、36=12+5+6+8=31,例4、某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备，每年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用，而且随着设备的老化会逐年增加。计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。,28,v1,v2,v3,v4,v5,v6,23,25,26,29,30,42,60,85,32,44,62,33,45,30,四、最大流问题,是一个增广链,显然图中增广链不止一条,容量为24,设，,则
14、截集为,容量为20,在此过程中，网络中的点或为标号点或为未标号点，每个标号点的标号包含两部分：第一个标号表明它的标号是从哪一点得到的，以便找出增广链，第二个标号是为确定增广链的调整量用的。,例：用标号法求下图所示的网络最大流,求下图所示网络中的最大流，弧旁数为,最小截集,13(11),9(9),4(0),5(5),6(6),5(5),5(4),5(4),4(4),4(3),9(9),10(7),截集1,截集2,最小截量为：9+6+5=20,（120）,（230）,（150）,（200）,寻找关于f 的最小费用增广链：构造一个关于f 的赋权有向图L(f)，其顶点是原网络G的顶点，而将G中的每一条
15、弧(vi,vj)变成两个相反方向的弧（vi，vj）和(vj,vi)，并且定义图中弧的权lij为：1.当，令 2.当（vj，vi）为原来网络G中（vi，vj）的反向弧，令 在网络G中寻找关于f 的最小费用增广链等价于在L(f)中寻求从vs 到vt 的最短路。,步骤：（1）取零流为初始可行流，f(0)=0。（2）一般地，如果在第k-1步得到最小费用流 f(k-1)，则构造图 L(f(k-1)。（3）在L(f(k-1)中，寻求从vs到vt的最短路。若不存在最短路，则f(k-1)就是最小费用最大流；否则转(4)。（4）如果存在最短路，则在可行流f(k1)的图中得到与此最短路相对应的增广链，在增广链上，
16、对f(k1)进行调整，调整量为：,令,得到新可行流f(k)。对f(k)重复上面步骤，返回（2）。,例8.11 求网络的最小费用最大流，弧旁权是（bij,cij）,第六节 中国邮递员问题,一、欧拉回路与道路定义8.18 连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。具有欧拉回路的图称为欧拉图。定理8.7 一个多重连通图G是欧拉图的充分必要条件是G中无奇点。推论 一个多重连通图G有欧拉道路的充分必要条件是G有且仅有两个奇点。,二、奇偶点图上作业法（1）找出图G中的所有的奇顶点，把它们两两配成对，而每对奇点之间必
17、有一条通路，把这条通路上的所有边作为重复边追加到图中去，这样得到的新连通图必无奇点。（2）如果边e=（u,v）上的重复边多于一条，则可从重复边中去掉偶数条，使得其重复边至多为一条，图中的顶点仍全部都是偶顶点。（3）检查图中的每一个圈，如果每一个圈的重复边的总长不大于该圈总长的一半，则已经求得最优方案。如果存在一个圈，重复边的总长大于该圈总长的一半时，则将这个圈中的重复边去掉，再将该圈中原来没有重复边的各边加上重复边，其它各圈的边不变，返回步骤（2）。,判定标准1:在最优邮递路线上，图中的每一条边至多有一条重复边。判定标准2:在最优邮递路线上，图中每一个圈的重复边总权小于或等于该圈总权的一半。,例8.12 求解下图所示网络的中国邮路问题，图中数字为该边的长。,l12+2 l23+2 l36+2 l89+2 l78+l69+l14+2 l47=51,
