运筹学第6章图与网络分析.ppt

《运筹学第6章图与网络分析.ppt》由会员分享，可在线阅读，更多相关《运筹学第6章图与网络分析.ppt（139页珍藏版）》请在三一办公上搜索。

1、图与网络分析(Graph Theory and Network Analysis),图与网络的基本知识,最短路问题,树及最小树问题,最大流问题,最小费用最大流问题,哥尼斯堡七桥问题,哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？,哥尼斯堡七空桥,一笔画问题,哈密尔顿（Hamilton）回路是十九世纪英国数学家哈密顿提出，给出一个正12面体图形，共有20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次

2、而且仅一次，最后回到原处的周游世界线路（并不要求经过每条边）。,有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同的就座方案共有多少种？用顶点表示人，用边表示两者相邻，因为最初任何两个人都允许相邻，所以任何两点都可以有边相连。,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,得到第一次就座方案是（1，2，3，4，5，6，7，1），继续寻求第二次就座方案时就不允许这些顶点之间继续相邻，因此需要从图中删去这些边

3、。,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,得出第二次就座方案是（1，3，5，7，2，4，6，1），那么第三次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,得到第三次就座方案是

4、（1，4，7，3，6，2，5，1），那么第四次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边，只留下7点孤立点，所以该问题只有三个就座方案。,1,2,3,7,6,4,5,引论 图的用处,某公司的 组织机构设置图,总公司,分公司,工厂或办事处,一、图与网络的基本知识（一）、图与网络的基本概念,1、一个图是由点和连线组成。（连线可带箭头，也可不带，前者叫弧，后者叫边）,一个图是由点集 和 中元素的无序对的一个集合 构成的二元组，记为G=(V，E)，其中 V 中的元素 叫做顶点，V 表示图 G 的点集合；E 中的元素 叫做边，E 表示图 G 的边集合。,例,图1,2、如果一个图是由点和边

5、所构成的，则称其为无向图，记作G=(V，E)，连接点的边记作vi,vj，或者vj,vi。,3、如果一个图是由点和弧所构成的，那么称它为有向图，记作D=(V,A)，其中V 表示有向图D 的点集合，A 表示有向图D 的弧集合。一条方向从vi指向vj 的弧，记作(vi,vj)。,图2,4、一条边的两个端点是相同的,那么称为这条边是环。5、如果两个端点之间有两条以上的边，那么称为它们为多重边。,6、一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。,7、每一对顶点间都有边相连的无向简单图称为完全图。有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。,度为零的点称为弧立点，度

6、为1的点称为悬挂点。悬挂点的关联边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。,8、以点v为端点的边的个数称为点v 的度（次），记作。,图中 d(v1)=4，d(v6)=4（环计两度）,定理1 所有顶点度数之和等于所有边数的2倍。定理2 在任一图中，奇点的个数必为偶数。,所有顶点的入次之和等于所有顶点的出次之和。,有向图中，以 vi 为始点的边数称为点vi的出次，用 表示；以 vi 为终点的边数称为点vi 的入次，用 表示；vi 点的出次和入次之和就是该点的次。,9、设 G1=（V1,E1），G2=（V2,E2）如果 V2 V1,E2 E1 称 G2 是G1 的子图；如果 V2=V

7、1,E2 E1 称 G2 是 G1 的部分图或支撑子图。,在实际应用中，给定一个图G=（V，E）或有向图D=（V，A），在V中指定两个点，一个称为始点（或发点），记作v1，一个称为终点（或收点），记作vn，其余的点称为中间点。对每一条弧，对应一个数，称为弧上的“权”。通常把这种赋权的图称为网络。,10、由两两相邻的点及其相关联的边构成的点边序列称为链。如:v0，e1，v1，e2，v2，e3，v3,vn-1,en，vn，记作（v0，v1，v2，v3,vn-1，vn），,11、图中任意两点之间均至少有一条通路，则称此图为连通图，否则称为不连通图。,其链长为 n，其中 v0，vn 分别称为链的起点和

8、终点。若链中所含的边均不相同，则称此链为简单链；所含的点均不相同的链称为初等链,也称通路。,（二）、图的矩阵表示对于网络（赋权图）G=（V，E），其中边有权，构造矩阵，其中：称矩阵A为网络G的权矩阵。,设图G=（V，E）中顶点的个数为n，构造一个矩阵，其中：称矩阵A为网络G的邻接矩阵。,例,权矩阵为：,邻接矩阵为：,二、树及最小树问题 已知有六个城市，它们之间 要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。,1、一个连通的无圈的无向图叫做树。树中次为1的点称为树叶，次大于1的点称为分支点。,树的性质：（1）树必连通，但无回路（圈）。（2）n 个顶点的树必有n-1 条边。

9、（3）树 中任意两个顶点之间，恰有且仅有一条链（初等链）。（4）树 连通，但去掉任一条边，必变为不连通。（5）树 无回路（圈），但不相邻的两个点之间加一条边，恰得到一个回路（圈）。,一个图G 有生成树的充要条件是G 是连通图。,2、设图 是图G=(V,E)的一支撑子图，如果图 是一个树,那么称K 是G 的一个生成树（支撑树），或简称为图G 的树。图G中属于生成树的边称为树枝，不在生成树中的边称为弦。,（一）破圈法：在图中任选一个圈，从这个圈中去掉一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。,用破圈法求出下图的一个生成树。,（二）避圈法：开始选一条边，以后每一步中，总从未被选取的

10、边中选出一条与已选边不构成圈的边，重复这个过程，直到不能进行为止。,根据破圈法和避圈法两种方式得到了图的两个不同的生成树，由此可以看到连通图的生成树不是唯一的。,3、最小生成树问题,一棵生成树所有树枝上权的总和为这个生成树的权。具有最小权的生成树，称为最小生成树。求赋权图G的最小支撑树的方法也有两种，“破圈法”和“避圈法”。,破圈法：在原图中，任选一个圈，从圈中去掉权最大的一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。,6,5,5,1,7,2,3,4,4,v1,v2,v3,v4,v5,v6,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,

11、1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,v1,v

12、7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,17,4,1,23,总造价=1+4+9+3+17+23=57,v1,v2,v3,v4,v5,1,4,2,3,1,3,5,2,避圈法：开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选边不构成圈的边。,某六个城市之间的道路网如图 所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长

13、度最短。,最短路的一般提法为：设 为连通图，图中各边 有权（表示 之间没有边），为图中任意两点，求一条路，使它为从 到 的所有路中总权最短。即：最小。,(一)、狄克斯屈拉(Dijkstra)算法适用于wij0，给出了从vs到任意一个点vj的最短路。,三、最短路问题,算法步骤：1.给始点vs以P标号，这表示从vs到 vs的最短距离为0，其余节点均给T标号，。2.设节点 vi 为刚得到P标号的点，考虑点vj，其中，且vj为T标号。对vj的T标号进行如下修改：3.比较所有具有T标号的节点，把最小者改为P标号，即：当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替v

14、i，返回步骤（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,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=

15、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+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

16、,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+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

17、,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,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

18、=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 的最短路长，同时也求出了从V1 到 任意一点 的最短路长。将从V1 到 任一点的最短路权标在图上，即可求出从V1 到 任一点的最短路线。本例中V1 到 V8 的最短路线是：v1 v2

19、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步，若出现则停止计算，即为v1到各点的最短路长。,例二、,求图中v1到各点的最短路,（0，0）,（v3，-5）,（v1，-2）,（v3，-7）,（v2，-3）,（v4，-5）,（v3

20、，-1）,（v6，6）,例三、求：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）画赋权有向图：设 Vi 表示第i年初，(Vi,Vj)表示第i 年初购买新设备用到第j年初（j-1年底），而Wi j 表示相应费用，则5年的一个更新计划相当于从

21、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=23W36=12+5+6+8=31,例四、某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备，每

22、年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用，而且随着设备的老化会逐年增加。计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。,28,v1,v2,v3,v4,v5,v6,23,25,26,29,30,42,60,85,32,44,62,33,45,30,四、最大流问题（一）、基本概念1、设一个赋权有向图D=（V,E）,在V中指定一个发点vs和一个收点vt,其它的点叫做中间点。对于D中的每一个弧（vi,vj）E,都有一个非负数cij,叫做弧的容量。我们把这样的图D叫做一个容量网络，

23、简称网络，记做D=（V，E，C）。网络D上的流，是指定义在弧集合E上的一个函数其中f(vi,vj)=fij 叫做弧(vi，vj)上的流量。,2、称满足下列条件的流为可行流：（1）容量条件：对于每一个弧（vi,vj）E有 0 fij cij。（2）平衡条件：对于发点vs，有对于收点vt，有对于中间点，有,可行流中 fijcij 的弧叫做饱和弧，fijcij的弧叫做非饱和弧。fij0 的弧为非零流弧，fij0 的弧叫做零流弧。,图中 为零流弧，其余为非饱和弧。,3、容量网络G，若 为网络中从vs到vt的一条链，给 定向为从vs到vt，上的弧凡与 方向相同的称为前向弧，凡与 方向相反的称为后向弧，其

24、集合分别用 和 表示。f 是一个可行流，如果满足：则称 为从vs到vt 的关于f 的一条增广链。,推论 可行流f 是最大流的充分必要条件是不存在从vs到vt 的关于f 的一条可增广链。,即 中的每一条弧都是非饱和弧,即 中的每一条弧都是非零流弧,是一个增广链,显然图中增广链不止一条,4、容量网络G=（V，E，C），vs为始点，vt为终点。如果把V分成两个非空集合 使，则所有始点属于S，而终点属于 的弧的集合，称为由S决定的截集,记作。截集 中所有弧的容量之和，称为这个截集的容量，记为。,容量为24,设，,则截集为,容量为20,（二）、求最大流的标号法 标号过程：1 给发点vs 标号（0，+）。

25、2 取一个已标号的点vi，对于vi一切未标号的邻接点vj 按下列规则处理：（1）如果边，且，那么给vj 标号，其中：（2）如果边，且，那么给vj 标号，其中：3重复步骤2，直到vt被标号或标号过程无法进行下去，则标号结束。若vt被标号，则存在一条增广链，转调整过程；若vt未被标号，而标号过程无法进行下去，这时的可行流就是最大流。,调整过程设1令 2去掉所有标号，回到第一步，对可行流重新标号。,求下图所示网络中的最大流，弧旁数为,最小截集,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+

26、6+5=20,（120）,（230）,（150）,（200）,第五节 最小费用最大流问题,定义 已知网络G=（V，E，C，d），f是G上的一个可行流，为一条从vs到vt的增广链，称为链的费用。,若*是从vs到vt的增广链中费用最小的增广链，则称*是最小费用增广链。结论：如果可行流 f在流量为W(f)的所有可行流中的费用最小，并且*是关于f 的所有增广链中的费用最小的增广链，那么沿增广链*调整可行流f，得到的新可行流f*也是流量为W(f*)的所有可行流中的最小费用流。当f*是最大流时，就是最小费用最大流。,寻找关于f 的最小费用增广链：构造一个关于f 的赋权有向图L(f)，其顶点是原网络G的顶点

27、，而将G中的每一条弧(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)的图中得到与此最短路相对应的增

28、广链，在增广链上，对f(k1)进行调整，调整量为：,令,得到新可行流f(k)。对f(k)重复上面步骤，返回（2）。,例8.11 求网络的最小费用最大流，弧旁权是（bij,cij）,第六节 中国邮递员问题,一、欧拉回路与道路定义 连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。具有欧拉回路的图称为欧拉图。定理 一个多重连通图G是欧拉图的充分必要条件是G中无奇点。推论 一个多重连通图G有欧拉道路的充分必要条件是G有且仅有两个奇点。,二、奇偶点图上作业法（1）找出图G中的所有的奇顶点，把它们两两配成对，而每对奇点之

29、间必有一条通路，把这条通路上的所有边作为重复边追加到图中去，这样得到的新连通图必无奇点。（2）如果边e=（u,v）上的重复边多于一条，则可从重复边中去掉偶数条，使得其重复边至多为一条，图中的顶点仍全部都是偶顶点。（3）检查图中的每一个圈，如果每一个圈的重复边的总长不大于该圈总长的一半，则已经求得最优方案。如果存在一个圈，重复边的总长大于该圈总长的一半时，则将这个圈中的重复边去掉，再将该圈中原来没有重复边的各边加上重复边，其它各圈的边不变，返回步骤（2）。,判定标准1:在最优邮递路线上，图中的每一条边至多有一条重复边。判定标准2:在最优邮递路线上，图中每一个圈的重复边总权小于或等于该圈总权的一半。,例 求解下图所示网络的中国邮路问题，图中数字为该边的长。,l12+2 l23+2 l36+2 l89+2 l78+l69+l14+2 l47=51,