运筹学与系统分析：第5章 图与网络分析

1、第五章 图与网络分析主要内容：5.1 图与网络的基本知识5.2 树5.3 最短路问题5.4 最大流问题思考：哥尼斯堡七桥问题 哥尼斯堡（现名加里宁格勒）是欧洲一个城市，有一条河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次，最后回到原地呢？ABCD 此难题于1736年被瑞士数学家欧拉解决，他在“依据几何位置的解题方法”论文中证明这样的走法不存在。欧拉被公认为图论的创始人。ABCDBACD 1857年，英国数学家Hamilton发明一种游戏，用一个实心正12面体象征地球，其20个顶点分别表示世界

2、的20个城市，要求游戏者从某一城市出发寻找一条经由每个城市一次且仅经一次再回到原出发点的路。此问题有解。Euler回路：在图中找一条经过每边一次且仅一次的路且回到原点。Hamilton回路：在图中找一条经过每个点一次其仅一次的路且回到原点。图论第一本专著：有限图与无限图的理论，1936，匈牙利数学家。图论迅速发展时期：20世纪中期，电子计算机的发展以及离散数学的发展，促使图论在管理科学、信息论、控制论等各领域广泛应用。5.1 图与网络基本知识一、图与网络的基本概念企业A企业B企业C企业D企业E工人工作甲乙丙丁戊ABCD图：反映对象之间关系的一种工具。定义1：一个图是由点集V=vi和边集E=ek

3、（所有边的端点都属于V）所构成的二元组，记为G=(V,E)。vi为顶点，ek为边，当V、E为有限集时G为有限图。e1v4e3v1v2e4e5v5v3e6e2例：右图中V=v1,v2,v3,v4,v5E=e1,e2,e3,e4,e5,e6e1=(v1,v1),e2=(v1,v2),无向图：任意边都是无向边的图有向图：任意边都是有向边的图环：边的两端点相同也称环，如e1;多重边：两点间多于一条边，如e4,e5定义2：不含环和多重边的图是简单图，含有多重边的图称为多重图。下图哪些是简单图，哪些是多重图？有向图中两点之间有不同方向的两条边，不是多重边。(a)(b)(c)(d)a,b为简单图，c,d为多

4、重图。定义3: 每一对顶点间都有边相连的无向简单图称为完全图。每一对顶点间有且仅有一条有向边的简单图称为有向完全图。定义4：图G的点集V可以分成两个非空子集X,Y,使得E中每条边的两个端点必有一个属于X，另一个属于Y，则G称为二部图。以下哪些是二部图？(a)(b)a,b图都是二部图。定义5：以点v为端点的边数叫做点v的次。记为deg(v),简记d(v)。 次为奇数的点称为奇点，次为偶数的点称为偶点。次为0的点称为孤立点。e1v4e3v1v2e4e5v5v3e6e2右图中d(v1)=4 (e1计算两次)d(v3)=4定理1：任何图中，顶点次数的总和等于边数的2倍。定理2：任何图中，次为奇数的顶点

5、必为偶数个。定义6：有向图中以vi为始点的边数称为vi的出次，记为d+(vi) ，以vi为终点的边数称为vi的入次，记为d-(vi) 。定义7：图G=(V,E)，若E是E的子集，V是V的子集，且E中的边仅与V中的顶点相关联，则称G=(V,E)是G的一个子图。若V=V, 则G称为G的生成子图。例，下图(b)为(a)的子图，(c)为(a)的生成子图。v1v2v3v4v5(a)v1v2v3v5(b)v1v2v3v4v5(c)权：点或边相关的某些数量指标，可代表距离、费用、容量等。网络：点或边带有某种数量指标的图。(a),(b)是常见网络例子，(a)网络图常见于最短路问题，(b)网络图常见于管道运输网

6、络。v3v1v4v5v2(a)v3v1v4v5v2(b)54362525436225二、连通图定义8：无向图G中能够连接两点的点、边序列构成一条链。没有重复点或重复边的链为初等链。v3v1v4v5v2e1e2e3e4e5e6e7S1=v1,e1,v3,e7,v5,e6,v3,e7,v5,e4,v4为连接v1,v4的一条链；S2=v1,e1,v3,e7,v5,e4,v4为初等链定义9：无向图G中一条链的始点和终点是同一点时，称为圈。没有重复点或重复边的圈为初等圈。S1=v1,e1,v3,e7,v5,e6,v3,e7,v5,e4,v4,e2,v1为一个圈；S2=v1,e1,v3,e7,v5,e4,

7、v4,e2,v1为一个初等圈。有向图中边的方向相同时，链和圈分别称为道路和回路。定义10：一个图中任意两点间至少有一条链，称为连通图。任何非连通图都可以分为若干个连通子图(分图)。三、图的矩阵表示v1v2v3v4v5745629483定义11：网络(赋权图)G=(V,E)上的边(vi,vj)有权wij，构造矩阵A=(aij)nn，其中称矩阵A为网络G的权矩阵。右图的权矩阵为：三、图的矩阵表示v1v2v3v4v5定义12：图G=(V,E)的顶点的数量为n，构造矩阵A=(aij)nn，其中称矩阵A为图G的邻接矩阵。当G为无向图时，邻接矩阵为对称矩阵。右图的邻接阵为：四、欧拉回路与中国邮路问题定义1

8、3：连通图中，若存在一条回路，经过每边一次且仅一次，则称之为欧拉回路。具有欧拉回路的图称为欧拉图（E图）。定理3：无向连通图G是欧拉图，当且仅当G中无奇点。定理4：有向连通图G是欧拉图，当且仅当G的每个顶点的出次等于入次。中国邮路问题：邮递员从邮局出发，走遍该地区所有街道再返回邮局，如何安排路线可以使所走总路程最短？中国邮路问题可以转化为如下问题：在连通图G=(V,E)中，求一个边集E1 E，把G属于E1的边均变为二重边得到G*=G+E1，使其满足G*无奇点，且L(E1)最小。 定理5：已知图G*=G+E1无奇点，则L(E1)最小的充要条件是：（1）每条边最多重复一次；（2）对图G中每个初等圈

9、来讲，重复边的长度之和不超过圈长的一半。例：利用定理5求解下面网络的中国邮路问题解：(1)检查是否有奇点?共有四个奇点：v2,v4,v6,v8v1v2v3v4v5v6v9v8v7256354434944(a)v1v2v3v4v5v6v9v8v7256354434944(b)59(2)将v2与v4,v6与v8配对，分别经v1和v9作出重复边，使整个网络图没有奇点，且满足定理5中的条件(1) ;初等圈都满足条件(2)？圈v1v2v5v4v1不满足条件(2)；(3)做调整，画出c图，满足条件(2)吗？v1v2v3v4v5v6v9v8v7256354434944(c)圈v2v3v6v9v8v5v2不满

10、足条件(2)。(4)做调整，将v2与v6，v4与v8重新配对，画出d图，满足条件(2)吗？已经满足，图中任一欧拉回路即为最优邮路，如红线所示为最优邮路。v1v2v3v4v5v6v9v8v7256354434944(d)注：最优邮路不唯一5.2 树一、树的概念和性质树在许多领域有广泛应用。ABCD运动员体育比赛四强相遇厂长人事科生产科财务科生产计划室质量监控室生产执行室某工厂的组织结构定义14：连通且不含圈的无向图称为树。树中次为1的点称为树叶，次大于1的点称为分枝点。定理6：图T=(V,E)的V有n个顶点，E有m条边，则下面对树的说法是等价的：T是一个树；T无圈，且m=n-1;T连通，且m=n

11、-1;T无圈，但每加一新边即得唯一一个圈；T连通，但舍去一边就不连通；T中任意两点，有唯一链相连。二、图的生成树定义15：若图G的生成子图是一棵树，则称该树为G的生成树（支撑树），简称G的树。G中属于生成树的边称为树枝，不在生成树中的边称为弦。例，如图b是a的生成树，边e4,e5,e6为弦。e3e5e2e4e8e7e6e9e1(a)e2e3e8e7e9e1(b)定理7：图G(V,E)有生成树的充要条件是G是连通图在图中找生成树的方法分两种：(a)深探法(1)任取一点v,标号0；(2)若某点u已编号i，检查端点有u的各边，其另一端是否已编号？ 若有边(u,w)的w端未标号，则标w为i+1,令w取

12、代u，重复步骤(2); 若有u的所有边另一端均已编号，退到i-1编号的点r，以r代替u，重复步骤(2);如此重复直到全部点得到编号为止，得到生成树。例：利用深探法找出下图的生成树。原图对应生成树012345678910111213012345678910111213(b)广探法(1)任取一点v,标号0；(2)检查编号i的点，包含i点的所有边的另一端是否已编号？对所有未编号的这些点都编相同的号i+1;(3)对编号i+1的所有点重复步骤(2);如此重复直到全部点得到编号为止，得到生成树。例：利用广探法找出下图的生成树。原图10122132122343对应生成树01234212112233注：图的生

13、成树不唯一三、最小生成树问题定义16：连通图G=(V,E)，每条边上有非负权L(e)。一棵生成树所有树枝上权的总和，称为生成树的权。具有最小权的生成树称为最小生成树(最小支撑树)，简称最小树。许多网络问题都可以归结为最小树问题。如：(1)交通系统中设计总长度最小的公路网，将若干城市联系起来；(2)通信系统中用最小成本把计算机系统和设备连接到局域网。找出最小树的算法：(a)Kruskal算法：(1)从未选的边中选取边e，使它与已选边不构成圈，且e是未选边中最小权边；(2)重复步骤(1)，直至选够n-1(n为图的顶点数)条边为止。例：一个乡有9个村，相互间道路及路长如下图，问如何拉线连通各个村，且

14、使用线最短。v2v0v3v4v5v1v8v7v64121415531342424v2v0v3v4v5v1v8v7v612113122解：先将图中各边按路长由小至大排列，然后按顺序依次选择: (v0,v2), (v2,v3), (v3,v4), (v1,v8), (v0,v1), (v0,v6), (v5,v6),(v6,v7)，得到最小树，权为13。找出最小树的算法：(b)破圈法：(1)从图G中任选一棵树T1;(2)加上一条弦e1,使T1+e1能生成一个圈。去掉此圈中最大权边，得到新树T2。以T2代替T1,重复步骤2，直到所有弦检查完毕。v2v0v3v4v5v1v8v7v64121415531

15、342424v2v0v3v4v5v1v8v7v612113122例：将上例用破圈法求解最小树解：先求出一棵生成树如下，加弦(v1,v2) 发现其自身是圈(v1v2v0v1)中最大权边并去掉, 逐步求解得：v2v0v3v4v5v1v8v7v621453424四、根树及其应用定义17：一个有向图在不考虑边的方向时是一棵树，则这个有向图为有向树。定义18：有向树T恰有一个结点入次为0，其余各点入次均为1，则称T为根树（又称外向树）。入次为0的点为根，出次为0的点称为叶，其他顶点称为分枝点。设每边长为1，则根到某点vi的路长称为vi点的层次。v1v2v3v4v5v6v7定义19：根树中每个顶点的出次小

16、于或等于m，则称这棵树为m叉树。若每个顶点的出次恰好都等于m或0，则称之为完全m叉树。当m=2时，称为二叉树。令有s个叶子的二叉树T各叶子的权分别为pi，根到各叶子的距离(层次)为 li (i=1,s)，则二叉树的总权数为满足总权数最小的二叉树称为最优二叉树。求最优二叉树的算法：霍夫曼算法(1)将s个叶子按权由小至大排序，设p1 p2 ps;(2)将两个具有最小权的叶子合并成一个新分枝点，其权为p1+p2 ,将该新分枝点作为一个叶子，令s=s-1(若s=1停止计算)，转步骤(1)。例：若叶子s=6,其权分别为4,3,3,2,2,1, 求最优二叉树。解：按霍夫曼算法将最优二叉树构造如下:1322

17、334334122535493361223615549331223633412253直观意义：叶子的距离按权的递减而增加，总权最小。总权 pili =14 +24+23+32+32+42=385.3 最短路问题 最短路问题一般提法：设G(V,E)为连通图，图中各边(vi,vj)有权 lij (lij=表示两点间无边)，vs和vt是图中任意两点，求一条道路从vs到vt且该道路总权最小。一、Dijkstra算法它被公认是求无负权网络最短路问题的最好方法。基本原理：若vs,v1,vt-1,vt是从vs到vt的最短路，则vs,v1,vt-1是从vs到vt-1的最短路。该算法采用标号法。T标号：给vi点

18、T标号表示从vs到vi点的估计最短路权的上界，是临时标号，没有P标号的点都标有T标号。P标号：给vi点P标号表示从从vs到vi点的最短路权，是永久标号不再改变。 此算法每一步把某点的T标记改为P标记，当终点vt得到P标号时，全部计算结束。具体算法如下：(1)给vs以P标号,P(vs)=0,其余各点均给T标号,T(vi)= ;(2)若vi点为刚得到P标号的点，寻找点vj要求 (vi,vj)属于E且vj为T标号。对所有找到的vj点的T标号值进行更改：T(vj) = minT(vj), P(vi)+lij;(3)比较所有T标号的点，把最小T值的点v*改为P标号，即P(v*)=minT(vi)。若全部

19、点均为P标号时算法结束，否则返回步骤(2)。例：用Dijkstra算法求下图v1到v6的最短路。解: (1)P(v1)=0, 其余点T(vi)= +;(2)(v1,v2)和(v1,v3)属于E,且v2和v3是T编号，对这两点改变T值：T(v2)=minT(v2),P(v1)+l12=min+,0+4=4T(v3)=minT(v3),P(v1)+l13=min+,0+6=6(3)比较所有T标号,T(v2)最小,令P(v2)=4,记录路径(v1,v2)(4) v2为刚得到的P点,考察边(v2,v4)和(v2,v5)的端点v4,v5 T(v4)=minT(v4),P(v2)+l24=min+,4+5

20、=9 T(v5)=minT(v5),P(v2)+l25=min+,4+4=8(5)比较所有T标号,T(v3)最小,令P(v3)=6,记录路径(v1,v3)v1v3v5v2v4v6456447575(6)考察v3: T(v4)=minT(v4),P(v3)+l34=min9,6+4=9 T(v5)=minT(v5),P(v3)+l35=min8,6+7=8(7)比较所有T标号,T(v5)最小,令P(v5)=8,记录路径(v2,v5)(8)考察v5: T(v6)=minT(v6),P(v5)+l56=min+,8+5=13(9)比较所有T标号,T(v4)最小,令P(v4)=9,记录路径(v2,v4

21、)(10)考察v4: T(v6)=minT(v6),P(v4)+l46=min13,9+7=13(11)比较所有T标号,T(v6)最小,令P(v6)=13,记录路径(v5,v6)计算结束，最短路为v1 v2 v5 v6, 路长P(v6)=13，同时得到v1点到其余各点的最短距离。v1v3v5v2v4v6456447575例：某公司在某地区有6个销售点，已知该6个点的交通网络如图所示，边表示公路，数字表示路长，问公司的仓库应该建在哪个点，使得离仓库最远的销售点到仓库的距离最近？25v2v5v6v3v41520v12060301815解：实际是求网络中心。先求出v1到其他各点的最短路长dj,令D(

22、v1)=max(d1,d2,d6),表示仓库建在v1时离仓库最远的销售点的距离为D(v1)。逐次求出所有D(vi) (i=1,2,6), D(vi)中最小值对应的vi即是网络中心。 本例中：D(v1)=63, D(v2)=50, D(v3)=33, D(v4)=63, D(v5)=48, D(v6)=63, 其中D(v3)最小, v3即是网络中心。二、Floyd算法该算法可直接求出网络中任意两点的最短路。 令网络的权矩阵为D=(dij)nn，lij为vi到vj的距离，而矩阵元素Floyd算法步骤：(1)输入权矩阵D(0) =D;(2)计算 其中(3) 中元素 即是vi到vj的最短路。例：用Fl

23、oyd法求下图G中任意两点间的最短距离。25v2v5v6v3v41520v12060301815解：由图得到网络权矩阵为D (1) =D (0), D (4) =D (3), D (6) =D (5)，计算结束， D (6)中矩阵元素即为任意两点的最短路 。 表示从vi点到vj点直接有边或经v1为中间点时的最短路长, 和 分别表示从vi到vj最多经中间点v1,v2与v1,v2,v3的最短路长。5.4 最大流问题一、最大流相关概念 如图看作输油管道网，vs起点，vt终点，其它6点为中转站，数字表示管道的最大输油能力，问应如何安排各管道输油量，才能从始点到终点的总输油量最大？vsvtv1v2v3v

24、4v5v653453322435定义20：设有向连通图G=(V,E)，G的每条边(vi,vj)上有非负的容量cij，仅有一个入次为0的点(发点,或称源)和一个出次为0的点(收点,或称汇)，其余点为中间点，则G称为容量网络，记为G=(V,E,C) 对G中任一边(vi,vj)有流量fij，称集合f=fij为网络G上的一个流。称满足下列条件的流f为可行流：(1)容量限制条件：对G中每条边(vi,vj) ，有0 fij cij;(2)平衡条件：中间点vi有fij= fki, 即输入输出相等；对收、发点vs,vt有 fsi = fjt =W，W为网络总流量。可行流总是存在的，f=0是流量为0的可行流。最

25、大流问题就是在容量网络中寻找流量最大的可行流。当fij = cij ，称流f 对边(vi,vj)是饱和的。定义21：容量网络G=(V,E,C)中，vs, vt分别是发、收点，若有边集E是E的子集，它将G分为两个子图G1, G2，其顶点集合记为S, S(SS =V, SS=), 其中vs, vt分属S, S, 同时满足(1)G(V, E-E)不连通；(2)E为E的真子集时，G(V,E-E)仍连通，则称E为G的割集，记为E=(S,S)。 割集中所有始点在S，终点在S的边的容量之和称为割集容量。割集容量最小的称为G的最小割。图中(vs,v1),(vs,v2),(v3,v6)和(v1,v4),(v5,

26、vt), (v6,vt)都是割集，其容量分别是11和13。vsvtv1v2v3v4v5v653453322435二、最大流-最小割定理容量网络中割集是由vs到vt的必经之路，无论拿掉哪个割集， vs和vt不再相通，故任一可行流的流量不超过任一割集的容量。定理10：设f为网络G(V,E,C)的任一可行流, 流量为W, (S,S)为分离vs和vt的任一割集, 则有W C(S,S)定理11: (最大流-最小割定理) 任一网络G中，从vs到vt的最大流流量等于分离vs和vt的最小割容量。定义22：容量网络G中，若为从vs到vt的一条链，给定向为从vs到vt，上的边与同向的称为前向边，与反向的称为后向边

27、，其集合分别用+和-表示，f是一个可行流，如果满足则称为从vs到vt的(关于f的)可增广链。推论：可行流f是最大流的充要条件是不存在从vs到vt的(关于f的)可增广链。可增广链的实际意义：沿着这条链输送的流有潜力可挖，可按一定方法把流量调高。调整后的流在各点仍满足平衡条件和容量限制条件，仍为可行流。 寻求最大流的方法可从一个可行流开始，寻求它的可增广链，若存在则调整到流量更大的可行流，直到不能找到可增广链为止，其流量即为最大流。三、求最大流的标号算法1. 标号过程 (通过标号寻找可增广链)(1)给发点vs标号(,+)，此时 s+;(2)选择一个已标号的顶点vi , 处理vi所有未标号邻接点vj :(a)若边(vj,vi) E, 且fji0, 则令j=min(fji, i), 给vj标号(-vi, j)(b)若(vi,vj) E, 且fijcij , 令j=min(cij-fij, i), 给vj标号(+vi, j)(3)重复(2)直到收点vt被标号或不再有顶点可标号为止, 若vt获得标号,则找到可增广链, 转到调整过程, 若vt未获标号且标号过程已