教学材料《运筹学》-第10章

第10章图与网络分析学习目标了解图与网络的概念和特点，掌握求图的最小树、最短路、最大流问题，能够将实际问题转化为图或网络问题加以求解。上一页下一页返回第10章图与网络分析关键词汇图论(GraphTheory)边(Edge)弧(Arc)无向图(UndirectedGraph)有向图(DirectedGraph)树(Tree)最刁、支撑树(TheMinimalSpanningTreeProblem)最短路问题(TheShortestRouteProblem)网络(Network)最大流问题(TheMaximalFlowProblem)中国邮递员问题(ChinesePostmanProblem)上一页下一页返回第10章图与网络分析案例导引例一设有一批货物要从图10-1所示的v1运到v7，每一边上的数字代表该段路线的长度，求最短的运输线路。例二图10-2表示一个水流域的网络，各边(弧)上的数字为最大流量试给定这个水流域网络上的水流方案，使总流量达到最大。案例思考题:(1)分析上面例题的共同特点是什么?提炼问题特征。思考实际中的类似情况和需要解决的有关问题。

(2)对于这类问题，我们关心哪些事情?如何求解?若得到有关信息，我们可以进一步做哪些有益的工作?上一页下一页返回第10章图与网络分析

图论是运筹学的一个重要分枝，对其最早的研究可以追溯到著名的一七桥问题。18世纪，欧洲的哥尼斯堡城(今俄罗斯的加里宁格勒，当时是东普鲁士的首都)有一条流经全城的普雷戈尔河，河的两岸与河中两个小岛及两岛之间有一七座桥彼此相通，图10-3所示。当时人们关心这样的问题，即从陆地A,B,C,D中的任意地方出发，能否通过每座桥一次且仅通过一次，就能返回原出发地。

1736年，瑞士数学家欧拉当时正在圣彼得堡科学院做研究工作，为俄罗斯女皇凯瑟琳服务。欧拉将这个问题抽象化，用含有四个点七条边的图形表示此问题，如图10-4所示。在解决该问题的过程中，欧拉创立了一个数学分枝，即后来人们所熟知的拓扑学。拓扑学后来在19世纪形成了一门数学分枝，它属于几何学的范畴。拓扑学作为几何学的一个分枝，又和通常的平面几何、立体几何上一页下一页返回第10章图与网络分析

有所不同。通常的平面几何或立体几何研究的对象是点、线、面之间的位置关系以及它们的度量性质。拓扑学的研究与研究对象的长短、大小、面积、体积等度量性质和数量关系都无关。举例来说，在通常的平面几何里，把平面上的一个图形搬到另一个图形上，如果完全重合，那么这两个图形叫做全等形。但是，在拓扑学里全等的概念已经变化，拓扑学研究的图形，在运动中，它的大小或者形状都可以发生变化。在拓扑学里没有不能弯曲的元素，每一个图形的大小、形状都可以改变。例如，前面讲的欧拉在解决哥尼斯堡七桥问题的时候，他画的图形就不考虑它的大小、形状，仅考虑点和线的个数及它们之间的连接关系，这些就是拓扑学思考问题的出发点。在拓扑学里更关注的是拓扑等价的概念。比如，尽管圆和方形、三角形的形状、大小不同，在拓扑变换下，它们都是等价图形，也就是说从拓扑学的角度看，它们是完全一样的。上一页下一页返回第10章图与网络分析

拓扑学主要研究拓扑空间在拓扑变换下的不变性质和不变量。拓扑学经常被描述成“橡皮泥的几何”，就是说它研究有形的物体在连续变形下不变的性质。有关拓扑学的一些内容早在18世纪就出现了，那时候发现的一些孤立的问题后来在拓扑学的形成中占有重要地位。在数学上，关于哥尼斯堡七桥问题、多面体的欧拉定理、四色问题等都是拓扑学发展史上的重要问题。欧拉在解哥尼斯堡一七桥问题时，采用了今天被人们称为网络的拓扑学知识，运用网络，欧拉证明了要走过哥尼斯堡的一七座桥且每桥只通过一次是不可能的。欧拉发表了一篇论文，证明一七桥问题不能实施一笔画，也就是说上述猜想不能成立，从而结束了人们的争论，因此欧拉被视为图论的奠基人。上一页下一页返回第10章图与网络分析1840年，莫贝斯提出著名的四色猜想问题，即一幅地图只要用四种不同的颜色着色，就可以使互相接壤的国家区分开来。此问题直到1976年才由美国学者Appel.Haken在伊利诺斯大学用当时的三台超大型计算机做了近200亿个逻辑判断，花费1200个机时才得以证明。

1859年，汉密尔顿提出，正十二面体中的20个角分别表示20个城市，从某城市出发，访遍所有城市，且仅访问一次，能否返回出发地的问题，此问题至今仍未得到完全解决。随着科技发展，人们提出了许多需用图论加以解决的问题，使图论得到飞速发展。目前，图论已经成为解决管理科学、系统科学、运筹学和信息论等自然与社会科学问题的有力工具。上一页返回下一页10.1图的基本概念10.1.1图论中的图在实际问题中，人们常用图来表示所研究的对象及这些研究对象之间某种特定的关系。

图10-5中表示了A,B,C,D,E这5个城镇的相对位置以及连接它们的公路网。在图中，点和线的位置是按照对图研究方便的原则而随意确定的，点的位置并不是实际的地理位置，边的形状不是实际路线形状，边的长度也不是严格地按实际比例绘出的，人们所关心的只是图中存在多少个点，这些点有多少边，它们的连接形式如何。因此，图论中所说的图与几何图形、函数图像以及机械制图中的图是完全不同的。抛开各种图所代表的实际内涵，可以发现组成图的基本要素是一些点和连接这些点的线。下一页返回上一页10.1图的基本概念1)基本概念定义(1)图。设 是n个元素的非空集合， 是m,个元素的集合若对于任一ej∈E，均有vs，vt

∈V与之对应，则称VUE为图，记为G=(V,E)。(2)顶点、边、端点、关联边、邻接点。在G中，称vi为G的顶点，ej为G的边，并记为 称vs，vt是ej的端点，ej是vs，vt关联的边，称vs，vt为邻接的点。把图10一6用数学定义描述为:G=(V,E)，且上一页下一页返回10.1图的基本概念

(3)环、多重边、简单图。如果图中某一边的两个端点相同，则称为环，如图10-6中的e3。如果图中两边(或多边)具有相同的一对端点，则称为多重边(或平行边)，如图10-6中的e7,e8

。无环和无多重边的图称为简单图。我们所讨论的都是简单图。注意:两个图的形状看似不同，但如果它们的顶点集、边集以及边与点的关系一一对应，则可视为同一个图。

(4)次、孤立点、奇点、偶点、悬挂点、悬挂边。上一页下一页返回10.1图的基本概念

与顶点v相关联的边数称为v的次数，记为d(v)，图10-6中d(v1)=1,d(v2)=5,d(v3)=4,d(v4)=3,d(v5)=3,d(v6)=0。次数为零的点称为孤立点，如v6；次数为奇数的点称为奇点，如图10-6中的:v1，v2，v4

，v5;次数为偶数的点称为偶点，如图10-6中的:v3，v6;次数为1的点为悬挂点，如图10-6中的v1，;与悬挂点关联的边称为悬挂边，如图10-6中的e1。定理10.1任一图中顶点次数之和等于边数的二倍，即定理10.2任一图中奇点的个数必为偶数。

(5)链、初等链、简单链。在图‘中，从一个顶点出发，经过边、点、边、点、…，最后到达某一点，称为G中的一条链，用经过这条链的顶点或边表示。图10-7中的(v1，v2，v3，v4

，v5，v6）是一条链，也可表示为(e1，e3，e4，e7)。上一页下一页返回10.1图的基本概念若链中的顶点均是不同的，则称为初等链;若链中所含的边均不相同，则称为简单链。目前，我们只讨论无重复边的链，即简单链，简单链也称为通路，简称路。(6)圈、初等圈、简单圈。链(v1，v2，…，vn）中，若v1=vn，则称此链为一个圈。若圈中的点(v1，v2，…，vn-1）都是不同的，则称为初等圈;若圈中所含的边均不相同，则称为简单圈。

(7)连通图、不连通图、子图。在一个图中，若任意两点之间至少存在一条链，则称该图为连通图，否则为不连通图，图10-7就不是连通图。我们仅讨论连通图。若有图G=(V,E)，取其全部或部分顶点V1,V, ，再取其全部或部分边E1, ，这里V1非空，且E1中的边的端点都在V1中，则称图G1=(V1，E1)为图G的子图。上一页下一页返回10.1图的基本概念2)有向图上述讨论的图是没有方向的，即ej=(vs，vt)=(vt

，vs)。事实上，许多实际问题用无向图无法描述，例如交通图中的单行道，一项工程各工序间的先后次序关系等，所以需要用有向图描述。定义:设V={v1,v2,…,vn}是n个元素的非空集合，A={a1,a2,…,an}是m,个元素的集合，若对于任一aj∈A,均有有序对(vs，vt)与之对应，则称VUA为有向图，记为D=(V,A)。称vi为顶点，aj为弧，记为a=(vs，vt)，在不至于混淆时也称为边。在有向图10-8中:上一页下一页返回10.1图的基本概念

在有向图D中，从一个顶点出发，顺着弧的方向，经过弧、点、弧、点、一最后到达某一点，称为D中的一条单向链或通路，简称路，用经过这条单向链的顶点(或弧)表示，如图10-8中(v1，a1，v2，a5，v5，a8，v4)是一条单向链，也可以简单表示为(v1，v2，v5，v4)或(a1，a5，a8)。在有向图中，顶点的次数分为入次d(vi)-和出次d(vi)+，入次是以该顶点为终点的边数，出次是以该顶点为起点的边数。如图108中 。

3)赋权图如果对于给定的图‘=(V,E)的任意一边e∈E，有一实数W(e)与之对应，则称‘为赋权图，称W(e)为边e的权。图10-9表示的是一个赋权图，其中 ，并把权数标示于该边上。

上一页下一页返回10.1图的基本概念

赋权图的应用比较广泛，如交通图中，权数可以是两点之间的距离，也可以是两地之间的单位运费、运能等，工程网络图中，权数代表工序的时间。本章所讨论的图中，绝大多数为赋权图。设在赋权图中存在一条通路，则通路上所有边的权数之和称为这条通路的权。对于一个有向图也可以定义权数使之成为有向赋权图。一个连通图连同定义在其边集上的实函数W(e)一起称为一个网络。若一个网络的每条边均有方向，称为有向网络;每一条边均无方向，称为无向网络;若有些边有向，另一些边无向，则称为混合网络。下面所讨论的各种算法可以适用于以上各种网络。上一页下一页返回10.1图的基本概念10.1.2图的矩阵描述随着实际问题的大型化，多数算法必须在计算机上实现，但是计算机在直接处理图形方面是有困难的，必须寻求另外的解决方法，矩阵化图形是一个有效途径。

1)无权图的邻接矩阵表示在图10-10中两顶点之间有边相连的记为1，无边相连的记为n，对角线位置数据记为n，这样就得到无权图的邻接矩阵(如图10-10所示)，该矩阵一定是对称矩阵。上一页下一页返回10.1图的基本概念2)赋权无向图的邻接矩阵表示在图10-11中，两顶点之间有边相连的，写上它们的权数，无边相连的记为∞，对角线上的数值仍然为0。如权数代表两点之间的距离，则∞表示此两点之间是不通的。赋权无向图对应的矩阵也是对称的。

3)赋权有向图的邻接矩阵表示

图10-12中，矩阵左侧第一列为各条弧的起点，在每一行中，以该点为起点，按弧的方向依次填上到各点的权数，如果不存在到该点的弧，则权数为∞，如此得到的矩阵往往不是对称矩阵。思考题(1)有向图和无向图有什么区别?熟悉图论中常用的概念和术语。(2)可以描述图的矩阵有哪些?它们各有什么特点?如何构造和应用?上一页返回下一页10.2最短路问题

最短路问题就是在一个网络中，给定一个起点，要求找出其到另一点的且权数最小的通路。最短路问题是网络分析中最重要的最优化问题之一。最短路问题在实际分析中有广泛的应用，如管道铺设、运输线路选择、工厂布局等。有些问题看起来似乎与地理方位无关，但通过适当的转化也可将其归结为最短路问题，如设备更新问题。我们可以将时点看成是网络图中的点，相关可采取的方案作为边，该方案的相关成本视为权数，则可把设备更新问题化成最短路问题。下面介绍求解网络最短路问题的标号算法和矩阵算法，这些方法适用于任何性质的网络。下一页返回上一页10.2最短路问题10.2.1最短路的标号算法最短路的标号算法是由E.D.Dijkstra于1959年提出的，是目前公认的求解最短路问题的较好算法，但此种算法要求图中边的权、,0。其思路是:从起点到终点往往存在许多不同的通路，可经过各个不同的中间点，情况比较复杂。Dijkstra算法在计算过程中，把所有的计算局限在关联边，即直接计算相关两点的边，这样就把一个比较复杂的运算转化为一系列简单的运算。过程如下(如图10-13所示):(1)从起点出发，依次寻找与起点距离最近的相邻点，并以此最短距离作为该点的标号，每次寻找一个点。上一页下一页返回10.2最短路问题(2)若已经计算出起点到若干点S={v1，v2，…，vi}的最短距离，在找下一点时，要充分考虑到与S集合中的点的每一邻接点的可能，也就是说要考虑S集合中的每一点到其他点的距离，从中选出最短距离点。

(3)重复上述过程，直到终点的标号被找到，则终止计算，找出最短路。如果要找起点到其他每一点的最短路，则必须计算到所有点的标号均找到为止。例10.1设有一批货物要从v1运到v7，每一边上的数字代表该段路线的长度，求最短的运输线路。上一页下一页返回10.2最短路问题

解给起点:，标号为0，记为d(v1)=0，用以表示v1是起点。建立集合S={v1}下面依次寻找到:，距离最短的点(此过程也可称为迭代)。第一步:找出与S={v1}中点直接相关联的边，也就是邻接点，并计算出它们(关联边)到点v1的距离。与v1相关联的边有两条e(v1

，v2)，e(v1

，v3)，邻接点v2，v3到v1的距离为取上述两者之中的最小值，即对应的相邻点为v2

，说明除v1点之外，v2是v1到其他与之邻接的点中距离的最短者，则v2进人S,S={v1，v2}，记v2的标号为d(v2)=1，并在图上标出，把边e(v1，v2)加粗(如图10-14所示)，用以表示v1到v2的最短距离是经过e(v1，v2)实现的。上一页下一页返回10.2最短路问题

第二步:找出与S={v1，v2}中点直接相关联的边。与v1相连的边有两条:e(v1

，v3)和e(v1

，v2)，(注意:e(v1

，v2)已经加粗，v2已经进入S，故不再考虑。一般情况下考虑的边必须是一端的点在S集，另一端的点不在S集)，故只考虑e(v1

，v3)。与v2相关联的边有4条，即e(v2

，v3)，e(v2

，v4)，e(v2

，v5)，e(v2

，v6)分别计算v1到相关各点的距离，得上一页下一页返回10.2最短路问题取上述值中最小的，即对应的点为v3

，说明除了S集内的点即:v1、v2点，v1到其他各点的距离中，到v3的距离最短，为3，则v3点进入S,S={v1，v2，v3}，v3的标号d(v3)=3。由于k23=3，可知此时的最短路是经过v2的，将边e(v2

，v3)加粗，如图10-15所示。第三步:找出与S={v1，v2，v3}中点直接相关联的边，与v1相关联的边(相邻点不包括已在S集内的点)已经不存在，与v2相连接的边(相邻点不包括已在S集内的点)为e(v2

，v4)、e(v2

，v5)、e(v2

，v6)，与v3相连接的边为e(v3

，v6)，分别计算相关各点的距离，得上一页下一页返回10.2最短路问题取上述数值中最小值，即上一页下一页返回10.2最短路问题对应的点为v6，说明除了S集内的点，v1到其他各点的距离中，到v6的距离最短，为4，则v6进入S集，S={v1，v2，v3，v6}，v6

的标号为d(v6)=4。由于k36=4，可知，此时由v1到v6的最短路是经过v3的，将边e(v3

，v6)加粗，如图10-16所示。第四步:找出与S={v1，v2，v3，v6}中点直接相关联的边，与v1相关联的边(相邻点不包括已在S集内的点)已经不存在，与v2相关联的边(相邻点不包括已在万集内的点)为e(v2，v4)，e(v2，v5)与v3相关联的边(相邻点不包括已在S集内的点)已不存在，与v6相关联的边(相邻点不包括已在S集内的点)为e(v6，v5),e(v6，v7),分别计算相关各点的距离，得上一页下一页返回10.2最短路问题取上述数值中最小值，即上一页下一页返回10.2最短路问题对应的点为v4，说明除了S集内的点，v1到其他各点的距离中，到v4的距离最短，为5，则v4进入S集，S={v1，v2，v3，v6，v7}，v4

的标号为d(v4)=5。由于k24=5，可知，此时由v1到v4的最短路是经过v2的，将边e(v2，v4)加粗，如图10-17所示。第五步:找出与S={v1，v2，v3，v6，v4}中点直接相关联的边，与v1相关联的边(相邻点不包括已在S集内的点)已经不存在，与v2相关联的边(相邻点不包括已在S集内的点)为e(v2，v5)，与v3相关联的边(相邻点不包括已在S集内的点)已不存在，与v6相关联的边(相邻点不包括已在S集内的点)为e(v6，v5),e(v6，v7),分别计算相关各点的距离，得上一页下一页返回10.2最短路问题取上述数值中最小值，即上一页下一页返回10.2最短路问题对应的点为v5，说明除了S集内的点，v1到其他各点的距离中，到v5的距离最短，为7，则v5进入S集，S={v1，v2，v3，v6，v7，，v5}，v5的标号为d(v5)=7。由于k65=k45=7，可知，此时由v1到v5的最短路是经过v4和v6的，将边e(v4，v5)和e(v6，v5)同时加粗，如图10-18所示。第六步:与S={v1，v2，v3，v6，v4，v5}内的点相关联的S集外的边只有两条，其参数计算为上一页下一页返回10.2最短路问题最小值为9，则v7进人S集,S={v1，v2，v3，v6，v4，v5，v7}，v7的标号为d(v7)=9，因为k57=9，说明由v1到v7的最短距离是通过v5实现的，将e(v5，v7)加粗。由于v7是终点且已经进入集合S，故已经求得v1到v7的最短路，距离为9。从v1点开始，沿加粗的边一直通往v7的路即为最短路。本题中共有两条最短路，分别是:和如图10-19所示。上一页下一页返回10.2最短路问题10.2.2最短路的矩阵算法最短路的矩阵算法是将图表达成矩阵形式，然后用矩阵表计算出最短路。矩阵算法的原理与标号算法完全相同，只是采用的形式不同，矩阵算法更为简洁，特别有利于计算机处理。矩阵算法的步骤为:(1)将图表示成矩阵形式。

(2)确定起点行，将其标号确定为0，将相应的列在矩阵表中划去。

(3)在已经标号的行中未划去的元素中，找出最小元素aij，把它圈起来，此时把第j列划去，同时给第j行标号aij

，并把第j行中未划去的各元素都加上aij

，注意标号的含义同标号算法一样。上一页下一页返回10.2最短路问题(4)若还存在某些行未标号，则返回上一步骤，如果各行均已获得标号(或终点行已经获得标号)则终止计算，并利用反向追踪，求得自起点到各点的最短路。例10.2仍以例10.1为例，求解最短路。解先将图10-13表示成矩阵形式，并将第一行起点标号0，划去第一列得上一页下一页返回10.2最短路问题上一页下一页返回10.2最短路问题

第一步:

在标号的第一行中，找出最小元素a12=1，将其圈出，并将其所在的第二列划去，给第二行标号1，第二行未划去的元素均加上1，得上一页下一页返回10.2最短路问题上一页下一页返回10.2最短路问题

第二步:

在已经标号的第一行、第二行未划去元素中找出最小元素a23=3，将其圈出，并将其所在的第三列划去，给第三行标号3，第三行未划去的元素均加上3，得上一页下一页返回10.2最短路问题上一页下一页返回10.2最短路问题

第三步:

在已标出标号的第一、第二、第三行未划去的元素中，找出最小的元素a36=4，将其圈出，并将其所在的第六列划去，给第六行标号4，第六行未划去的元素均加上4，得上一页下一页返回10.2最短路问题上一页下一页返回10.2最短路问题

第四步:

在已标出标号的第一、第二、第三、第六行未划去的元素中，找出最小的元素a24=5将其圈出，并将其所在的第四列划去，给第四行标号5，第四行未划去的元素均加上5，得上一页下一页返回10.2最短路问题上一页下一页返回10.2最短路问题

第五步:

在已标出标号的第一、第二、第三、第四、第六行未划去的元素中，找出最小的元素a45=a65=7，将这两个数都圈出，并将其所在的第五列划去，给第五行标号7，第五行未划去的元素均加上7。注意:如果最小元素有两个或两个以上，且不在同一列，则将所有含最小元素的列划去，给相应的行标号，并将未划去的该相应行元素均加上此最小元素，也就是独立地做完各个过程，得上一页下一页返回10.2最短路问题上一页下一页返回10.2最短路问题

第六步:

在已标出标号的第一、第二、第三、第四、第五、第六行未划去的元素中，找出最小的元素a57=9，将其圈出，并将其所在的第一七列划去，给第七行标号9，由于终点v7已得标号9，故从v1到v7的最短距离为9。如下面矩阵所示。第七步:

逆推寻找从v1到v7的最短路径。上一页下一页返回10.2最短路问题上一页下一页返回10.2最短路问题

在上面的矩阵中，在终点v7所在列中，圈起来的数9在第五行，即v7前面的连接点为v5，v5所在列中圈起来的数值7有两个，说明v5前面有两个分枝，现任取其中一个，如第四行，则v5在此分枝上前方的点为v4，v4所在列中圈起来的数值5位于第二行，则v4前面的连接点为v2，v2所在列中圈起来的数值1位于第一行，则v2前面的连接点为v1，v1即起点。故可以找到一条v1到v7的最短路径为类似地，从另一个分枝逆推，则可找出另一条最短路为上一页下一页返回10.2最短路问题

例10.3某公司在最近五年需要使用一种设备，购买和维修该设备的费用见表10-1和表10-2，问:采用怎样的使用策略可使总费用最低。分析构造设备更新的有向图，其中包含六个顶点v1，v2，v3，v4，v5，v6，分别代表第一年年初到第五年年末共6个不同时刻，从顶点vi(i=1，2，…，5)分别引出至终点为vi+1，vi+2，…，v6的有向边，边的权重等于从起点时刻购买设备并用到终点时刻所需的购买费用和维护费用的总和。上一页下一页返回10.2最短路问题

在图10-20中，从v1到v6的一条通路就代表一种设备使用策略，如P1=(v1，v2，v3，v4，v5，v6)表示在第1、第2、第3、第4、第5年年初购买设备，每台设备只用一年，而W(P1)=1290是实行这种策略的总费用;又如P2(v1，v3，v6)表示第1年年初购买设备，使用到第3年年初，更换新设备用到第5年年末，W(P2)=940是这种策略的费用。要寻求费用最小的设备使用策略，只要找出有向图10-20中v1到v6

的最短路即可。思考题(1)试述Diikstra算法的关键步骤(2)这里最短路径问题与动态规划中讲的最短路径问题的共同点和不同点是什么?上一页返回下一页10.3最小树问题10.3.1树、最小树的定义及性质(1)树的定义。在无向图G中的链(v1，v2，…，vn)中，若v1=vn，若圈中的点(v1，v2，…，vn-1)，都是不同的，则称为初等圈。在图论中，称无圈的连通图为树，如六个城镇v1，v2，v3

，v4，v5，v6的一个通讯网络(如图10-21所示)是一棵树。

(2)树的重要性质。①树中任意两点之间有且仅有一条通路。所以从树中任意去掉一边即成为不连通图。也就是说，在具有相同顶点的连通图中，树是边数最少的。②树中是没有圈的，在树的任意两点之间加上一条边就会生成圈，所以树也是具有相同顶点的无圈图中边数最多的。③树的顶点与边数之间的关系为:m=n-1，即边数=顶点数-1。下一页返回上一页10.3最小树问题(3)生成树、最小生成树。在一个连通图G中，如果保留全部顶点，并选择适当的边构成一个新的图，并使这个图是树，则称它为图‘的生成树。生成树中各边的权数之和称为该生成树的权。具有最小权数的生成树称为最优树或最小生成树。我们所说的最小树问题，就是指在一个连通赋权图中(网络)，寻找具有最小权数的生成树。许多问题可以归结为求最小生成树问题。例如，在资源有限的情况下，如何修筑一些公路把若干个城市连接起来，如何架设通讯网络将若干个需要通话的点连接起来，如何修筑渠道将水源和若干待灌溉土地连通起来使资源消耗最低等。上一页下一页返回10.3最小树问题10.3.2最小生成树的求解求最小生成树的方法很多，我们介绍“破圈法”和“避圈法”。例10.4某电话公司计划在六个村庄架设电话线，各村庄之间的距离如图10-22所示，找出使电缆总长度最小的铺设方案。分析要求电缆总长度最小的铺设方案，实际上要求出图10-22的最小生成树。解方法1:破圈法。破圈法的基本思想就是在图中找圈，找到一个圈后，将组成该圈的各边中权数最大的边舍去，破除这个圈，然后再寻找下一个圈，一直重复此过程，直到图中不含圈为止，即得到最小树。上一页下一页返回10.3最小树问题(1)选圈:v1→v3

→v4→v1

，去掉权数最大的边e(v1，v4)得到图10-23中的(1)图。

(2)选圈:v1→v3

→v4→v2→v1

，去掉权数最大的边e(v1，v2)得到图10-23中的(2)图。

(3)选圈:v3

→v4→v6→v3

，去掉权数最大的边e(v4，v6)得到图10-23中的(3)图。

(4)选圈:v3

→v4→v5→

v6→v3，去掉权数最大的边e(v3，v6)得到图10-23中的(4)图。

(5)选圈:v2

→v4→v5→v2，去掉权数最大的边e(v2，v5)得到图10-23中的(5)图。经过上述过程，图中已经不含圈，剩下的边和顶点构成了原网络的最小生成树，此时的电缆铺设方案为最优方案。上一页下一页返回10.3最小树问题最小树的权为:1+2+2+1+2=8。方法2：避圈法。避圈法的基本思想与破圈法相反，避圈法先将所有的边按权数由小到大(或由大到小)递增(或递减)排列，然后按权数由小到大依次进行检查，如果某条边加到图上不会产生圈，则将其加到图上，反之则舍去，直到所有边均检验完毕，即可得到最小生成树。将题中各边按权数由小到大排列，为:上一页下一页返回10.3最小树问题

先取e(v1,v3)，e(v4,v5);

判断e(v3,v4)与先取的两边不生成圈，则将e(v3,v4)加入图中;

判断e(v2,v4)与先取的边不生成圈，则将e(v2,v4)加入图中;

判断e(v5,v6)与先取的边不生成圈，则将e(v5,v6)加入图中;

判断e(v1,v2)与先取的边生成圈，v1→v3

→v4→v2→v1

，故舍去;

重复此过程直到所有的边均被检验，最后得到最小生成树，过程如图10-24所示，权数为8，结果与用破圈法求解的结果完全相同。思考题(1)符合哪些条件的图才可以称之为树?(2)避圈法和破圈法求解最小支撑树可以得到相同的结果吗?这两种方法有什么区别?(3)每一个图都有支撑数吗?最小支撑数是唯一的吗?上一页返回下一页10.4最大流问题10.4.1最大流的基本知识给定一个有向图D=(V,A)，如果对于每一条弧a=(vi，vj)∈A，均有一个非负实数c(a)∈C与之对应，称c(a)为弧a的容量;V中给定一个顶点x为源(发点)，另一个顶点y为汇(收点)，其余顶点为中间顶点，则称这个图为容量网络，记为N=(V,A,C，x，y)。容量网络有广泛的实际背景，如以源二表示某种物资的产地，汇y表示该物资的销地，中间顶点是物资的中转站，网络图中的有向弧(vi，vj)表示运输线路，容量。表示该运输线路的最大运输能力，此时容量网络代表运送该物资的运输网络，典型的如铁路运输。鉴于这种实际背景，有时也称容量网络为运输网络，简称网络。

图10-25表示一个网络，弧上的数字为容量c(a)。下一页返回上一页10.4最大流问题

对于给定运输网络上的一个运输方案称为运输网络的一个网络流，图10-26所示网络上的一个网络流如图10-26所示。在图10-26中，弧上的数字前一个为容量cij，括号内的数字表示特定运输方案沿该弧运输货物的数量fij。显然，对于任意弧的运输量不能超过容量，即关fij≤cij

。由于中间顶点vk是中转站，所以进入的货物量 应该等于流出的货物量 ，而从源x运出的货物应该等于汇y收到的货物，就是该运输方案运送货物的总量，称为网络流的流量，记为Vf，图10-26中网络流的流量Vf=6。一般地，如果在网络N=(V,A,C，x，y)中，定义在弧集A上的一个函数f满足:上一页下一页返回10.4最大流问题(1)对于任一条弧 。(2)对于中间顶点vk，存在 。(3)对于源x和汇y，存在则称f为N的一个网络流，简称流，称V,为f的流量。对于给定的运输网络，一个十分实际的问题是如何求得流量最大的网络流，简称最大流。上一页下一页返回10.4最大流问题10.4.2最大流的标号算法设P是从源二到汇y的一条链，定义P的方向是从x到y。称P上与P同向的弧为前向弧，记前向弧的集合为P+，称P上与P反向的弧为反向弧，记反向弧的集合为P-。设P是网络N中从源x到汇y的一条链，f是N的一个网络流，若对于任一a∈P+(a为前向弧),f(a)<c(a),对于任一a∈P-为反向弧)，f(a)>0，则称P是网络N中关于流f的一条增广链。如果P是网络N中关于流f的一条增广链，可以采用如下方法改进流f使流量Vf增大。令上一页下一页返回10.4最大流问题作可以验证，所得到的f一定仍然满足网络流的三个条件，所以f仍然为N中的网络流，而 ，流量增大。下面通过实际例子说明这种改进的实际意义。例10.5图10-27给出网络N和它的一个网络流f,弧上数字是c(a)，括号中的数字是f(a)，寻求增广链，并改进流。上一页下一页返回10.4最大流问题解找出P1=(x，v2，v4，y)为关于流f的一条增广链，因为P1上所有弧均为前向弧，即a∈P+，且满足f(a)<c(a)，所以这表示可以在P1的各个弧上增加一个单位流量，修改后的网络流如图10-28所示，此时流量从5增加到6，流量增加。现在考虑P2=(x，v3，v2，v4，y)，因为P2+={(x，v3),(v2，v4)=(v4，y)},其中的前向弧均满足f(a)<c(a)，P2-={(v2，v3)}，且反向弧满足f(v2，v3)=2>o，所以P2是关于流f的一条增广链，则修改后的网络流量如图10-29所示，网络流量增加到8。上一页下一页返回10.4最大流问题

这种改进的实际意义在于将沿反向弧(v2，v3)送到顶点v3的2个单位运输量转移到还有潜力的弧(v2，v4)、(v4，y)户上，通过它们送到y，这样把(v2，v3)节省下来的2个单位输送量增加在弧(x，v3)上，从而使总输送量加大2个单位。这种改进的实质是通过不断调整增大网络流量。通过以上分析可知，只要网络中存在关于流f的增广链，就可以通过改进流f使网络总流量增大。如此，如何寻找增广链是关键问题，我们可以采用逐步构造顶点集万的方法来求得从x到y的增广链。上一页下一页返回10.4最大流问题

其思想是:开始时令S={x}，记 ，若 (前向弧)，则将vj吸纳入S若 (注意是反向弧)，则也将vj吸纳入S。如果最后y进入S，则从构造万的方法可知必定存在从二到)的增广链。如果最后y不能进入S，则 ，并且无法再从 向 方向增加运输量，所以此时的f就是网络的最大流。总结上述思想归纳网络最大流标号算法如下。

(1)给出初始流(可以给出初始流f=0)。(2)令l(x)=+∞,表示x是源，能够得到任意多的流量,上一页下一页返回10.4最大流问题(3)考察S-B中的顶点u:

若 ，前向弧(u,v)满足f(u,v}<c(u,v)，给顶点v标号 ，其中 ,并将v吸纳人S。若 ，前向弧(u,v)满足(注意是反向弧)满足f(v，u)>0，给顶点v标号 ，其中 ,并将v吸纳人S。

(4)若对所有 ，前向弧(u,v)和反向弧(u,v)均检查完毕，将检查完的顶点u并入已查视顶点集B，转步骤(3)。

(5)若y进入S，则必然存在从x到y的增广链P，利用y标号的第一部分可以找到P中y的紧前顶点u，利用y标号的第二部分可以知道P中从u到y的这一段是前向弧(+)，还是反向弧(一)，类似可以找到P中u的紧前顶点。通过上述追踪可以得到增广链P，而y标号的第三部分l(y)即为该增广链的θ值，令θ=l(y)，做:上一页下一页返回10.4最大流问题

，转步骤(2)。(6)若 ，y不能进人S，则厂已是网络最大流。上一页下一页返回10.4最大流问题

例10.6用最大流标号算法求解图10-27所示网络的最大流。解先为网络分配一个初始流，初始流f=5。(可以设定初始流为0，在此基础上进行流的分配与调整)

第一次迭代:①寻找增广链。为源点x标记l(x)=[∞]，表示x是源点，能够得到任意多的流量，建立集合(x，v2)是一个S到的非饱和弧, ,因此v2可标号，为其标号为 ，其中上一页下一页返回10.4最大流问题即v2标号为 。修改 。(x，v3)是一个S到的非饱和弧, ,因此v3可

标号，为其标号为 ，其中即v3标号为 。修改 。由于S中的点v2到中的点v4的弧(v2,v4)为非饱和弧(其余S中的点到中的点直接相连的弧均为饱和弧，不能进行标号)， ,因此v4可标号，为其标号为 ，其中上一页下一页返回10.4最大流问题即v4标号为 。修改 。由于汇点y已经标号，因此可以找到一条增广链，x→v2→v4→y。上述过程绘图如下(见图10-30)。②在此增广链上调整流量。由于y标号为 ，即l(y)=1为该增广链的θ值，作:即在增广链上的正向弧上加θ

，反向弧上减θ

，故:上一页下一页返回10.4最大流问题增广链上无反向弧，调整完毕，得到新的可行流图如图10-31所示。第二次迭代:①寻找增广链。为源点x标记l(x)=[∞]，则(x，v3)是一个S到的非饱和弧(其余S中的点到中的点直接相连的弧均为饱和弧，不能进行标号)， ,因此v3可标号，为其标号为 ,其中:即v3标号为: 。修改 。上一页下一页返回10.4最大流问题(v2，v3)是一个S到的非饱和弧(其余S中的点到中的点直接相连的弧均为饱和弧，不能进行标号)，而 ,因此v2可

标号，为其标号为: 。其中 即v2标号为: 。修改 。由于S中的点v2到中的点v4的弧(v2，v4)为非饱和弧(其余S中的点到中的点直接相连的弧均为饱和弧，不能进行标号),

因此v4可标号，为其容标号为 ，其中:上一页下一页返回10.4最大流问题即v4标号为: 。修改 。由于S中的点v4到中的点y的弧(v4，y)为非饱和弧， 。因此y可标号，为其标号为 ，其中:即y标号为: 。修改 。由于汇点y已经标号，因此可以找到一条增广链，x→v3→v2→v4→y。上述过程绘图如图10-32所示。上一页下一页返回10.4最大流问题其中(v2，v3)为反向弧，其余均为前向弧。②在此增广链上调整流量。

θ=l(y)=2，作:即在增广链上的前向弧上加θ

，反向弧上减，故:调整完毕，得到新的可行流图为图10-33所示。上一页下一页返回10.4最大流问题

第三次迭代:

寻找增广链。为源点x标记l(x)=[∞]，则 。

(x，v3)是一个S到的非饱和弧(其余S中的点到中的点直接相连的弧均为饱和弧，不能进行标号)， ，因此v3可标号，为其标号为 其中即v3标号为: 。修改 。上一页下一页返回10.4最大流问题(v2，v3)是一个S到的非饱和反向弧(其余S中的点到中的点直接相连的弧均为饱和弧，不能进行标号)，而 ，不满足f(v，

u)>0条件，因此v2不能标号，S={x，v3}不能再扩大，则图10-33所示的网络流即为最大流。思考题(1)网络可行流具备哪些特点?(2)如何找到一个网络的可行流?(3)试述网络最大流的求解过程上一页返回下一页10.5推销员及中国邮路问题10.5.1推销员问题一个推销商到n个城市开拓市场推销产品，他从n个城市v1，v2，…，vn中的某个城市vi出发，遍历其他所有城市且每个城市只到一次，最后回到:，这个推销商如何安排他的商业营销线路计划使总的路程距离最短，这就是推销员问题，也被称为货郎担问题。对一个图G(V,E)而言，若一个回路H过每个点且仅过一次，则称H是图G(V,E)的一个Hamilton回路。我们已经知道，与顶点v相关联的边数称为v的次数，记为d(v)，次数为奇数的点称为奇点，次数为偶数的点称为偶点。若图G(V,E)中，任意两个顶点vi

、vj满足:下一页返回上一页10.5推销员及中国邮路问题则图G(V,E)中存在Hamilton回路。商品推销员所要选择行走的路线就是一个由n个城市构成的一个Hamilton回路。下面介绍一种寻求一个满意的(不一定为最优)的Hamilton回路的方法。例10.7某校园开设小巴交通线，教学地点和学生宿舍的分布如图10一34所示，其中有两条为单行线，图中的权数表示通过路径的时间，现需寻找一条最优路径，即使得小巴通过每个教学点和宿舍楼一次的时间最少的线路。解可以验证，图10-33存在Hamilton回路。

(1)把教学地点和学生宿舍抽象为图中的点，将图10-34转化为矩阵描述，但要注意，为避免直接出现:井:的回路，描述中把本点到本点的权数设为∞。上一页下一页返回10.5推销员及中国邮路问题(2)类似采用匈牙利法处理指派问题矩阵的方法，即在矩阵的每行每列中均减去该行或该列中的最小元素，使矩阵中的每行每列均出现0元素。上一页下一页返回10.5推销员及中国邮路问题(3)采用紧邻推断法(NearestNeighborHeuristic)在C1中找出一条初始Hamilton回路H1。上一页下一页返回10.5推销员及中国邮路问题起始可以选择任意点，比如选择:，作为起点，然后从C1中选择距离v1最近的点，在C1矩阵中的v1行数据中，最小的数值为0，位于第二列，说明距离v1最近的点为v2，所以选择v2作为v1的接续点，按此方法继续寻求，依次选择v3、v6、v5、v4、v1，由此找到一条初始Hamilton回路H1={v1，v2，v3，v6，v5，v4，v1}，该回路的路径长度为:(4)修正回路H1。在矩阵C1中，已经选择 作为初始Hamilton回路H1的第一步，故从C1中割掉第一行以及第二列，得到新矩阵C2，同时，为避免出现 回路，令矩阵C2中的元素c21=∞。为保证矩阵C2中的每行每列均有0元素，矩阵的第一行元素减去1，第一列元素减去0.3，得到矩阵C3。上一页下一页返回10.5推销员及中国邮路问题

在矩阵C3中采用紧邻推断法，从v2出发寻找一条终点为v1，的Hamilton回路。从v2出发的下一个选择应该是v3，从C3可以看出，终点v1的前一点不能是v5或v6，所以v3的下一个选择不能是v4，只能是v5或v6

，如果依次选择:v3→v5→v6

，则无法构成Hamilton回路;如果依次选择:v3→v6→v5→v4→v1

，则构成的回路与H1相同，无法改进。上一页下一页返回10.5推销员及中国邮路问题综上所述，在矩阵C3中采用紧邻推断法，从v2出发的下一个选择应该是v6，依次选取可寻找到一个新的Hamilton回路H2={v1，v2，v6，v5，v3，v4，v1}，该回路的路径长度为:(5)重复(4)步骤，去掉C3中的第一行和第五列，并令c61=∞(在C3c61已经取值为无穷)，得到矩阵c4。上一页下一页返回10.5推销员及中国邮路问题

矩阵c、中的每行和每列均有n元素存在，按紧邻推断法可以找出两条有别于已找到的Hamilton回路的新回路，为:取回路H3进入下一步推演。

(6)继续重复步骤(4)，去掉C4中的第四行和第四列，得到矩阵C5。上一页下一页返回10.5推销员及中国邮路问题

从矩阵C5可以看出，已经不存在与H1,H2,H3不同的Hamilton回路，所求得的H3是最小的Hamilton回路。也就是说，校园小巴按:v1→v2→v6→v5→v3→v4→v1

，路线行驶一圈的时间为15.6。从计算过程可以看出，最后所选择的Hamilton回路的结果依赖于前面所选择行走的路线，如果第一步确定了某个出发点，后续的结果只能在此基础上推出，所以所求得的结果不一定是最优的。如果在本例中出发点选择v2，则计算的结果就不相同。如果需要寻找最优的H