合肥工业大学系统工程导论第4章图与网络

-4-1-第4章图与网络图与网络是运筹学的一个重要分支。其中，图论是从实践中抽象出来的最早的数学问题之一，如1736年欧拉提出的“哥尼斯堡七桥问题”、“哈密尔顿环问题”以及“地图四色问题”等。随后又发展出网络理论，并应用于电路分析、运输系统、信息论、工程设计和管理等方面。本章着重介绍有关图与网络的基本概念，以及网络最优化的两个基本问题——最短路问题和最大流问题。一、图与网络的基本概念1.概念的引入图论的理论和方法可用于解决企业管理、交通运输、日常生活等许多不同领域的问题，例如，在运输规划中，应怎样合理地组织运输路线和运量，使总的运费最省；又如，在组织生产时，应如何安排各生产工序间的衔接，才能使生产任务完成得既快又好；再如，邮递员送信时，应选择何种路线才能使所走的距离最短等。这些问题都可以用图论的方法进行求解。在实际生活中，人们为了反映某些对象间的关系，常用点和线画出各种各样的示意图。例1我国北京、上海等10个城市间的铁路交通示意图如图所示，它反映了这10个城市的铁路分布情况。图中，用点代表城市，点与点之间的连线代表两个城市之间的铁路线。诸如此类的示意图还有电话线分布图、煤气管道图、航空线图等。2.基本概念（1）图图：图是由一些点以及点之间的连线所组成的。其中，这些点又称为顶点。边（弧）：两顶点之间不带箭头的连线称为边；带箭头的连线称为弧。边（或弧）上相应的数值称为边（或弧）的权。无向图：由点和边构成的图称为无向图（简称图），记作G=(V，E)，其中V、E分别是G的顶点集合和边的集合。连接两顶点vi,vj∈V的边e记为e=(vi，vj)或e=(vj，vi)。有向图：由点和弧构成的图称为有向图，记作D=(V，A)，其中V、A分别是D的顶点集合和弧的集合。从起始点vi∈V指向终点vj∈V的弧a记为a=(vi，vj)≠(vj，vi)。多重边和环：两个顶点间具有两条以上的边称为多重边；若边的两端为同一顶点则称其为环，如图1（参见P82图4-1）中的“边7”。多重图和简单图：含多重边的图称为多重图；无环且无多重边的图称为简单图。本章讨论的图一般都是简单图。图1环图2支撑子图-4-2-支撑子图：如果图G=(V，E)，G'=(V'，E')且V'V，E'E，则称G'为G的子图，如图2(b)所示（参见P82图4-2(b)）；若在同一图中，V'=V，E'E，则称G'为G的支撑子图，如图2(c)所示（图4-2(c)）。（2）链链：在图G=(V，E)中，由一些顶点和边所组成的交错序列{v1,e1,v2,e2,…,vk1,ek,vk}就称为一条联结顶点v1、vk的链。开链和闭合链：起点和终点不是同一顶点的链，则称其为开链，否则就称其为闭合链。单纯链和基本链：一条没有重复边的链称为单纯链，如图3（参见P82图4-3）中的边序列{5,6,2,7,8}；一个没有重复顶点的链称为基本链，如图3中的边序列{1,2,3}。路和回路：一个开的基本链称为路，如图中的边序列{1,6,7,3}；一个闭合的基本链称为回路，如图中的边序列{1,6,5}。连通图：如果在一个图中任意两个不同的顶点之间至少有一条路，则该图就称为连通图。图3链图4树（3）树树：如果连通图G的子图Gl也是连通的，并包含了G的所有顶点，且没有回路，则称Gl为G的一个生成树（简称树），记为T，如图4（参见P83图4-4）中的(b)、(c)、(d)即为图(a)的树：T1={l,3,5}，T2={2,3,5}，T3={2,4,5}。组成树的边就称为树枝。树的性质如下．．．．．．：○1树的任意两个顶点之间只有一条链；○2在树中不相邻的两个顶点间添上—条边，则恰好得到一个回路；○3在树中去掉任何一条边，则成为不连通图；○4含有n个顶点的树，则有n1条边。例2已知有五个城市，试问如何在它们之间架设电话线，使任何两个城市都可以互相通话（允许通过其它城市），且电话线的根数最少？解用五个点v1,v2,v3,v4,v5代表五个城市，如果某两个城市之间架设电话线，则在相应的两点之间连一条边，则该电话线网就可以用一个图来表示。为了使任何两个城市都可以互相通话，则此图必须是连通图；另外，若此图中有回路，从回路上任意去掉一条边，使余下的图仍是连通的，且可以省去一根电话线。因此，满足要求的电话线网所对应的图必定是一个树，如图5所示。（注意：由于连通图对应的树有多个，故这里只给出了其中一个树）图5电话线网图6割集-4-3-（4）割集割集：将连通图分割为两个子图所需割断的最少边集就称为割集，如图6（参见P83图4-5）中的边集{8,9}、{1,3,6}、{4,5,6}等。注意：割集的定义表明，当去掉构成割集的一组边时，则原连通图被分割成相互分离的两部分；而只要少去掉一条边，则被分开的两部分仍是连通的。例如，边集{7,8,9}就不是割集，因为移去这个边集可以使图分离为两部分，但若再连上边7，已分离的图仍不能连通，不符合割集的定义。最小割集：对于一个图有若干个割集，其中边数最少的割集，则称其为最小割集（简称最小割），如图6中的边集{8,9}。二、最短路问题1.问题的提出在企业经营活动和日常生活中，常会遇到所谓的最短路问题，例如，从家中出发上班时，应走怎样的路线才能在最短时间内到达单位；假日外出旅游时，怎样选择旅游路线才能使花费最省；在企业经营中，需要运送一批物资到达某地，应选择怎样的运输路线才能使运费最省。类似于各种管道铺设、线路安排、设备更新、选址等都属于最短路问题。例3（管道铺设问题）从油田铺设管道，把原油运输到原油加工厂。要求管道必须沿图7所给定的路线铺设，图中v1点为油田，v9点为原油加工厂，弧权为相应路段的管道长度，试问如何铺设管道才能使管道总长最短？图7油田管道路线图图8油田管道最短路线图解显然，可能的油田管道铺设方案有多种，而不同方案的管道总长不同，则现在的问题是要寻求一条从v1到v9的路线，使油田的管道总长最短。若v1…viv9是从v1到v9的最短路，则v1…vi是从v1到vi的最短路，根据这一原理来求出该最短路问题。（1）与v1直接相连的点为v2、v3，但l13=2l12=4，所以v1v3为最短路，连接v1v3两点；（2）与v1v3直接相连的点为v2、v5、v6，则l12=4，l15=6，l16=6，min{l12,l15,l16}=4，连接v1v2；（3）与v1v2v3直接相连的点为v4、v5、v6，则l14=10，l15=6，l16=6，min{l14,l15,l16}={l15,l16}=6，连接v3v5、v3v6；（4）与v1v2v3v5v6直接相连的点为v4、v7、v8，则l14=10，l17=10，l18=8，min{l14,l17,l18}=8，连接v5v8；（5）与v1v2v3v5v6v8直接相连的点为v4、v7、v9，则l14=10，l17=10，l19=12，min{l14,l17,l18}={l14,l17}=10，连接v2v4、v5v7；（6）与v1v2v3v4v5v6v7v8直接相连的点为v9，则l19=12，min{l19}=12，连接v7v9、v8v9；（7）至此已将所有的点都相连，如图8所示。由图可见，v1v3v5v7v9或v1v3v5v8v9为所求的最短路线，相应的油田管道总长均为12。2.两固定顶点间的的最短路问题——标号算法（又称狄克斯屈拉算法）-4-4-最短路问题可以化为线性规划问题或动态规划问题进行求解，这里着重介绍目前常用的一种标号算法——狄克斯屈拉（Dijkstra）算法。利用这种算法，可以求出从起点v1到终点vn（即两个固定顶点间）的最短路，但该算法只适用于各弧权lij均为非负的情况（即lij≥0），一般在实际的管理工作中都能满足这一要求。注意：标号算法不适用于弧权为负的情况（但这种情况可以用福特算法来求解，略）。标号算法的基本思路是．．．．．．．．．．（参见P86）：从起点v1开始，对每个顶点给定一个标号，标号分临时标号T和固定标号P两类。顶点vi的临时标号记为T(i)，它表示起点v1到顶点vi最短距离的上界；顶点vi的固定标号记为P(i)，它表示起点v1到顶点vi的实际最短距离。已得到P类标号的顶点不再改变其标号，而没有标上P类标号的顶点则必须标上T类标号，算法的每一步都要把某一顶点的T类标号改为P类标号，直到终点vn获得P类标号时，就可求得从起点v1到终点vn的最短路线。标号算法的计算步骤如下．．．．．．．．．．．：（1）给起点v1标上固定标号P(1)=0，表示v1到v1的最短距离为零；其余顶点vj(j=2,…,n)标上临时标号T(j)=∞，表示v1到vj暂时无路；（2）设顶点vi是刚得到P类标号的顶点，把与顶点vi有弧直接相连且又属于T类标号的各顶点vj的标号，改为以下新的T类标号，即T(j)=min{T(j)，P(i)+lij}（3）在T类标号中选出标号最小的顶点j0，并将其临时标号T(j0)改为固定标号P(j0)；（4）若终点vn获得P类标号，则算法终止，最短路已经找到，否则返回（1）。确定由起点．．．．．v．1．到终点．．．v．n．最短路径的方法有以下两种．．．．．．．．．．．．：其一，在算法进行时作出标记，以表明每个固定标号的顶点是由哪个顶点得到标号的，然后从终点反向追踪到起点，这样就可找出最短路径；其二，从终点反向逆算，看哪个顶点的固定标号与终点固定标号的差值恰好等于与终点直接相连的相应弧权，如顶点j，则对顶点j之前的顶点再做类似的逐点推算，直到起点为止，这样也可找到最短路径；例4（邮递员投递路线问题）已知某邮递员沿着图9所示的街道网络投递邮件，试求从顶点1到顶点6的最短距离及其路线。图9街道网络路线图解用最短路标号算法求解时，首先给顶点1标上P类标号，即P(1)=0，其余顶点标上T类标号，且T(j)=∞（j=2,…,6）。第一步○1与顶点1直接相连且又为临时标号的顶点是2和3，则将这两个顶点的T类标号改为T(2)=min{T(2)，P(1)+l12}=min[∞，0+4]=4T(3)=min{T(3)，P(1)+l13}=min[∞，0+3]=3○2在所有的T类标号中，T(3)=3最小，于是令P(3)=3，即顶点3获得固定标号；第二步○1与顶点3直接相连且又为临时标号的顶点是2和5，则将它们的T类标号改为T(2)=min{T(2)，P(3)+l32}=min[4，3+2]=4-4-5-T(5)=min{T(5)，P(3)+l35}=min[∞，3+2]=5○2在所有的T类标号中，T(2)=4最小，于是令P(2)=4；第三步○1与顶点2直接相连且又为临时标号的顶点是4和5，则将它们的T类标号改为T(4)=min{T(4)，P(2)+l24}=min[∞，4+3]=7T(5)=min{T(5)，P(2)+l25}=min[5，4+1]=5○2在所有的T类标号中，T(5)=5最小，于是令P(5)=5；第四步○1与顶点5直接相连且又为临时标号的顶点是4和6，则将它们的T类标号改为T(4)=min{T(4)，P(5)+l54}=min[7，5+2]=7T(6)=min{T(6)，P(5)+l56}=min[∞，5+4]=9○2在所有的T类标号中，T(4)=7最小，于是令P(4)=7；第五步○1与顶点4直接相连且又为临时标号的顶点只有6，则将它的T类标号改为T(6)=min{T(6)，P(4)+l46}=min[9，7+3]=9○2显然应令P(6)=9，即终点（顶点6）获得固定标号，算法到此结束，则顶点1到顶点6的最短距离为9。要找出从顶点1到顶点6最短路的各顶点顺序，可从顶点6反向逆算。与顶点6直接相连的是顶点4和顶点5，而顶点6与顶点4或顶点5固定标号之差为2和4，与顶点6直接相连的弧中只有弧（5,6）的弧权为4，因此顶点6之前的是顶点5。类似地可以推算出，顶点5之前的是顶点3，顶点3之前的是顶点1，即有一条最短路线为1→3→5→6；或者得出，顶点5之前的是顶点2，顶点2之前的是顶点1，即另一条最短路线为1→2→5→6。这