运筹学八章图与网络分析

1、第八章 图与网络分析,8.1图与网络的基本知识 8.2 树 8.3最短路径问题 8.4网络最大流问题 8.5最小费用最大流问题,图论的产生：1736年的“哥尼斯堡七桥问题”十八世纪的东普鲁士哥尼斯堡城,哥尼斯堡七桥问题的网络分析,8.1 图与网络的基本知识 一、图与网络的基本概念,1、图及其分类 由一些点及一些点的连线所组成的图形。若V=V1,V2, Vn是空间n个点的集合; E= e1,e2, em是空间m个边的集合,满足: 1)V非空 2)E中每一条线ei是以V中两个点Vs,Vt为端点 3)E中任意两条线之间除端点之外无公共点. 则由V、E构成的二元组合G=(V， E)就是图。 子图：已知

2、图G1（V1，E1）若V1 V， E1 E ; 则称图G1（V1，E1）是图G=(V， E)的子图 若在图G中，某个边的两个端点相同，则称e是环。 多重边：图中某两点之间有多余一条的边，称之为多重边。 多重图：含有多重边的图。 简单图：无环、无多重边的图。,分类：,无向图：G（V，E）点集+边集 弧：点与点之间有方向的边，叫做弧。弧集：A=a1,a1,am 有向图：由点及弧所构成的图，记为D=(V,A)，V,A分别是D的点集合和弧集合。 环：某一条孤起点=终点，称为环。 基础图：给定一个有向图D=(V,A) ，从D中去掉所有弧上的箭头，所得到的无向图。记之为G(D)。 链：设(vi1,ai1,

3、vi2,ai2,vik-1,aik-1,vik)是D中的一个点弧交错序列，如果这个序列在基础图G(D)中所对应的点边序列是一条链，则称这个点弧交错序列是D的一条链。 路：如果(vi1,ai1,vi2,ai2,vik-1,aik-1,vik)是D中的一条链，并且对t=1,2,k-1，均有ait=(vit,vit+1)，称之为从vi1到vik的一条路。 回路：若路的第一个点和最后一点相同，则称之为回路。,2、顶点的次,次：图中的点V，以V为端点的边的个数，称为V的次，记为d(V)。 定理1：图G=(V,E)中，所有点的次之和是边数的两倍，即设边数为q ，则d(vi)=2q ，其中viV 奇点：次为

4、奇数的点。否则称为偶点。 任一图中，奇点的个数为偶数。 一笔划： 可以一笔划：没有或仅有两个奇次点的图形 如没有奇次点：任取一点，它既是起点又是终点。 两个奇次点：分别选为起点和终点。,二、连通图,1、链：给定一个图G=(V,E)，一个点边的交错序列(vi1, ei1, vi2, ei2,vik-1,eik-1,vik)，如果满足eit=vit,vit+1 (t=1,2,k-1)，则称为一条联结vi1和vik的链，称点vi2, vi3,vik-1为链的中间点。 2、圈：链(vi1,vi2,vik)中，若vi1=vik,，则称之为一个圈。 3、简单链：若链(vi1,vi2,vik)中，点vi1,

5、vi2,vik都是不同的，则称之为简单链。 4、连通图：图G中，若任何两个点之间，至少有一条链。否则为不连通图。,三、图的矩阵表示,1、赋权图：给图G=(V,E) ，对G中的每一条边vi,vj，相应地有一个数wij，则称这样的图G为赋权图，wij称为边vi,vj上的权。 2、网络（赋权图）G=（V，E），其边（vi,vj）有权wij, 构造矩阵A=（aij）nn,其中： aij= wij（vi,vj）E 0 其他 称矩阵A为网络G的权矩阵。如P239，例2 3、对于图G=（V，E）， V =n,构造一个矩阵A=（aij）nn,其中： aij= 1（vi,vj）E 0 其他 称矩阵A为图G的邻接

6、矩阵。如P239，例3,四、欧拉回路与中国邮路问题,1、欧拉回路与道路：连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路，具有欧拉回路的图也称欧拉图。 仅当无向连通图G中无奇点时是欧拉图，仅当恰有两个奇点时为欧拉道路； 仅当有向连通图G中每个顶点的出次等于入次时是欧拉图，仅当两个顶点外，其余每一个顶点的出次等于入次，且这两个顶点中，一个顶点出次多1，另一个顶点入次多1时为欧拉道路； 2、中国邮路问题：给定一个连通图G，每边有非负权l(e)，要求一条回路过每边至少一次，且满足总权最小。,8.2 树（是最简单又十分

7、重要的图）例如：比赛中的相遇情况、组织结构图、家庭树,1、定义：一个无圈的连通图称为树。,2、树的性质： 1）图G是树的充分必要条件是任意两个顶点之间有且只有一条链。 2）在树中去掉任意一条边则构成一个不连通图，不再是树；在树中不相邻的两点之间添加一条边，恰好形成了一个圈，也就不再是树。 3）树中顶点的个数为P，则其边数必为P-1。,3、生成树：设图T=(V,E) 是图G（V，E）的子图，如果图T=(V, E) 是一个树，则称T是G的一个支撑树。 4、寻找生成树的方法 1）破圈法：在图中任取一个圈，从圈中去掉任一边，对余下的图重复上述操作，即可得到一个支撑树。 2）避圈法：每一步选取与已选的边

8、构不成圈的边，直到不能继续为止。（深探法广探法阅读内容）,5、最小生成树 1）最小支撑树：如果T=(V,E) 是G的一个支撑树，称E中所有边的权之和为支撑树T的权，记为w(T)，即 w(T)=wij (vi,vj)T 如果支撑树T*的权w(T*)是G的所有支撑树的权中最小者，则称T*是G的最小生成树（最小支撑树，简称最小树） w(T*)=min w(T),2）求最小树的方法： 方法一(避圈法) 开始选一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈。 方法二(破圈法) 任取一个圈，从圈中去掉一条权最大的边。在余下的图中，重复这个步骤，一直到一个不含圈

9、的图为止，这时的图便是最小树。,例 用破圈法求下图的最小树,6、根树及其应用 定义17：若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树。 定义18：有向树T，恰有一个结点入次为0，其余各点入次均为1，称树T为根树（又称外向树）。 定义19：在根树中，若每个顶点的出次小于或等于m，称这颗树为m叉树，若每个顶点的出次恰好等于m或0，则称这颗树为完全m叉树。当m=2时，称为二叉树、完全二叉树。满足总权最小的二叉树称为最优二叉树（又称霍夫曼树）。 最优二叉树求解步骤： （1）将s个叶子按权由小到大排序，不失一般性，设p1p2ps （2）将两个具有最小权的叶子合并成一个分枝点，其权为p1

10、+p2，将新的分枝点作为一个叶子，令s=s-1，若s=1停止，否则转（1）,习题：,P8.7 P8.8 P8.9,8.3 最短路问题,引例： 如下图中V1：油田，V9：原油加工厂 求使从V1到V9总铺路设管道最短方案。,V1,V4,V2,V3,V6,V9,V8,V7,V5,4,2,4,6,6,2,3,4,4,4,2,用图论来解释最短路问题：在一个赋权有向图D（V，A，w）中，其中始点V1，终点Vt，求从V1到Vt的一条路，使其为V1到Vt的所有路中总权值最小的路。,一、最短路算法,1、情况一： wij0(Dijkstra算法) 原理：Bellman最优性定理 方法：图上作业法（标号法）；双标号

11、法（表的形式） 标号：对于点V,若已求出V1到Vi的最短值，标号（i,i) i ：表示V1到Vi的最短路值 i:表示最短路中最后经过的点 标号法步骤： 1）给V1标号(0, Vs) 2）把所有顶点分成两部分，X：已标号的点；X未标号的点 考虑与已标号点相邻的弧是存在这样的弧（ Vi ，Vj ）, Vi X, Vj X若不存在，此问题无解，否则转3） 3）选取未标号中所有入线的起点与未标号的点Vj进行计算:mini + wij= j 并对其进行标号(j, Vi)，重复2）,例9：（图831）,*,4,6,4,v1,*,6,9,8,6,v1,*,9,8,8,v2,*,9,13,14,9,v2,*,

12、13,14,13,v5,*,14,17,14,v5,*,15,15,v7,最短路长为15，路径可以逆向追踪，v8-v7-v5-v2-v1,例,0,8,15,10,12,15,11,31,13,Dijkstra最短路算法的特点和适应范围,一种隐阶段的动态规划方法 每次迭代只有一个节点获得永久标记，若有两个或两个以上节点的临时标记同时最小，可任选一个永久标记；总是从一个新的永久标记开始新一轮的临时标记，是一种深探法 被框住的永久标记 Tj 表示 vs 到 vj 的最短路，因此 要求 dij0，第 k 次迭代得到的永久标记，其最短路中最多有 k 条边，因此最多有n1 次迭代 可以应用于简单有向图和混

13、合图，在临时标记时，所谓相邻必须是箭头指向的节点；若第 n1 次迭代后仍有节点的标记为 ，则表明 vs 到该节点无有向路径 如果只求 vs 到 vt 的最短路，则当 vt 得到永久标记算法就结束了；但算法复杂度是一样的 应用 Dijkstra 算法 n1 次 ，可以求所有点间的最短路 vs 到所有点的最短路也是一棵生成树，但不是最小生成树,2、情况二： wij0（逐次逼近法） 设从V1到Vj(j=1,2,t)的最短路长为P1j V1到Vj无任何中间点 P1j（1）= wij V1到Vj中间最多经过一个点 P1j（2）= min P1i（1）+wij V1到Vj中间最多经过两个点 P1j（3）=

14、 min P1i（2）+wij . V1到Vj中间最多经过t-2个点 P1j（t-1）= min P1i（t-2）+wij 终止原则： 1）当P1j（k）= P1j（k+1）可停止，最短路P1j*= P1j（k） 2）当P1j（t-1）P1j（t-2）时，再多迭代一次P1j（t） ，若P1j（t） = P1j（t-1） ，则原问题无解，存在负回路。,0,2,5,-3,0,-2,4,0,6,4,0,0,-3,0,4,7,2,0,3,-1,0,0,2,5,-3,0,2,0,-3,6,11,0,2,0,-3,6,6,15,0,2,0,-3,3,6,14,10,0,2,0,-3,3,6,9,10,0,

15、2,0,-3,3,6,9,10,例：,例 设备更新问题,制订一设备更新问题，使得总费用最小,第1年 第2年 第3年 第4年 第5年 购买费 13 14 16 19 24 使用年数 0-1 1-2 2-3 3-4 4-5 维修费 8 10 13 18 27,解设以vi(i=1,2,3,4,5)表示“第i年初购进一台新设备”这种状态，以v6表示“第5年末”这种状态；以弧(vi, vj)表示“第i年初购置的一台设备一直使用到第j年初”这一方案，以wij表示这一方案所需购置费和维护费之和。,v1,v2,v3,v5,v6,v4,21,44,32,22,89,62,31,63,45,24,47,34,27

16、,37,32,(0，Vs),(21，V1),(31, V1),(44,V1),(62,V1),(78,V3),这样，可建立本例的网络模型。于是，该问题就可归结为从图中找出一条从v1到v6的最短路问题。,用Dijkstra标号法，求得最短路为 v1v3v6,即第一年初购置的设备使用到第三年初予以更新，然后一直使用到第五年末。这样五年的总费用最少，为78。,习题,P8.10 P8.11,8.4 最大流问题,如下是一运输网络，弧上的数字表示每条弧上的容量，问：该网络的最大流量是多少？,一、基本概念和基本定理,1、网络与流 定义1：给定一个有向图D=(V,A),在V中有一个发点vs和一收点vt，其余的

17、点为中间点。对于每一条弧(vi,vj),对应有一个c(vi,vj)0,(cij)称为弧的容量。这样的有向图称为网络。记为D=(V,A,C)。 网络的流：定义在弧集合A上的一个函数f=f(vi,vj)，称f(vi,vj)为弧(vi,vj)上的流量，简记fij 。,2、可行流与最大流 定义2 满足下列条件的流称为可行流： 0 fijcij 2)平衡条件：中间点 fij = fji (vi,vj)A (vj,vi)A 发点vs: fsj fjs=v(f) (vs,vj)A (vj,vs)A 收点vt: ftj fjt= v(f) (vt,vj)A (vj,vt)A,式中v(f)称为这个可行流的流量，

18、即发点的净输出量（或收点的净输入量）。,最大流问题：求一流fij满足 1）0 fijcij v(f) i=s 2）fijfji= 0 is，t v(f) i=t 3）且使v(f)达到最大。,3、增广链,给定可行流f=fij，使fij=cij的弧称为饱和弧，使fij0的弧称为非零流弧。,若是网络中连接发点vs和收点vt的一条链，定义链的方向是从vs到vt，则链上的弧被分成两类：,前向弧：弧的方向与链的方向一致 全体+,后向弧：弧的方向与链的方向相反 全体-,定义：设f是一可行流，是从vs到vt的一条链，若满足下列条件，则称之为（关于流f的）一条增广链： 在弧(vi,vj)+上，0fijcij 在

19、弧(vi,vj)-上，0fijcij,可结合下图理解其实际涵义。,4、割集与割集容量 定义4 给定网络D=(V,A,C)，若点集V被剖分为两个非空集合V1和V1，使vsV1， vtV1，则把弧集(V1,V1)称为是分离vs和vt的割集。 割集是从vs到vt的必经之路。 定义：给定一割集(V1,V1)，把割集(V1,V1)中所有弧的容量之和称为这个割集的容量(割量),记为C(V1,V1)。,v(f) C(V1,V1),若对于一可行流f*，网络中有一割集(V1*,V1*)，使得v(f*)= C(V1*,V1*)，则f必是最大流，而(V1*,V1*)，必定是容量最小的割集，即最小割集。,定理1 可行

20、流f*是最大流的充要条件是不存在关于f*的增广链。,若f*是最大流，则网络中必存在一个割集(V1*,V1*)，使得 v(f*)= C(V1*,V1*),定理 任一网络D中，从vs到vt的最大流的流量等于分离vs，vt的最小割集的割量。,X,X,X,X,2,3,4,1,1,2,2,4,3,割集为(1,3)(2,3)(2,4)割集的容量9,2,3,4,1,1,2,2,4,3,割集为(1,2)(1,3)割集的容量5,X,X,X,X,2,3,4,1,1,2,2,4,3,割集为(1,2)(3,4)割集的容量3,2,3,4,1,1,2,2,4,3,割集为(2,4)(3,4)割集的容量5,网络最大流的流量等

21、于网络最小割集的容量,步骤： 1、选取一个可行流（可选择零流弧） 2、 标号过程 从Vs出发，在前向弧(vi,vj)上，若fij0，则给vj标号( Vi,l(vj)，其中l(vj)=minl(vi)，fji。,二、寻找最大流的标号法(Ford Fulkerson),思想：从一可行流出发，检查关于此流是否存在增广链。若存在增广链，则增大流量，使此链变为非增广链；这时再检查是非还有增广链，若还有，继续调整，直至不存在增广链为止。,3、若标号延续到vt，表明得到一条从vs到vt的增广链，转入调整阶段4，否则当前流即为最大流。,4、调整过程,令调整量为= l(vt),令 fij+ (vi,vj)+ f

22、ij= fij (vi,vj) fij (vi,vj),去掉所有的标号，对新的可行流f=fij，重新进入标号过程。,例 求下列网络的最大流与最小截集。,解一、标号过程,（2）检查vs,在弧(vs,v1)上,fs1=7,cs1=9,fs1cs1,则v1的标号为(vs,l(v1)，其中,(vs,2),l(v1)=minl(vs)，cs1fs1=min+，9 7=2,(Vs,),（1）线vs标号：(VS, ),（3）检查v1,在弧(v1,v4)上,f14=1,c14=3,f14c14,则v4的标号为(v1,l(v4)，其中,l(v4)=minl(v1)，c14f14=min2，3-1=2,(v1,2

23、),（4）检查v4,在弧(v3,v4)上,f14=10，,则v3的标号为(-v4, l(v3)，其中,l(v3)=minl(v4)，f34=min2，1=1,(-v4,1),（5）检查v3,在弧(v3,vt)上,f3t=3,c3t=6,f3tc3t,则vt的标号为(v3,l(vt)，其中,l(vt)=minl(v3)，c3tf3t=min1，6-3=1,(v3,1),这样，我们得到了一增广链,如图所示。,其中+=(vs,v1),(v1,v4),(v3,vt)， -=(v3,v4),(v3,1),二、调整过程,取调整量为=1，在上调整f。,在+上： fs1+=7+1=8 f14+=1+1=2 f

24、3t+=3+1=4,在-上： f34=11=0,其余弧上的流量不变，这样得到一个新的流，如下图所示。,t,v,4,v,2,(,5,5),(Vs,),在上图中重复上述标号过程，依次给vs,v2,v1,v4标号，,v,v(f)=8+3=11,与此同时，可找到最小截集(V1,V1)，其中V1为标号点集合，V1为未标号点集合，弧集合(V1,V1) 即为最小截集。,此例中， V1=vs,v2,v1,v4, V1=v3,vt,(V1,V1)=(v1,v3)， (v4,vt),由于标号无法继续下去，算法结束。这时的流为最大流，最大流的流量为,(vs,1),(v1,1),(vs,2),最大流最小割集的标号法举

25、例,(s+,),(s+,6),(2,6),(3+,1),(4+,1),(s+,),(s+,5),(2+,2),(5,2),(4+,2),最大流最小割集的标号法举例,(s+,),(s+,3),(2,3),最小截集,最大匹配问题,考虑工作分配问题，有n个工人，m件工作，每个工人能力不同，各能胜任其中的几项工作，假设每件工作只需一人做，每人只做一件工作，怎样分配才能使尽量多的工作有人做，更多的人有工作做？ 用图的语言来描述：x1,x2,xn表示工人， y1,y2,ym表示工作，边(xi, yj)表示xi胜任 yj工作，这样就得到了二部图G=（X，Y，E），工作分配问题就要在图G中找一个边集E的子集，使得其中任何两条边没有公共端点，最好的方案就是要使此边集的边数尽可能多，这就是最大匹配问题。,举例,某单位招收懂俄、英、日、德、法文的翻译各一人，有5人应聘。已知乙懂俄文，甲、乙、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这5个人是否都能得到聘书？最多几个得到招聘，招聘后每人从事哪一方面翻译任务？ 将五个人与五个外语语种分别用点表示，把各个人与懂得的外语语种之间用弧相连。规定每条弧的容量为1，图网络的最大流量数字即为最多能得到招聘的人数。,vs,甲,乙,丙,丁,戊,俄,英,日,德,法,vt,1,1,1,1,1,1,