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

1、第4章 图与网络图与网络是运筹学的一个重要分支。其中，图论是从实践中抽象出来的最早的数学问题之一，如1736年欧拉提出的“哥尼斯堡七桥问题”、“哈密尔顿环问题”以及“地图四色问题”等。随后又发展出网络理论，并应用于电路分析、运输系统、信息论、工程设计和管理等方面。本章着重介绍有关图与网络的基本概念，以及网络最优化的两个基本问题最短路问题和最大流问题。一、 图与网络的基本概念1. 概念的引入图论的理论和方法可用于解决企业管理、交通运输、日常生活等许多不同领域的问题，例如，在运输规划中，应怎样合理地组织运输路线和运量，使总的运费最省；又如，在组织生产时，应如何安排各生产工序间的衔接，才能使生产任务

2、完成得既快又好；再如，邮递员送信时，应选择何种路线才能使所走的距离最短等。这些问题都可以用图论的方法进行求解。在实际生活中，人们为了反映某些对象间的关系，常用点和线画出各种各样的示意图。例1 我国北京、上海等10个城市间的铁路交通示意图如图所示，它反映了这10个城市的铁路分布情况。图中，用点代表城市，点与点之间的连线代表两个城市之间的铁路线。诸如此类的示意图还有电话线分布图、煤气管道图、航空线图等。2. 基本概念（1）图图：图是由一些点以及点之间的连线所组成的。其中，这些点又称为顶点。边（弧）：两顶点之间不带箭头的连线称为边；带箭头的连线称为弧。边（或弧）上相应的数值称为边（或弧）的权。无向图

3、：由点和边构成的图称为无向图（简称图），记作G = (V，E)，其中V、E分别是G的顶点集合和边的集合。连接两顶点vi, vjV的边e记为e = (vi，vj)或e = (vj，vi)。有向图：由点和弧构成的图称为有向图，记作D = (V，A)，其中V、A分别是D的顶点集合和弧的集合。从起始点viV指向终点vjV的弧a记为a = (vi，vj)(vj，vi)。多重边和环：两个顶点间具有两条以上的边称为多重边；若边的两端为同一顶点则称其为环，如图1（参见P82图4-1）中的“边7”。多重图和简单图：含多重边的图称为多重图；无环且无多重边的图称为简单图。本章讨论的图一般都是简单图。 图1 环 图2

4、 支撑子图支撑子图：如果图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

5、；一个没有重复顶点的链称为基本链，如图3中的边序列1, 2, 3。路和回路：一个开的基本链称为路，如图中的边序列1, 6, 7, 3；一个闭合的基本链称为回路，如图中的边序列1, 6, 5。连通图：如果在一个图中任意两个不同的顶点之间至少有一条路，则该图就称为连通图。 图3 链 图4 树（3）树树：如果连通图G的子图G l也是连通的，并包含了G的所有顶点，且没有回路，则称G l为G的一个生成树（简称树），记为T，如图4（参见P83图4-4）中的(b)、(c)、(d) 即为图(a)的树：T1 = l, 3, 5，T2 = 2, 3, 5，T3 = 2, 4, 5。组成树的边就称为树枝。树的性质如

6、下： 树的任意两个顶点之间只有一条链； 在树中不相邻的两个顶点间添上条边，则恰好得到一个回路； 在树中去掉任何一条边，则成为不连通图； 含有n个顶点的树，则有n-1条边。例2 已知有五个城市，试问如何在它们之间架设电话线，使任何两个城市都可以互相通话（允许通过其它城市），且电话线的根数最少？解 用五个点v1, v2, v3, v4, v5代表五个城市，如果某两个城市之间架设电话线，则在相应的两点之间连一条边，则该电话线网就可以用一个图来表示。为了使任何两个城市都可以互相通话，则此图必须是连通图；另外，若此图中有回路，从回路上任意去掉一条边，使余下的图仍是连通的，且可以省去一根电话线。因此，满足

7、要求的电话线网所对应的图必定是一个树，如图5所示。（注意：由于连通图对应的树有多个，故这里只给出了其中一个树） 图5 电话线网 图6 割集（4）割集割集：将连通图分割为两个子图所需割断的最少边集就称为割集，如图6（参见P83图4-5）中的边集8, 9、1, 3, 6、4, 5, 6等。注意：割集的定义表明，当去掉构成割集的一组边时，则原连通图被分割成相互分离的两部分；而只要少去掉一条边，则被分开的两部分仍是连通的。例如，边集7, 8, 9就不是割集，因为移去这个边集可以使图分离为两部分，但若再连上边7，已分离的图仍不能连通，不符合割集的定义。最小割集：对于一个图有若干个割集，其中边数最少的割集

8、，则称其为最小割集（简称最小割），如图6中的边集8, 9。二、 最短路问题1. 问题的提出 在企业经营活动和日常生活中，常会遇到所谓的最短路问题，例如，从家中出发上班时，应走怎样的路线才能在最短时间内到达单位；假日外出旅游时，怎样选择旅游路线才能使花费最省；在企业经营中，需要运送一批物资到达某地，应选择怎样的运输路线才能使运费最省。类似于各种管道铺设、线路安排、设备更新、选址等都属于最短路问题。例3（管道铺设问题） 从油田铺设管道，把原油运输到原油加工厂。要求管道必须沿图7所给定的路线铺设，图中v1点为油田，v9点为原油加工厂，弧权为相应路段的管道长度，试问如何铺设管道才能使管道总长最短？ 图

9、7 油田管道路线图 图8 油田管道最短路线图解 显然，可能的油田管道铺设方案有多种，而不同方案的管道总长不同，则现在的问题是要寻求一条从v1到v9的路线，使油田的管道总长最短。若v1 - - vi - v9是从v1到v9的最短路，则v1 - - vi是从v1到vi的最短路，根据这一原理来求出该最短路问题。（1）与v1直接相连的点为v2、v3，但l13 = 2 l12 = 4，所以v1 v3为最短路，连接v1 v3两点；（2）与v1 v3直接相连的点为v2、v5、v6，则l12 = 4，l15 = 6，l16 = 6，minl12, l15, l16 = 4，连接v1 v2；（3）与v1 v2

10、v3直接相连的点为v4、v5、v6，则l14 = 10，l15 = 6，l16 = 6，minl14, l15, l16 = l15, l16 = 6，连接v3 v5、v3 v6；（4）与v1 v2 v3 v5 v6直接相连的点为v4、v7、v8，则l14 = 10，l17 = 10，l18 = 8，minl14, l17, l18 = 8，连接v5 v8；（5）与v1 v2 v3 v5 v6 v8直接相连的点为v4、v7、v9，则l14 = 10，l17 = 10，l19 = 12，minl14, l17, l18 = l14, l17 = 10，连接v2 v4、v5 v7；（6）与v1 v

11、2 v3 v4 v5 v6 v7 v8直接相连的点为v9，则l19 = 12，minl19 = 12，连接v7 v9、v8v9；（7）至此已将所有的点都相连，如图8所示。由图可见，v1 v3 v5 v7 v9或v1 v3 v5 v8 v9为所求的最短路线，相应的油田管道总长均为12。2. 两固定顶点间的的最短路问题标号算法（又称狄克斯屈拉算法）最短路问题可以化为线性规划问题或动态规划问题进行求解，这里着重介绍目前常用的一种标号算法狄克斯屈拉（Dijkstra）算法。利用这种算法，可以求出从起点v1到终点vn（即两个固定顶点间）的最短路，但该算法只适用于各弧权li j均为非负的情况（即li j0

12、），一般在实际的管理工作中都能满足这一要求。注意：标号算法不适用于弧权为负的情况（但这种情况可以用福特算法来求解，略）。标号算法的基本思路是（参见P86）：从起点v1开始，对每个顶点给定一个标号，标号分临时标号T和固定标号P两类。顶点vi的临时标号记为T ( i)，它表示起点v1到顶点vi最短距离的上界；顶点vi的固定标号记为P ( i )，它表示起点v1到顶点vi的实际最短距离。已得到P类标号的顶点不再改变其标号，而没有标上P类标号的顶点则必须标上T类标号，算法的每一步都要把某一顶点的T类标号改为P类标号，直到终点vn获得P类标号时，就可求得从起点v1到终点vn的最短路线。标号算法的计算步骤

13、如下：（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 ) + li j （3）在T类标号中选出标号最小的顶点j0，并将其临时标号T ( j0 )改为固定标号P ( j0 )；（4）若终点vn获得P类标号，则算法终止，最短路已经找到，否则返回（1）。确定由起点v1到终点vn最短路径的方法有以下两种：

14、其一，在算法进行时作出标记，以表明每个固定标号的顶点是由哪个顶点得到标号的，然后从终点反向追踪到起点，这样就可找出最短路径；其二，从终点反向逆算，看哪个顶点的固定标号与终点固定标号的差值恰好等于与终点直接相连的相应弧权，如顶点j，则对顶点j之前的顶点再做类似的逐点推算，直到起点为止，这样也可找到最短路径；例4（邮递员投递路线问题） 已知某邮递员沿着图9所示的街道网络投递邮件，试求从顶点1到顶点6的最短距离及其路线。图9 街道网络路线图解 用最短路标号算法求解时，首先给顶点1标上P类标号，即P (1) = 0，其余顶点标上T类标号，且T ( j ) = （ j =2, 6）。第一步 与顶点1直接

15、相连且又为临时标号的顶点是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 在所有的T类标号中，T ( 3 ) = 3最小，于是令P (3) = 3，即顶点3获得固定标号；第二步 与顶点3直接相连且又为临时标号的顶点是2和5，则将它们的T类标号改为T (2 ) = min T (2 )，P (3) + l32 = min4，3+2 = 4T (5 ) = min T (5 )，P (3) + l35 = min，3+2 = 5

16、在所有的T类标号中，T ( 2 ) = 4最小，于是令P (2 ) = 4；第三步 与顶点2直接相连且又为临时标号的顶点是4和5，则将它们的T类标号改为T (4 ) = min T (4 )，P (2) + l24 = min，4+3 = 7T (5 ) = min T (5 )，P (2) + l25 = min5，4+1 = 5 在所有的T类标号中，T ( 5 ) = 5最小，于是令P (5) = 5；第四步 与顶点5直接相连且又为临时标号的顶点是4和6，则将它们的T类标号改为T (4 ) = min T (4 )，P (5) + l54 = min7，5+2 = 7T (6 ) = mi

17、n T (6 )，P (5) + l56 = min，5+4 = 9 在所有的T类标号中，T ( 4 ) = 7最小，于是令P (4) = 7；第五步 与顶点4直接相连且又为临时标号的顶点只有6，则将它的T类标号改为T (6 ) = min T (6 )，P (4) + l46 = min9，7+3 = 9 显然应令P (6) = 9，即终点（顶点6）获得固定标号，算法到此结束，则顶点1到顶点6的最短距离为9。要找出从顶点1到顶点6最短路的各顶点顺序，可从顶点6反向逆算。与顶点6直接相连的是顶点4和顶点5，而顶点6与顶点4或顶点5固定标号之差为2和4，与顶点6直接相连的弧中只有弧（5, 6）的

18、弧权为4，因此顶点6之前的是顶点5。类似地可以推算出，顶点5之前的是顶点3，顶点3之前的是顶点1，即有一条最短路线为1356；或者得出，顶点5之前的是顶点2，顶点2之前的是顶点1，即另一条最短路线为1256。这两条路线的最短距离均为9。注意：标号算法可用于任何弧（边）权为正的有向图（无向图）。3. 任意两顶点间的最短路问题福劳德算法网络图中任意两顶点间的最短路问题比上述两固定顶点间的最短路问题更具有普遍性。显然，该问题可以应用前面介绍的标号算法（即狄克斯屈拉算法），分别将图中每两个顶点作为起点和终点，并通过反复计算来确定。但这样做，其计算工作量会相当大，因此，下面介绍一种新算法福劳德算法。设网

19、络图的顶点编号为1, 2, , N，令D m矩阵的元素di j m为顶点vi到vj的一条最短路长度，该路径的中间顶点只有m个。若不存在这种最短路，则di j m = 。由di j m的含义可知，di j 0为直接相连（即相邻）的两顶点间的最短长度，且di i 0 = 0；di j N为所要确定的任意两顶点vi、vj之间的最短距离。福劳德算法的求解步骤为：（1）确定D 0矩阵，其元素di j0为任意两相邻顶点vi、vj间的最短路长度，若顶点vi、vj间不存在这种最短路，则di j 0 = ；若i = j，则di i 0 = 0；（2）对m = 1, 2, , N，依次按下式由D m-1矩阵确定D

20、 m矩阵：di j m = min di m m-1 + dm j m-1，di j m-1若选出的最小元素是由di m m-1 + dm j m-1决定的，则记下m；若二者相等或取决于di j m-1，则不记录；（3）如此类推，直到计算出D N矩阵为止。例5（防火安全问题） 某工地有四个重点防火点，道路和防火点位置如图10所示，试问安全员该如何确定任一防火点到其他防火点的最短路径？图10 防火点位置及其道路示意图解 应用福劳德算法：第一步，写出D 0矩阵第二步，根据D 0矩阵列表求出D 1矩阵和相应的路径di j 1 = mindi1 0 +d1 j 0, di j 0中间点di j 1 =

21、 mindi1 0 +d1 j 0, di j 0中间点d11 1 = d11 0 =0d311 = min6+0, 6=6d121 = min0+1, 1=1d321 = min6+1, 5=5d131 = min0+2, 2=2d331 = min6+2, 0=0d141 = min0+1, 1=1d341 = min6+1, 2=2d211 = min2+0, 2=2d411 = min1+0, 1=1d221 = min2+1, 0=0d421 = min1+1, =21d231 = min2+2, 7=41d431 = min1+2, 4=31d241 = min2+1, =31d4

22、41 = min1+1, 0=0其路径矩阵为其中，D 1中的矩阵元素表示中间点为1（即m=1）时各点间的最短距离，相应的路径表示经过中间点1的最短路径。例如，d421 =2表示路径412对应的距离为2。第三步，由D 1矩阵按上述方法求出D 2矩阵和相应的路径 此时中间点为两个，即m=2，其计算公式为di j 2 = mindi2 1 +d2 j1, di j 1di j 2 = mindi2 1 +d2 j1, di j 1中间点di j 2 = mindi2 1 +d2 j1, di j 1中间点d11 2 = min1+2, 0=0d312= min5+2, 6=6d122 = min1+

23、0, 1=1d322= min5+0, 5=5d132 = min1+4, 2=2d332= min5+4, 0=0d142 = min1+3, 1=1d342= min5+3, 2=2d212 = min0+2, 2=2d412 = min2+2, 1=1d222= min0+0, 0=0d422= min2+0, 2=21d232= min0+4, 4=41d432= min2+4, 3=31d242 = min0+3, 3=31d442 = min2+3, 0=0由于没有选择中间点，所以对应的路径与上一步相同。注意，D 2中的矩阵元素表示经过两个中间点时各点间的最短距离，而不是经过第二个

24、顶点时各点间的最短距离，因为公式di j 2 = mindi2 1 +d2 j1, di j 1中di2 1 +d2 j1或di j 1为已经经过一个中间点的值。第四步，由D 2矩阵按上述方法求出D 3矩阵和相应的路径 此时中间点为三个，即m=3，其计算公式为di j 3 = mindi32 +d3 j2, di j 2di j 3 = mindi32 +d3 j2, di j 2中间点di j 3 = mindi32 +d3 j2, di j 2中间点d11 3 = min2+6, 0=0d313 = min0+6, 6=6d123 = min2+5, 1=1d323 = min0+5, 5

25、=5d133 = min2+0, 2=2d333 = min0+0, 0=0d143 = min2+2, 1=1d343 = min0+2, 2=2d213 = min4+6, 2=2d413 = min3+6, 1=1d223 = min4+5, 0=0d423 = min3+5, 2=21d233 = min4+0, 4=41d433 = min3+0, 3=31d243 = min4+2, 3=31d443 = min3+2, 0=0对应的路径仍同上。第四步，由D 3矩阵按上述方法求出D 4矩阵和相应的路径 此时中间点为四个，即m=4，其计算公式为di j 4 = mindi43+d4

26、j3, di j 3其计算结果为di j 4 = mindi43+d4 j3, di j 3中间点di j 4 = mindi43+d4 j3, di j 3中间点d114 = min1+1, 0=0d314 = min2+1, 6=34d124 = min1+2, 1=1d324 = min2+2, 5=44d134 = min1+3, 2=2d334 = min2+3, 0=0d144 = min1+0, 1=1d344 = min2+0, 2=2d214 = min3+1, 2=2d414 = min0+1, 1=1d224 = min3+2, 0=0d424 = min0+2, 2=2

27、1d234 = min3+3, 4=41d434 = min0+3, 3=31d244 = min3+0, 3=31d444 = min0+0, 0=0对应的路径矩阵为 由D 4矩阵可求出网络图中任意两点间的最短距离，并确定所对应的路径。例如，点3到点2之间的的最短距离是4；且由路径矩阵可知，先由第3行第2列对应的4确定由34，再查该矩阵的第4行第2列对应的1确定由41，最后查该矩阵的第1行第2列对应的0确定12可直接到达，因此确定点3到点2之间的的最短路径为3412。三、 最大流问题在实践中除了经常遇到最短路问题以外，还有一类重要问题，也就是求解一个网络系统的最大通过能力问题网络的最大流问题

28、。例如，在通过能力有限的情况下，如何在一定时间内使甲乙两地铁路系统的车流（人员流、物资流）、金融系统的现金流、供水系统的水流、互联网的信息流等达到最大。1. 基本假设和符号含义（1）将出发点称为源点S；终点称为汇点T；其余点称为中间点i； （2）假设源点有无限多的物资、能量、信息及人力等要运出，而汇点则有无限大的仓库来存储这些物资、能量、信息及人力等；（3）假设中间点不存储任何物资、能量、信息等，只起传递作用；（4）由i点到j点的最大传递数量规定为线路的容量，用C(i, j)表示；（5）规定X(i, j)为由i点到j点的实际通过流量。注意：实际支路通过流量X(i, j)等于支路容量C(i, j

29、)，就称为支路饱和。2. 基本定理及其有关概念（1）流量守恒定律根据上述假设，仿照电路中的基尔霍夫定律，可以得到流量守恒定律。如果X(i, j)，jV(i)表示流出i点的总流量，其中V(i)为可直接到达j点的点集合；而X(j, i)，jR (i)表示流入i点的总流量，其中R (i)为可直接到达i点的点集合，由于基尔霍夫定律中流入节点的电流之和与流出节点的电流之和相等的原理，与上述假设中的中间点只起传递作用相似，因此有上式就称为流量守恒方程，式中f表示流量。由假设（4）可知，0X(i, j)C(i, j)，即实际流量为非负且不大于线路的容量，因此，网络最大流问题的数学规划模型为该问题单纯形法可以

30、得到最优解，故最大流问题本质上是线性规划问题，但是当网络较大时，约束方程的数量和变量的个数较多，线性规划模型很大，不便于求解，则利用图的特性可是问题的求解变得容易。（2）割集和割集容量设G是一个连通图，则满足下列条件的边的集合就称为割集： 把这些边全部从图G中去掉，则图G成为不连通的两部分； 把该边集合的任何子集从图G中去掉，则图G仍是连通的。 割集中各支路容量的和称为割集容量。（3）最大流最小割定理 定理：网络中从源点S到汇点T的最大流量就等于把S和T分开的最小割集容量。3. 标记法由最大流最小割定理可知，在求解网络最大流问题时， 可以利用穷举法列出所有将源点S和汇点T分开的割集，并计算其相

31、应的割集容量，从而确定其最小割集容量，即最大流量。这种方法虽然准确，但过于繁琐，因此采用标记法来求解网络最大流问题。标记法的基本思路是：先假设网络各支路中有一个满足流量守恒方程的初始流量，该初始流量就称为“可行流”。选择可行流的方法有两种： 为了计算方便，可将可行流全部选为零，因为零也是符合流量守恒方程的； 为了加快计算速度，通常把可行流选择成使网络中某些主要支路饱和。然后在该可行流的基础上，再试探着对其进行扩充，一次次地试探扩充，直到再也无法扩充为止，这样就找到了该网络的最大流。标记法的求解步骤如下：第一步，先给源点S以标记（-, )，其中“-”表示开始，依据假设条件（1）可知“”表示进入源

32、点S的流量可无穷大，这时源点S成为已标记未检查的点。第二步，用已标记未检查的点i对有联系的未标记的点j进行检查（1）首先检查从已标记点出发的支路 如果初始流量小于最大容量，即X (i, j) 0，则将j点标记为（i-, ( j)），表示i点向j点可以少提供的流量为( j)，实质上也等于j点向i点多提供的流量为( j)，其中( j)表示i点可以少提供的数量和流量中最小的一个，且( j) = min( i), C (j,i)，如图11(b)所示；图11 标记法 当( i) X(S, 2)，则点2应标记(S+, (2)，(2) = min, C(S, 2) -X(S, 2) = min, 6 = 6，所以点2标记(S+, 6)，它表明由S可增加6单位流量到点2。此时，由于C(S, 3) = 9，X(S, 3) = 9为饱和支路；无指向点S的支路，故点S已检查完，成为已标记、已检查的点。点2成为已标记未检查的点，对其进行检查。先看由点2出发的两条支路(2, 4)、(2, 5)，C(2, 5) = X(2, 5)，C(2, 4) = X(2, 4)均为饱和支路；再看