第10章 地理网络分析

第十章地理网络分析

甘肃农业大学资源与环境学院对于许多现实的地理问题，譬如，城镇体系问题、城市地域结构问题、交通问题、商业网点布局问题、物流问题、管道运输问题、供电与通讯线路问题等等，都可以运用网络分析方法进行研究。

网络分析，主要是运用图论方法研究各类网络的结构及其优化问题。网络分析方法是计量地理学必不可少的重要方法之一。甘肃农业大学资源与环境学院问题1(哈密尔顿环球旅行问题,1859年爱尔兰数学家哈密尔顿提出):

十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）甘肃农业大学资源与环境学院问题2(四色问题,1852年，摩尔根):

对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了.问题3(关键路径问题):

一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序.这些工序相互约束,只有在某些工序完成之后,一个工序才能开始.即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间.

这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个？甘肃农业大学资源与环境学院列昂纳德·欧拉——7桥问题

东普鲁士的哥尼斯堡城（现在的加里宁格勒）是建在两条河流的汇合处以及河中的两个小岛上的，共有7座小桥将两个小岛及小岛与城市的其他部分连接起来，那么，哥尼斯堡人从其住所出发，能否恰好只经过每座小桥一次而返回原处？图论研究结果告诉我们，其答案是否定的。甘肃农业大学资源与环境学院内容地理网络的图论描述

最短路径与选址问题

最大流与最小费用流甘肃农业大学资源与环境学院第1节地理网络的图论描述地理网络的图论描述地理网络的测度（LeonhardPaulEuler，1707年－1783年)甘肃农业大学资源与环境学院通俗意义上的“图”，主要是指各种各样的地图、遥感影像图，或者是由各种符号、文字代表的示意图，或者是由各种地理数据绘制而成的曲线图、直方图等等。

图论中的“图”，是一个数学概念，这种“图”能从数学本质上揭示地理实体与地理事物空间分布格局，地理要素之间的相互联系以及它们在地域空间上的运动形式、地理事件发生的先后顺序等。

甘肃农业大学资源与环境学院（1）图：设V是一个由n个点vi(i=1，2，…，n)所组成的集合，即V={v1，v2，…，vn}，E是一个由m条线ei（i=1，2，…，m）所组成的集合，即E={e1，e2，…，em}，而且E中任意一条线，都是以V中的点为端点；任意两条线除了端点外没有其他的公共点。一、地理网络的图论描述（一）图的定义那么，把V与E结合在一起就构成了一个图G，记作G＝（V，E）。甘肃农业大学资源与环境学院（3）边：E中每一条线称为图G的边（或弧）；若一条边e连接u，v两个顶点，则记为e＝（u，v）。

（2）顶点：V中的每一个点vi（i=1，2，…，n）称为图G的顶点。（4）在图G＝（V，E）中，V不允许是空集，但E可以是空集。（5）从以上定义可以看出，图包含两个方面的基本要素：点集（或称顶点集）；边集（或称弧集）。甘肃农业大学资源与环境学院例：在如图10.1.1所示的图中，顶点集为

V＝｛v1，v2，v3，v4，v5，v6，v7，v8｝，边集为E＝{e1，e2，e3，e4，e5，e6，e7，e8，e9，e10，e11}。图10.1.1甘肃农业大学资源与环境学院（6）在现实地理系统中，对于地理位置、地理实体、地理区域以及它们之间的相互联系，可以经过一定的简化与抽象，将它们描述为图论意义下的地理网络，即图。

地理位置、地理实体、地理区域，譬如，山顶、河流汇聚点、车站、码头、村庄、城镇等——点。它们之间的相互联系，譬如，构造线、河流、交通线、供电与通讯线路、人口流、物质流、资金流、信息流、技术流等——点与点的连线。一个由基本流域单元组成的复杂的流域地貌系统，如果舍弃各种复杂的地貌形态，各条河流——线，河流分岔或汇聚处——点，流域地貌系统——水系的基本结局（树）。

甘肃农业大学资源与环境学院（7）需要说明的是：图的定义只关注点之间是否连通，而不关注点之间的连结方式。对于任何一个图，他的画法并不唯一。

甘肃农业大学资源与环境学院图与网络优化的一些基本问题例1最短路问题（SPP－shortestpathproblem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。例2公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？甘肃农业大学资源与环境学院例3指派问题（assignmentproblem）一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？例4中国邮递员问题（CPP－Chinesepostmanproblem）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。甘肃农业大学资源与环境学院例5旅行商问题（TSP－travelingsalesmanproblem）一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。例6运输问题（transportationproblem）某种原材料有个产地，现在需要将原材料从产地运往个使用这些原材料的工厂。假定每个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？甘肃农业大学资源与环境学院上述问题有两个共同的特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题；二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network）。与图和网络相关的最优化问题就是网络最优化或称网络优化（netwokoptimization）问题。所以上面例子中介绍的问题都是网络优化问题。由于多数网络优化问题是以网络上的流（flow）为研究的对象，因此网络优化又常常被称为网络流（networkflows）或网络流规划等。甘肃农业大学资源与环境学院（二）图的一些相关概念

（1）无向图与有向图：无向图——图的每条边都没有给定方向，即（u，v）＝（v，u）；有向图——图的每条边都给定了方向，即（u，v）≠（v，u）。

一般将有向图的边集记为A，无向图的边集记为E。这样，G=（V，A）就表示有向图，而G=（V，E）则表示无向图。甘肃农业大学资源与环境学院

（2）赋权图：如果图G＝（V，E）中的每一条边（vi，vj）都相应地赋有一个数值wij，则称G为赋权图，其中wij称为边（vi，vj）的权值。除了可以给图的边赋权外，也可以给图的顶点赋权。这就是说，对于图G中的每一顶点vj，也可以赋予一个载荷a(vj)。

（3）关联边：若e＝（u，v），则称u和v是边e的端点，e是u和v的关联边。甘肃农业大学资源与环境学院（4）环：若e的两个端点相同，即u＝v，则称为环。（5）多重边：若连接两个端点的边多于一条以上，则称为多重边。（6）多重图：含有多重边的图，称为多重图。（7）简单图：无环、无多重边的图，称为简单图。甘肃农业大学资源与环境学院（8）点与次。以点v为端点的边的个数称为点v的次，记为d(v)。次等于1的点称为悬挂点；与悬挂点关联的边称为悬挂边。次为零的点称为孤立点。次为奇数的点称为奇点；次为偶数的点称为偶点。（9）连通图。在图G中，若任何两点之间至少存在一条路（对于有向图，则不考虑边的方向），则称G为连通图，否则称为不连通图。甘肃农业大学资源与环境学院（10）路（链）：若图G＝（V，E）中，若顶点与边交替出现的序列（对于有向图来说，要求排在每一条边之前和之后的顶点分别是这条边的起点和终点）

P＝{vi1，ei1，vi2，ei2，…，eik-1，vik}

满足

eit

=(vit，vi，t+1)(t=1,2,…,k-1)

则称P为一条从vi1到vik的路（或链），简记为

P＝{vi1，vi2，…，vik}。（11）回路：若一条路的起点与终点相同，即vi1=vik，则称它为回路。（12）树：不含回路的连通的无向图称为树。甘肃农业大学资源与环境学院（13）基础图：从一个有向图D＝（V，A）中去掉所有边上的箭头所得到的无向图，就称为D的基础图，记之为G（D）。（14）截：如果从图中移去边的一个集合将增加亚图的数目时，被移去的边的集合就称为截。（15）子图：设G＝（V，E）是一个无向图，V1与E1分别是V与E的子集，即V1V，

E1E。如果对于任意ei∈E1，其两个端点都属于V1，则称G1＝（V1，E1）是图G的一个子图。甘肃农业大学资源与环境学院（16）支撑子图：设G1＝（V1，E1）是图G＝（V，E）的一个子图，如果V1＝V，则称G1是G的支撑子图。（17）支撑树：设G＝（V，E）是一个无向图，如果T＝（V1，E1）是G的支撑子图，并且T是树，则称T是G

的一个支撑树。（18）树的重量：一个树的所有边的权值之和称为该树的重量。（19）最小支撑树：在一个图的所有支撑树中，重量最小的那个叫做该图的最小支撑树。甘肃农业大学资源与环境学院v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子图v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撑子图甘肃农业大学资源与环境学院二、地理网络的测度

许多现实的地理问题，只要经过一定的简化和抽象，就可以将它们描述为图论意义下的地理网络，点和线的排布格局，并可以进一步定量化地测度它们的拓扑结构，以及连通性和复杂性。

树状型地理网络平面网络（二维的）非平面网络（非二维的）道路型环状型细胞型图10.1.5地理网络的拓扑分类

甘肃农业大学资源与环境学院

目前关于地理网络的拓扑研究，最多、最常见的是基于平面图描述的二维平面网络。

所谓平面图，被规定为：各连线之间不能交叉，而且每一条连线除顶点以外，不能再有其他的公共点（牛文元，1987）。

以下的讨论，除非特别申明外，都限于二维平面网络。

甘肃农业大学资源与环境学院（一）关联矩阵与邻接矩阵

关联矩阵（incidencematrix）测度网络图中顶点与边的关联关系。

假设网络图G＝（V，E）的顶点集为V={v1，v2，…，vn}，边集为E={e1，e2，…，em}，则该网络图的关联矩阵就是一个n×m矩阵，可表示为

式中：gij为顶点vi与边ej相关联的次数。甘肃农业大学资源与环境学院v3v1v2v4v5e1e2e3e4e5e6e7该图的关联矩阵为

例：

甘肃农业大学资源与环境学院邻接矩阵（adjacencymatrix）测度网络图中各顶点之间的连通性程度。

假设图G＝（V，E）的顶点集为V={v1，v2，…，vn}，则邻接矩阵是一个n阶方阵，可表示为式中：aij表示连接顶点vi与vj的边的数目。

甘肃农业大学资源与环境学院该图的邻接矩阵为

v3v1v2v4v5e1e2e3e4e5e6e7例：

甘肃农业大学资源与环境学院（二）有关测度指标对于任何一个网络图，都存在着3种共同的基础指标：

①连线（边或弧）数目m；

②结点（顶点）数目n；

③

网络中亚图的数目p。由它们可以产生如下几个更为一般性的测度指标：β指数、回路数k、α指数、γ指数。甘肃农业大学资源与环境学院

也称为线点率，是网络内每一个结点的平均连线数目

β=0，表示无网络存在；网络的复杂性增加，则β值也增大。

没有孤立点存在的网络，连线数目为n-p,则β指数为β指数如果地理网络不包含次级亚图，即P＝1，则其最低限度连接的指数值为。甘肃农业大学资源与环境学院回路数k

回路是一种闭合路径,它的始点同时也是终点。

若网络内存在回路，则连线的数目就必须超过n-p（最低限度连接网络的连接数目）。

回路数k为实际连线数目减去最低限度连接的连线数目，即

甘肃农业大学资源与环境学院指数指数指实际回路数与网络内可能存在的最大回路数之间的比率。网络内可能存在的最大回路数目为连线的最大可能数目减去最低限度连接的连线数目，即所以，

指数为

指数也可以用百分率表示甘肃农业大学资源与环境学院对于非平面网络，其指数为指数的变化范围，一般介于[0，1]区间，＝0意味着网络中不存在回路；＝1，说明网络中已达到最大限度的回路数目。

甘肃农业大学资源与环境学院γ指数

γ指数指网络内连线的实际数目与连线可能存在的最大数目之间的比率，对于平面网络，其计算公式为γ指数也可以用百分比表示γ指数是测度网络连通性的一种指标，其数值变化范围为[0，1]。γ＝0，表示网络内无连线，只有孤立点存在；γ＝1，则表示网络内每一个结点都存在与其他它所有结点相连的连线。甘肃农业大学资源与环境学院

对于非平面网络，指数的计算公式为

甘肃农业大学资源与环境学院表10.1.1几种简单网络图的有关测度指标

甘肃农业大学资源与环境学院第2节最短路径与选址问题

最短路径问题选址问题甘肃农业大学资源与环境学院对于许多地理问题，当它们被抽象为图论意义下的网络图时，问题的核心就变成了网络图上的优化计算问题。其中，最为常见的是关于路径和顶点的优选计算问题。在路径的优选计算问题中，最常见的是最短路径问题；而在顶点的优选计算问题中，最为常见的是中心点和中位点选址问题。

甘肃农业大学资源与环境学院“纯距离”意义上的最短路径例如，需要运送一批物资从一个城市到另一个城市，选择什么样的运输路线距离最短？“经济距离”意义上的最短路径

例如，某公司在10大港口C1，C2，…，C10设有货栈，从Ci到Cj之间的直接航运价格，是由市场动态决定的。如果两个港口之间无直接通航路线，则通过第三个港口转运。那么，各个港口之间最廉价的货运线路是什么？一、最短路径问题（一）最短路径的含义甘肃农业大学资源与环境学院“时间”意义上的最短路径

例如，某家经营公司有一批货物急需从一个城市运往另一个城市，那么，在由公路、铁路、河流航运、航空运输等4种运输方式和各个运输线路所构成的交通网络中，究竟选择怎样的运输路线最节省时间？

以上3类问题，都可以抽象为同一类问题，即赋权图上的最短路径问题。

不同意义下的距离都可以被抽象为网络图中边的权值。

权——这种权值既可以代表“纯距离

”，又可以代表“经济距离

”，也可以代表“时间距离

”。

甘肃农业大学资源与环境学院（二）最短路径的算法标号法（狄克斯屈拉算法）

1959年E.W.Dijkstar

提出的标号法是最短路径问题最好的求解方法。

标号法优点

不仅可以求出起点到终点的最短路径及其长度，而且可以求出起点到其他任何一个顶点的最短路径及其长度；同时适用于求解有向图或无向图上的最短路径问题。甘肃农业大学资源与环境学院标号法的基本思想设G是一个赋权有向图，即对于图中的每一条边，都赋予了一个权值。在图G中指定两个顶点，确定为起点和终点，不妨设v1为起点，vk为终点。

首先从v1开始，给每一个顶点标一个数，称为标号。这些标号，又进一步区分为T标号和P标号两种类型。其中，每一个顶点的T标号表示从起点v1到该点的最短路径长度的上界，这种标号为临时标号；P标号表示从v1到该点的最短路长度，这种标号为固定标号。在最短路径计算过程中，对于已经得到P标号的顶点，不再改变其标号；对于凡是没有标上P标号的顶点，先给它一个T标号；算法的每一步就是把顶点的T标号逐步修改，将其变为P标号。那么，最多经过k-1步，就可以求得到从起点v1到每一个顶点的最短路径及其长度。甘肃农业大学资源与环境学院标号法具体计算步骤

①如果刚刚得到P标号的点是vi，那么，对于所有这样的点将其T标号修改为：min[T(vj)，P(vi)+wij]。②若G中没有T标号，则停止。否则，把点的T标号修改为P标号，然后再转入①。

其中，满足

开始，先给v1标上P标号P(v1)＝0，其余各点标上T标号T(vj)＝+∞（j≠1）。甘肃农业大学资源与环境学院例1：在图10.2.1所示的赋权有向图中，每一个顶点vi（i=1，2，…，n）代表一个城镇；每一条边代表相应两个城镇之间的交通线，其长度用边旁的数字表示。试求城镇v1到v7之间的最短路径。

图10.2.1赋权有向交通网络图甘肃农业大学资源与环境学院解：首先给v1标上P标号P(v1)=0，表示从v1到v1的最短路径为零。其他点(v2，v3，…，v7)标上T标号T(vj)＝+∞（j＝2，3，…，7）。第1步：①

v1是刚得到P标号的点。因为(v1，v2)，(v1，v3)，(v1，v4)∈E，而且v2，v3，v4是T标号，所以修改这3个点的T标号为

T(v2)＝min[T(v2)，P(v1)+w12]＝min[+∞，0+2]＝2

T(v3)＝min[T(v3)，P(v1)+w13]＝min[+∞，0+5]＝5

T(v4)＝min[T(v4)，P(v1)+w14]＝min[+∞，0+3]＝3②

在所有T标号中，T(V2)＝2最小，于是令P(V2)＝2。甘肃农业大学资源与环境学院第2步：①v2是刚得到P标号的点。因为(v2，v3)，(v2，v6)∈E，而且v3,v6是T标号，故修改v3和v6的T标号为T(v3)＝min[T(v3)，P(v2)+w23]＝min[5，2+2]＝4

T(v6)＝min[T(v6)，P(v2)+w26]＝min[+∞，2+7]＝9

②在所有的T标号中，T(v4)＝3最小，于是令P(v4)＝3。甘肃农业大学资源与环境学院第3步：①v4是刚得到P标号的点。因为(v4，v5)∈E，而且v5是T标号，故修改v5的T标号为

T(v5)＝min[T(v5)，P(v4)+w45]＝min[+∞，3+5]＝8

②在所有的T标号中，T(v3)＝4最小，故令P(v3)＝4。甘肃农业大学资源与环境学院第4步：①v3是刚得到P标号的点。因为(v3，v5)，(v3，v6)∈E，而且v5和v6为T标号，故修改v5和v6的T标号为

T(v5)＝min[T(v5)，P(v3)+w35]＝min[8，4+3]＝7

T(v6)＝min[T(v6)，P(v3)+w36]＝min［9，4+5]＝9

②

在所有的T标号中，T(v5)＝7最小，故令P(v5)＝7。

甘肃农业大学资源与环境学院第5步：①

v5是刚得到P标号的点。因为(v5，v6)，(v5

，v7)∈E，而且v6和v7都是T标号，故修改它们的T标号为

T(v6)＝min[T(v6)，P(v5)+w56]＝min[9，7+1]=8

T(v7)＝min[T(v7)，P(v5)+w57]＝min[+∞，7+7]=14

②

在所有T标号中，T(v6)＝8最小，于是令：P(v6)＝8。甘肃农业大学资源与环境学院第6步：①

v6是刚得到P标号的点。因为(v6，v7)∈E，而且v7为T标号，故修改它的T标号为

T(v7)＝min[T(v7)，P(v6)+w67]＝min[14，8+5]=13

②目前只有v7是T标号，故令：P(v7)＝13。

从城镇v1到v7之间的最短路径为(v1，v2，v3，v5，v6，v7)，最短路径长度为13。甘肃农业大学资源与环境学院甘肃农业大学资源与环境学院最短路问题的应用举例例1、电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？v1v2v3v4v5v7v615103176445260151014131930181622v1v3v5v6v7总长度为22甲地乙地甘肃农业大学资源与环境学院237184566134105275934682求从1到8的最短路径甘肃农业大学资源与环境学院237184566134105275934682X={1},w1=0min{c12,c14,c16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},p4=1p4=1p1=0甘肃农业大学资源与环境学院237184566134105275934682X={1,4}min{c12,c16,c42,c47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},p2=2p1=0p4=1p2=2甘肃农业大学资源与环境学院237184566134105275934682X={1,2,4}min{c13,c23,c25,c47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},p6=3p2=2p4=1p1=0p6=3甘肃农业大学资源与环境学院237184566134105275934682X={1,2,4,6}min{c23,c25,c47,c67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},p7=3p2=2p4=1p1=0p6=3p7=3甘肃农业大学资源与环境学院237184566134105275934682X={1,2,4,6,7}min{c23,c25,c75,c78}=min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6X={1,2,4,5,6,7},p5=6p2=2p4=1p1=0p6=3p7=3p5=6甘肃农业大学资源与环境学院237184566134105275934682X={1,2,4,6,7}min{c23,c53,c58,c78}=min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8X={1,2,3,4,5,6,7},p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8甘肃农业大学资源与环境学院237184566134105275934682X={1,2,3,4,6,7}min{c38,c58,c78}=min{8+6,6+4,3+7}=min{14,10,11}=10X={1,2,3,4,5,6,7,8},p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10甘肃农业大学资源与环境学院237184566134105275934682X={1,2,3,4,6,7,8}1到8的最短路径为{1，4，7，5，8}，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10甘肃农业大学资源与环境学院二、选址问题

选址问题，是现代地理学研究的主要问题之一。选址问题涉及人类生产、生活、文化、娱乐等各个方面。选址问题的数学模型取决于两个方面的条件：可供选址的范围、条件；怎样判定选址的质量。本节的讨论仅限于选址的范围是一个地理网络，而且选址位置位于网络图的某一个或几个顶点上。

对这样的选址问题，根据其选址的质量判据，可以将其归纳为求网络图的中心点与中位点两类问题。甘肃农业大学资源与环境学院（一）中心点选址问题

例：某县要在其所辖的6个乡镇之一修建一个消防站，为6个乡镇服务，要求消防站至最远乡镇的距离达到最小。

中心点选址问题的质量判据

最佳选址位置所在的顶点的最大服务距离为最小。中心点选址问题适宜于医院、消防站点等一类服务设施的布局问题。甘肃农业大学资源与环境学院

设G＝（V，E）是一个无向简单连通赋权图，连接两个顶点的边的权值代表它们之间的距离，对于每一个顶点vi，它与各个顶点之间的最短路径长度为di1，di2，…，din。这些距离中的最大数称为顶点vi的最大服务距离，记为e(vi)。

那么，中心点选址问题，就是求网络图G的中心点，使得中心点选址问题的数学描述

甘肃农业大学资源与环境学院例2：假设某县下属的6个乡镇及其之间公路联系如图所示。每一顶点代表一个乡镇；每一条边代表连接两个乡镇之间的公路，每一条边旁的数字代表该条公路的长度。现在要设立一个消防站，为全县的6个乡镇服务。试问该消防站应该设在哪一个乡镇（顶点）？

图10.2.2甘肃农业大学资源与环境学院解：第1步：用标号法求出每一个顶点vi至其他各个顶点vj的最短路径长度dij（i，j

＝1，2，…，6），并将它们写成如下的距离矩阵甘肃农业大学资源与环境学院

第2步：求每一个顶点的最大服务距离。显然，它们分别是矩阵D中各行的最大值，即：e(v1)＝6，e(v2)＝7，e(v3)＝6，e(v4)＝7，e(v5)＝6，e(v6)＝7。

第3步：判定。因为e(v1)＝e(v3)＝e(v5)＝min{e(vi)}＝6，所以v1，v3，v5都是中心点。也就是说，消防站设在v1，v3，v5中任何一个顶点上都是可行的。甘肃农业大学资源与环境学院中位点选址问题的质量判据

使最佳选址位置所在的顶点到网络图中其他各个顶点的最短路径距离的总和（或者以各个顶点的载荷加权求和）达到最小。（二）中位点选址问题甘肃农业大学资源与环境学院中位点选址问题的数学描述

设G＝（V，E）是一个简单连通赋权无向图，连接两个顶点的边的权值为该两顶点之间的距离；对于每一个顶点vi（i＝1，2，…，n），有一个正的负荷a(vi)，而且它与其他各顶点之间的最短路径长度为di1，di2，…，din。那么，中位点选址问题，就是求图G的中位点，使得甘肃农业大学资源与环境学院例3：某县下属7个乡镇，各乡镇所拥有的人口数a(vi)（i=1，2，…，7），以及各乡镇之间的距离wij（i，j=1，2，…，7）如图所示。现在需要设立一个中心邮局，为全县所辖的7个乡镇共同服务。问该中心邮局应该设在哪一个乡镇（顶点）？

图10.2.3甘肃农业大学资源与环境学院解：第1步：用标号法求出每一个顶点vi至其他各个顶点vj的最短路径长度dij（i，j

＝1，2，…，7），并将其写成如下距离矩阵

甘肃农业大学资源与环境学院第2步：以各顶点的载荷（人口数）加权，求每一个顶点至其他各个顶点的最短路径长度的加权和

甘肃农业大学资源与环境学院

第3步：判断。因为

所以，v3和v4都是图10.2.3的中位点。即：中心邮局设在点v3或点v4都是可行的。

甘肃农业大学资源与环境学院v6v8v1v7v5v4v2v389363253757例4，某县要在其所辖的8个乡镇之一修建一个消防站，为8个乡镇服务，要求消防站至最远乡镇的距离达到最小。假设该8个乡镇之间的交通网络被抽象为无向赋权连通图，权值为乡镇之间的距离。下面求解消防站应设在哪个乡镇，即哪个顶点？甘肃农业大学资源与环境学院首先，用Dijkstra算法计算出每一个顶点vi至其它各顶点vj的最短路径长度dij(i,j=1,2,…,6)，写出距离矩阵：

6061916152565473甘肃农业大学资源与环境学院其次，求距离矩阵中每行的最大值，即各个顶点的最大服务距离，得

e(v1)=14,e(v2)=15,e(v3)=20,e(v4)=12,e(v5)=15,e(v6)=17,e(v7)=12,e(v8)=20

最后计算最大服务距离的最小值。显然，e(v4)=e(v7)=min{e(vi)}。所以，消防站应建在v4或v7点所在的乡镇。甘肃农业大学资源与环境学院6061916152565473要求消防站至所有乡镇的距离达到最小：消防站应建在v5点所在的乡镇甘肃农业大学资源与环境学院第3节最大流与最小费用流

最大流问题及其求解方法最小费用流及其求解方法甘肃农业大学资源与环境学院一、最大流问题及其求解方法

（一）最大流问题最大流问题设有向网络N（V，A），在发点Vs

有一批货，要通过网络上的弧运输到收点Vt

去，受运输条件限制，每条弧aij在单位时间内通过的车辆数不能超过cij

辆，分析：如何组织运输才能使从Vs到Vt

在单位时间内通过的车辆达到最多？上面描述的这类问题，称为最大流问题。

最大流问题广泛地应用在交通运输、供水、油管供油、邮电通讯，也可以用在生产安排，管理优化等实际问题上。甘肃农业大学资源与环境学院例：如图10.3.1中，有一批物资需要用汽车尽快从发点①运到收点⑦，弧（i，j）上所标的数字表示该条道路在单位时间内最多能通过的车辆数（单位：百辆），问如何调运，才能使单位时间里有最多的车辆从①调到⑦。图10.3.1甘肃农业大学资源与环境学院┍┑线

性

规

划

方

法┕┙点①出发的车辆数应该与点⑦到达的车辆数相同，除①和⑦以外的各中间点，进的车辆数应该与离去的车辆数应该相同。xij

是通过弧(i，j)的车辆数。（10.3.1）（10.3.4）（10.3.5）（10.3.6）（10.3.2）（10.3.3）甘肃农业大学资源与环境学院

对所有弧（i，j），应满足约束

满足（10.3.1）～（10.3.7）的解称为从①到⑦的一个可行流。我们的目的：在所有可行流中求出一个方案，使得这个可行流得到的f最大。

若从收点到发点连接一条假想弧(7，1)，设它的容量c71=∞，那么

对点①：

对点⑦：

最大流问题的目标为┍┑线

性

规

划

方

法┕┙

（10.3.7）（10.3.8）（10.3.9）（10.3.10）甘肃农业大学资源与环境学院所以，对于发点为Vs，收点为Vt的网络N（V，U），当增加一条约束为cts=∞的假想弧（t，s）后，最大流问题就成为：

容量约束

平衡条件

目标函数┍┑线

性

规

划

方

法┕┙

（10.3.11）（10.3.12）（10.3.13）甘肃农业大学资源与环境学院（二）求最大流的方法：弧标号法

尽管最大流问题可以用线性规划模型描述，但是我们一般并不用求解线性规划的方法求最大流，而是用一种更为简便明了的图上作业法——弧标号法，求解上述最大流问题。

甘肃农业大学资源与环境学院

(1)为了便于弧标号法的计算，首先需要将最大流问题（譬如图10.3.1）重新改画成为图10.3.2的形式。

图10.3.2甘肃农业大学资源与环境学院在图10.3.2中，每条弧上标有两个数字，其中，靠近点i的是，靠近点j的是。如①②表示从①到②的最大通过量是5（百辆），从②到①的最大通过量是0；②③表示从②到③和从③到②都可以通过2（百辆）；等等。

图10.3.2甘肃农业大学资源与环境学院

(2)求最大流的基本步骤：标号法求最大流的过程，就是对图10.3.2反复地进行修改的过程，其计算步骤如下：

步骤1.

从发点s到收点t选定一条路，使这条路通过的所有弧Vij的前面约束量cij都大于0，如果找不到这样的路，说明已经求得最大流，转步骤4。

步骤2.

在选定的路上，找到最小的容许量cij定为P。

甘肃农业大学资源与环境学院

步骤3.

对选定的路上每条弧的容量作以下修改，对于与路同向的弧，将cij修改为cij-P，对于与路反向的弧，将cij修改为cij+P。修改完毕后再转入步骤1。步骤4.用原图中各条弧上起点与终点数值减去修改后的图中对应点的数值，得到正负号相反的两个数，并将从正到负的方向用箭头表示。这样，就得到一个最大流量图。

甘肃农业大学资源与环境学院第1次修改：

①从发点s到收点t找一条路，使得这条路上的所有弧前面的约束量。从图10.3.2中可以看出，显然，①—③—⑥—⑦就是满足这样的条件的一条路。

下面，我们用弧标号法求解图10.3.2中的最大流。

②在路①—③—⑥—⑦中,,,，所以取。甘肃农业大学资源与环境学院

③在路①—③—⑥—⑦中，修改每一条弧的容量甘肃农业大学资源与环境学院通过第1次修改，得到图10.3.3。图10.3.3返回步骤①，进行第2次修改。甘肃农业大学资源与环境学院

第2次修改：选定①—②—⑤—⑦，在这条路中，由于，所以，将改为2，改为0，改为5，、、改为3。修改后的图变为图10.3.4。

图10.3.4返回步骤①继续做第3次修改。甘肃农业大学资源与环境学院第3次修改：取①—②—③—⑤—⑦，在这条路中，由于所以将改为0，改为5，改为0，改为4，改为1，改为2，改为3,c75改为5。修改后的图变为图10.3.5。

图10.3.5返回步骤①，继续做第4次修改。，甘肃农业大学资源与环境学院

第4次修改：选定①—④—⑥—⑦，在这条路中，由于P=c67=1，所以将c14改为4,c41改为1,c46改为4,c64改为1,c67改为0，c76改为7。修改后的图为变为图10.3.6。

图10.3.6返回步骤①，继续做第5次修改。甘肃农业大学资源与环境学院

第5次修改：选定①—④—⑥—⑤—⑦,在这条路中，由于P=c65

=1，所以将c14和c46均改为3，c65改为0，c57改为2，c41、c64、c56均改为2，c75改为6。修改后的图变为图10.3.7。

图10.3.7甘肃农业大学资源与环境学院需要注意的是，由图10.3.7中可以看出，弧本来在图10.3.2中是无容量可通过的，但经过几次修改，由③⑥变成③⑥，即此时从③到⑥还可通过1（百辆），而从⑥到③，可以通过6（百辆）的容量，这说明，修改过程实际上是把计划中从③到⑥的通过车辆数减少了。甘肃农业大学资源与环境学院第6次修改：取①—④—⑥—③—⑤—⑦，在这条路中，由于P=c35=1，所以将c14和c46均改为2，c63改为5,c35改为0，c57改为1，c41、c64、c53均改为3，c36改为2，c75改为7。修改后的图变为图10.3.8。

图10.3.8甘肃农业大学资源与环境学院在图10.3.8中，从发点①到收点⑦，再也不存在连通的起点容量都大于零的弧了，所以图10.3.8为最大流图。

转入步骤④，用原图中各条弧上发点与收点数值减去修改后的图上各点的数值，将得到正负号相反的两个数，将这个数标在弧上，并将从正到负的方向用箭头表示,这样就得到最大流量图。例如原来弧是③⑥，现在是③⑥，相减为±5，③那边为正，我们就记作③⑥。这样，就得到图10.3.9，即最大流量图。依这样的调度方式，可以从发点s调运14（百辆）汽车到收点t。

甘肃农业大学资源与环境学院图10.3.9最大流量图

甘肃农业大学资源与环境学院

(3)最大流算法的讨论：

①从上面的标号计算过程可以看出，一个图成为最大流图的条件是从发点到收点的每一条路上总存在某个起点容量为零的弧，我们称这样的路为饱和路；如果从s到t有一条路，它上面每条路的起点容量都大于零，则称为非饱和路。由此可以得到一个结论：一个图是最大流图的充分必要条件是不存在从s到t的非饱和路。甘肃农业大学资源与环境学院

②将网络中的点分成两组，一组包括发点，称为发集，一组包括收点t，称为收集，连接到的所有弧称为截集，截集中各弧在旁的容量和称为截集的容量。

例如，在图10.3.2中，

图10.3.2甘肃农业大学资源与环境学院我们取，，则截集为{(2,5),(3,5),(1,4),(3,6),(3,4)}，它的容量为3+3+5+7+3=21；若在图10.3.6中，取，，则截集为{(2,5),(3,5),(6,5),(6,7)}，其容量为0+1+1+0=2等等。在将网络分成发集与收集的所有分法中，容量最小的截集称为最小截集。可以证明：甘肃农业大学资源与环境学院设f是网络N的一个可行流，那么，网络N的最小截集的容量（μ）等于网络最大流与f的差，即（10.3.14）

式中：μ称为可行流f的余量。

甘肃农业大学资源与环境学院

显然，当μ=0时，就得到了最大流。因此，进一步可以得到：在网络N中，设f是从发点到收点的一个可行流，那么，f是最大流的充分必要条件是网络N的最小截集的容量为零。

从到的最大流的流量等于分离与的最小截集的容量。

这表明，从到，最小截集的弧是网络中的“卡脖子”线路，要获得最大流量，必须在最小截集的各弧上达到满载。甘肃农业大学资源与环境学院图10.3.10

③最大流fmax的大小是确定的，但最大流的路线可以不唯一。在上例中，如果从不同的路开始来修改图，也可能得到另外一个最大流图（图10.3.10）。

甘肃农业大学资源与环境学院对于不同的最大流图（譬如图10.3.9与图10.3.10），它们必有以下性质：

对于网络的最小截集上的弧，它们的流量是相同的。

对于由最小截集分开的V1和V2内，它们的流量可能不同，但都是相差一个或几个不饱和回路上的量，如图10.3.9与图10.3.10，相差的是③—④—⑥—③回路上一个值为2的流量。

甘肃农业大学资源与环境学院二、最小费用流及其求解方法

（一）最小费用流问题如果在考虑网络上流量的同时，还要使得所安排流量的费用或者代价达到最小，就是所谓的最小费用流问题。

在上例中，如果单位车辆数通过某一条弧要付出一定的代价，其代价如图10.3.11。

甘肃农业大学资源与环境学院现在要从发点①调动若干车辆到收点⑦去，约束条件为图10.3.1，代价条件为图10.3.11，要使所花费的代价达到最小，用公式表示，就是要在（10.3.1）～（10.3.7）式的约束条件下，找到一个可行流f的流量（10.3.15）

使其代价最小，即

（10.3.16）

式中：指单位车辆数通过弧的代价。

甘肃农业大学资源与环境学院图10.3.11代价条件

图10.3.1约束条件

甘肃农业大学资源与环境学院（二）求解最小费用流问题求最小费用流的步骤和求最大流的步骤几乎完全一致，只是在步骤（1）中，选一条非饱和路时，应选代价和最小的路，即最短路。例如，在图10.3.11中，从①到⑦的最短路是①—③—⑤—⑦，代价为7，在这条最短非饱和路上取后，③—⑤变成容量为零，在下一次选择最短路时应将③—⑤视为断路来选取最短非饱和路。另外，选取①—③—⑤—⑦路后，③—①，⑤—③，⑦—⑤的弧成为容量大于零的弧，可分别标上它们的代价值为-3，-3，-1，是①—③，③—⑤，⑤—⑦的相反数。

甘肃农业大学资源与环境学院在求最小费用流过程中，可以依上述方法不断重复求最大流的步骤来进行，当流量达到时就可以停止，这时求出的是最小费用流。当然，如果，就需要将步骤进行到最后，直到不存在非饱和路存在为止。

按照这种方法，可以将约束条件由图10.3.1所示，代价函数为图10.3.11所示的最小费用流问题的求解算法，可以用表10.3.1表示，这里设。

甘肃农业大学资源与环境学院表10.3.1最小费用流的求解过程

将各条路的流量相加，就得到最小费用流，如图10.3.12所示。

甘肃农业大学资源与环境学院图10.3.12最小费用流

这个最小费用流的总代价为

甘肃农业大学资源与环境学院练习：提出下图的关联矩阵和邻接矩阵甘肃农业大学资源与环境学院关联矩阵M=邻接矩阵A=甘肃农业大学资源与环境学院练习2、用标号法求下图从v1到v6的最短路。v1v2v3v4v6v5352242421甘肃农业大学资源与环境学院

解（1）首先给v1以P标号，给其余所有点T标号。（2）（3