运筹学图论概述

本章重点图的基本概念常见的四个问题的求解方法图的含义图是一种模型如公路、铁路交通图，通讯网络图等图是对现实的抽象很多问题都可以用顶点和边来表示，一般顶点表示实体，边(顶点与顶点之间的连线)表示实体之间的关系，顶点和边的集合定义为图图论的提出(1)用图来描述事物及其联系，最早是由瑞士数学家欧拉(Euler)于1736年解决哥尼斯堡七桥问题时提出的如右图所示，哥尼斯堡地区被河流分为了四个区域，四个区域之间有七座桥相连，问是否有一条路线，可以经过所有的桥并且每座桥只经过一次？BACD图论的提出(2)用图来表示这个问题用四个顶点表示四个地区用七条边表示七座桥要寻找这样的一条路线：经过所有的边并且每条边只经过一次该问题已经证明无解图的基本概念(1)图：顶点和边的集合点的集合用V表示，边的集合用E表示，则图可以表示为G=(V,E)如下图G=(V,E)其中，V={A,B,C,D}E={e1,e2,e3,e4,e5,e6,e7}E中，e1=(A,D),e2=(B,D),e3=(C,D)e4=(B,C),e5=(A,C),e6=(A,C),e7=(B,C)e2e1e3e4e5e6e7图的基本概念(2)边都没有方向的图称为无向图，前面所讲的图就是无向图。无向图的边eij=(vi,vj)=(vj,vi)=eji当图中的边都有方向时，称为有向图。为了区别于无向图，有向图用G(V,A)表示在有向图中，有向边又称为弧，用aij=(vi,vj)表示，(vi,vj)≠(vj,vi)，弧的方向用箭头标识既有边又有弧的图称为混合图下图中从左向右依次为：无向图，有向图，混合图图的基本概念(3)集合V中元素的个数称为图G的顶点数，记作p(G)。前例中，p(G)=4集合E(或A)中元素的个数称为图G的边数，记作q(G)。前例中，q(G)=7若e=(u,v)∈E(或a=(u,v)∈A)，则称u和v为e(或a)的端点，e(或a)称为顶点u和v的关联边，也称u,v与边e(或a)相关联。前例中，A,B是边e1的端点，e1是A,B的关联边若顶点u和v与同一条边相关联，则称u和v为相邻点若两条边ei和ej有同一个端点，则称ei和ej为相邻边图的基本概念(4)若一条边的两个端点是同一个顶点，则称该边为环若两个端点之间有多于一条边，则称为重边(书上称为多重边)，前例中，A,C之间和B,C之间都有两条边无环也无重边的图称为简单图与顶点v相关联的边的数目，称为该顶点的“度”(书上称为次)，记为d(v)度数为奇数的顶点称为奇点，度数为偶数的顶点称为偶点在有向图中，由顶点指向外的弧的数目称为正度，记为d+，指向该顶点的弧的数目称为负度，记为d–度数为0的点称为孤立点，度数为1的点称为悬挂点图的基本概念(5)与悬挂点连接的边称为悬挂边若图中所有的点都是孤立点，则称为空图定理6.1所有顶点的度数之和，等于所有边数的两倍原因：每条边关联两个顶点，计算顶点的度数时，每条边计算了2次定理6.2图中奇点的个数总是偶数个原因：所有顶点的度数之和是偶数，偶点的度数之和也是偶数，因此，奇点的度数之和必为偶数，因此，奇点的个数必是偶数个图的基本概念(6)点边交错序列v0,e1,v1,e2,v2,…,vn-1,en,vn称为链。其中v0称为路的起点，vn称为路的终点若v0≠vn，称为开链；反之，称为闭链(对于无向图而言，也称为回路)若链中所含的边均不相同，称为简单链若链中所含的顶点均不相同，称为初等链(对于无向图而言，也称为通路)除起点和终点外均不相同的闭链，称为圈(对于无向图而言，也称为初等回路)以上概念(除特别标注的外)对无向图和有向图均适用图的基本概念(7)在有向图中，点边交错序列v0,e1,v1,e2,v2,…,vn-1,en,vn(其中ek=(vk-1,vk))称为路若v0≠vn，称为开路；反之，称为回路(注意和无向图的回路区分开来)若路中所含的边均不相同，称为简单路若路中所含的顶点均不相同，称为初等路除起点和终点外均不相同的回路，称为初等回路(注意和无向图的初等回路区分开来)本页概念都是针对有向图图的基本概念(8)若一个图(无向图或有向图)中任意两点之间至少有一条初等链连接，则称该图为连通图，否则称为不连通图在一个有向图中，若任意两点u和v，u到v和v到u之间都至少有一条初等路连接，则称该图为强连通图，否则称为非强连通图图的基本概念(9)子图：设G1=(V1,E1)，G2=(V2,E2)，若V1V2，E1E2，则称G1是G2的子图注：生成子图时，可以只选顶点不选与该顶点相关联的边，但不能只选边不选与该边相关联的顶点如下图，右图是左图的子图图的基本概念(10)如下图，右图是左图的真子图真子图：若V1V2，E1E2，称G1是G2的真子图部分图：若V1=V2，E1E2，称G1是G2的部分图图的基本概念(11)导出子图：若V1V2，E1={(ui,vj)E2|uiV1,vjV1}，称G1是G2中由V1导出的导出子图，记作G(V1)如下图，右图是左图的导出子图图的基本概念(12)一个没有圈的图称为无圈图或称为林一个连通的无圈图称为树一个林的每个连通子图都是一个树定理6.3：关于树的以下描述是等价的无圈连通图(定义)无圈图G，q(G)=p(G)-1(定义+对顶点个数用归纳法)连通图G，q(G)=p(G)-1(定义+对顶点个数用归纳法)无圈，但增加一条边可以得到唯一的圈(定义+对顶点个数用归纳法)连通，但去掉一条边就不连通(反证法)每一对顶点之间有且仅有一条初等链(反证法)图的基本概念(13)若T是图G的部分图，且T是树，则称T为G的生成树(书上称为部分树)图的存储方式(1)计算机中存储图一般采用矩阵存储常用的存储方法有两种邻接矩阵关联矩阵图的存储方式(2)对于无向图，邻接矩阵存储方式如下若顶点vi和vj之间没有边，则aij=aji=0若顶点vi和vj之间存在n条边，则aij=aji=n注：一般i≤jv1v2v3v4v5图的存储方式(3)v1v2v3v4v5对于有向图，邻接矩阵存储方式如下若顶点vi和vj之间没有弧，则aij=0若顶点vi和vj之间存在n条弧(vi,vj)，则aij=n注：允许i=j图的存储方式(4)对于无向图，关联矩阵存储方式如下若顶点vi不和边ej相关联，则bij=0若顶点vi和边ej相关联，则bij=1v1v2v3v4v5e1e2e3e4e5e6e7e8e9e9关联的顶点个数为1，是自环图的存储方式(5)对于有向图，关联矩阵存储方式如下若顶点vi不和弧ej相关联，则bij=0若顶点vi是弧ej的起点，则bij=1若顶点vi是弧ej的终点，则bij=-1若顶点vi既是弧ej的起点又是弧ej的终点，则bij=2v1v2v3v4v5e1e2e3e4e5e6e7e8e9简单图的权值矩阵(1)对于赋权简单图，权值矩阵存储方式如下若顶点vi和vj之间没有边，则wij=0若顶点vi和vj之间有边(vi,vj)，则wij=相应边的权值注：无向图和有向图均适用，有向图要注意边的方向简单图的权值矩阵(2)v1v2v3v4v5376245v1v2v3v4v5376245最短路线问题一般针对赋权连通图(有向图或无向图皆可)，求两点之间所经路线权值之和为最小的路线求解该问题可以采用上一章介绍的动态规划的方法该方法适用于无负初等回路(指所有边的权值之和为负值的初等回路)的赋权连通图(有向图或无向图皆可)；若有负初等回路，则不存在最短路线该方法需要人工划分阶段，适合人工计算书上介绍的三种算法，不需要明确的划分阶段，较为适合计算机运算狄克斯拉(Dijkstra)算法(1)该算法有两个依据从v1到vn的最短路线也是从vn到v1的最短路线对于无向图必定成立对于有向图而言，vn到v1的最短路线是指将图中弧的方向反过来，但权值不变时的最短路线以vn为起点，v1为终点应用动态规划的最优性原理第一条依据保证了按这种方法求得的结果是从v1到vn的最短路线狄克斯拉(Dijkstra)算法(2)算法步骤已知网络的距离矩阵L=(lij)，lij表示vi到vj的弧上的距离权值令i=1，S1={v1}，S2={v2,v3,…,vn}，令P(v1)=0，T(vj)=∞（vj∈S2）令T(vj)=min{T(vj)，P(vi)+lij|vj∈S2}令vk=min{T(vj)|vj∈S2}，P(vk)=T(vk)若vk=vn，则已经找到v1到vn的最短距离P(vk)否则，令i=k，从S2中删去vi，转上一步狄克斯拉(Dijkstra)算法(3)该算法适用于无负初等回路的赋权连通图(有向图或无向图皆可)，但算法本身不能判定图中是否存在负初等回路因此，该算法一般应用于无负权值的赋权连通有向图或无向图示例(6.1-1)sabcdt5839149543路线图如下所示，箭头表示通行方向，线上数字表示道路长度，试用Dijkstra算法求s到t的最短路线示例(6.1-2)sabcdt初始值T()第1次P()+lijT()第2次P()+lijT()第3次P()+lijT()第4次P()+lijT()第5次P()+lijT()0∞∞∞∞∞0+50+80+∞0+∞0+∞58∞∞∞5+∞5+35+95+∞8814∞8+∞8+48+∞812∞8+38+9111711+51612345示例(6.1-3)sabcdt5839149543海斯算法(1)该算法有两个依据从v1到vn的最短路线也是从vn到v1的最短路线对于无向图必定成立对于有向图而言，vn到v1的最短路线是指将图中弧的方向反过来，但权值不变时的最短路线若从vi到vj的最短路线经过vk，则vi到vk、vk到vj的都是相应的最优路线第一条依据保证了从vi到vj的最短路线也是从vj到vi的最短路线则根据动态规划最优性原理，vk到vj和vk到vi都是相应的最优路线，由此得到上面的结论海斯算法(2)算法步骤已知网络的距离矩阵L=(lij)，lij表示vi到vj的弧上的距离权值令dij(0)=lij，i=1～n，j=1～ndij(t)表示从vi到vj的2t步距离当dij(m-1)已知时，令

dij(m)=min{dik(m-1)+dkj(m-1)|k=1～n}当对所有的i,j有dij(m)=dij(m-1)时，dij(m)是vi到vj的最短距离。否则，若2m-1＜n-1，m=m+1，转上一步；若2m-1≥n-1，说明存在负初等回路，最短路线不存在，算法停止海斯算法(3)该算法可以判断是否存在负初等回路，适用于任意权值的赋权连通有向图或无向图所得的结果矩阵中包含了图中任意两点之间的最短距离示例(6.2-1)sabcdt5839149543路线图如下所示，箭头表示通行方向，线上数字表示道路长度，试用海斯算法求s到t的最短路线示例(6.2-2)示例(6.2-3)示例(6.2-4)由于D(3)=D(2)，停止计算s到t的最短路线长度为16由D(2)知s到t经过c由D(1)知s到c经过a，c到t经过d则最短路线为sacdtsabcdt5839149543福德(Ford)算法(1)该算法和Dijkstra算法一样有两个依据从v1到vn的最短路线也是从vn到v1的最短路线对于无向图必定成立对于有向图而言，vn到v1的最短路线是指将图中弧的方向反过来，但权值不变时的最短路线以vn为起点，v1为终点应用动态规划的最优性原理第一条依据保证了按这种方法求得的结果是从v1到vn的最短路线福德(Ford)算法(2)算法步骤已知网络的距离矩阵L=(lij)，lij表示vi到vj的弧上的距离权值令dj(1)=l1j，j=1～ndj(t)表示从v1到vj的步数不超过t的最短距离当dj(k)已知时，令dj(k+1)=min{di(k)+lij|i=1～n}当对所有的j有dj(k+1)=dj(k)时，dj(k)是v1到vj的最短距离。否则，若k＜n-1，k=k+1，转上一步；若k≥n-1，说明存在负初等回路，最短路线不存在，算法停止福德(Ford)算法(3)该算法可以判断是否存在负初等回路，适用于任意权值的赋权连通有向图或无向图所得的结果中包含了从v1到其他任意点的最短距离示例(6.3-1)sabcdt5839149543路线图如下所示，箭头表示通行方向，线上数字表示道路长度，试用Ford算法求s到t的最短路线示例(6.3-2)abcdd示例(6.3-3)由于dj(4)=dj(3)(j=s,a,b,c,d,t)，停止计算s到t的最短路线长度为16最短路线为sacdtsabcdt5839149543最小生成树问题一般针对赋权连通图，求该图权值之和为最小的生成树求解该问题一般有两种方法破圈法生长法破圈法求最小生成树假设原图为赋权连通图破圈法依据树的定义给出求最小生成树算法破圈法步骤如下在图中找到一个圈，进入下一步；若无圈则停止，此时的图就是原图的最小生成树查看该圈与其它圈是否有公共边若没有公共边，在该圈中选权值最大的边，去掉该边；对新的图返回上一步若有公共边，将这些有公共边的若干个圈合在一起看作一个回路，在该回路中选权值最大的边，去掉该边；对新的图返回上一步示例(6.4-1)3354726432用破圈法求下图的最小生成树生长法求最小生成树(1)生长法依据根据动态规划最优性原理，划分n-1个阶段x1=S1从图中任选一点vi，令S1={vi}，S2=V-S1，k=1uk为k阶段选中的权值最小的边(vi,vj)，vi∈S1，vj∈S2xk+1=xk+{uk}+{vj}S1=S1+{(vi,vj)}+{vj}，S2=S2-{vj}xn状态结束此时，S1就是要求的最小生成树的点边集合，S2是空集生长法求最小生成树(2)假设原图为赋权连通图生长法步骤如下从图中任选一点vi，令S1={vi}，S2=V-S1从S1中的各点到S2中各点的边中选择权值最小的边(vi,vj)，vi∈S1，vj∈S2令S1=S1+{(vi,vj)}+{vj}，S2=S2-{vj}若S2是空集，则停止，S1就是要求的最小生成树的点边集合；否则转第二步示例(6.5-1)3354726432用生长法求下图的最小生成树作业(17)书上218页5-1的(b)补充：3和8之间权值为13破圈法或生长法皆可最大流问题(1)一般针对赋权连通有向图，每条弧的权值表示该弧允许流过的最大流量，每个顶点的流入量之和等于流出量之和，求图上两定点之间允许流过的最大流量最大流-最小割定理最大流量等于最小割集(容量最小的割集)的容量注：将图G中顶点集合V分为两个集合S1和S2，其中起点vs∈S1、终点vt∈S2，且S1∪S2=V、S1∩S2=，则把集合C={(vi,vj)|vi∈S1,vj∈S2}称为图G的一个割集割集中弧的权值之和称为该割集的容量最大流问题(2)利用最大流-最小割定理，福德和富克逊提出了求解最大流问题的标号法可行流最大流结束改变流量是否最大流问题(3)标号法相关概念若弧(vi,vj)上的流量xij=bij，则称该弧为饱和弧，否则称为非饱和弧若弧(vi,vj)上的流量xij=0，则称该弧为零流弧，否则称为非零流弧在一条从vs到vt的点边交错序列中，与vs到vt方向一致的弧称为正向弧，与vs到vt方向相反的弧称为逆向弧若从vs到vt的某个点边交错序列中，正向弧均为非饱和弧，逆向弧均为非零流弧，则称该点边交错序列为一条流量增广链最大流问题(4)流量增广链的作用它是用来增加正向总流量的使增广链上正向弧的流量增大使增广链上逆向弧的流量减小若找不到，表示不能再增大正向总流量，即当前的正向总流量就是最大流量最大流问题(5)标号法步骤如下分配vi到vj的初始流xij寻找增广链，若不存在，则已经最优；否则进入下一步调整。寻找增广链方法如下将vs标记上(-,∞)，S1={vs}，S2=V-S1若存在以S1中点为起点、以S2中点为终点的非饱和弧(vi,vj)，则为vj标记上(vi+,zj)，zj=min{zi,bij-xij}，S1=S1+{vj}，S2=S2-{vj}若存在以S2中点为起点、以S1中点为终点的非零流弧(vj,vi)，则为vj标记上(vi-,zj)，zj=min{zi,xji}，S1=S1+{vj}，S2=S2-{vj}若S1中已包含vt

，则已找到一条增广链，否则转向第二步最大流问题(6)调整流量，方法如下设vt

上的标记为(vk+,zt)，则整个增广链上最大的调整量为z=zt由vt

上的标记可以得到增广链上的前一个顶点vk

，依次向前可以找到整个增广链在增广链上，正向弧流量增加z，逆向弧流量减少z返回第二步继续寻找下一个增广链示例(6.6-1)(9)(8)(3)(7)(4)(4)(2)(6)(11)711106915543vsvtv2v3v4v5(-,∞)(vs+,7)(v2-,3)(v3+,1)(v3+,3)(v5+,3)用标号法求出从vs到vt的最大流示例(6.6-2)调整流量，得711106915543vsvtv2v3v4v5(11)(0)(9)(7)(4)(4)(5)(9)(11)(-,∞)(vs+,4)找不到增广链，则当前流量20为最优最小费用-最大流问题(1)一般情况下，最大流量是唯一的，而相应的每条弧上的流量分布却是不唯一的如果已知流过弧(vi,vj)的单位流量要发生cij的费用，要求使得总费用为最小的最大流流量分配方案，这种问题称为最小费用-最大流问题可以使用对偶法解决这个问题最小费用-最大流问题(2)对偶法原理对原图求出从vs到vt的所有初等路将这些初等路按照单位流量费用之和从小到大排序，编号1,2,3,…,m使第1号初等路上的流量为最大在余下的允许流量中，使第2号初等路上的流量为最大在余下的允许流量中，使第3号初等路上的流量为最大…在余下的允许流量中，使第m号初等路上的流量为最大此时，图中的流量分布即为最小费用-最大流在实际使用时，要对原图求出从vs到vt的所有初等路有一定的难度，容易遗漏最小费用-最大流问题(3)因此，对偶法在实际操作时求出最大流量，以0流为初始可行流对原图求出从vs到vt的单位流量费用之和为最小的初等路调整使得该初等路上的流量为最大，若当前可行流的流量等于最大流量，则当前可行流就是最小费用-最大流，否则进入下一步对当前可行流生成扩展费用图。在扩展费用图中，从原图的允许流量中去掉当前可行流的流量，将图中某些弧的单位流量费用调整为∞(这些弧的允许流量已经减小为0，使得此弧不通)在该扩展费用图中，求出新的从vs到vt的单位流量费用之和为最小的初等路，转向第三步最小费用-最大流问题(4)对偶法步骤用标号法求出最大流量将原图作为初始扩展费用图，以0流作为初始可行流在扩展费用图上，用Ford算法求出从vs到vt的单位流量费用之和为最小的初等路作为增广链按前面标号法中调整流量的方法调整流量，得到一个新的可行流若当前可行流的流量等于最大流量，则当前可行流就是最小费用-最大流，否则进入下一步对当前可行流生成新的扩展费用图，转向第三步最小费用-最大流问题(5)扩展费用图的生成在弧(vi,vj)上若xij=0，则原弧不变若0＜xij＜bij

，则把弧(vi,vj)改造成如下的两条弧若xij=bij

，则把弧(vi,vj)改造成方向相反的另一条弧vivj(bij-xij,cij)(xij,-cij)vivj(bij,cij)在生成增广链时用不到反向弧(vj,vi)

，这样就去掉了当前可行流的流量同理，使得弧(vi,vj)不通，将其单位流量费用调整为∞示例(6.7-1)求出从vs到vt的最小费用-最大流，图中弧上数字含义为(bij,cij)vsvtv2v4v3v5(15,2)(9,6)(3,3)(5,5)(4,9)(7,8)(6,3)(10,1)(11,3)示例(6.7-2)由示例(6.6)，如下图，已知从vs到vt的最大流量为20vsvtv2v4v3v5(15,2)(9,6)(3,3)(5,5)(4,9)(7,8)(6,3)(10,1)