求常用网络分析方法

  对于许多现实的地理问题,譬如,城镇体系问题,城市地域结构问题,交通问题,商业网点布局问题,物流问题,管道运输问题,供电与通讯线路问题,…,等等,都可以运用网络分析方法进行研究科来网络分析。

网络分析,是运筹学的一个重要分支,它主要运用图论方法研究各类网络的结构及其优化问题科来网络分析。

网络分析方法是计量地理学必不可少的重要方法之一科来网络分析。

本章主要内容:

地理网络的图论描述

最短路径与选址问题

最大流与最小费用流

第一节 地理网络的图论描述

通俗意义上的"图",主要是指各种各样的地图,遥感影像图,或者是由各种符号,文字代表的示意图,或者是由各种地理数据绘制而成的曲线图,直方图,等等科来网络分析。

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

一,地理网络的图论描述

(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)无向图与有向图

无向图——图的每条边都没有给定方向,

即(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的子集,即V1 V,E1 E科来网络分析。如果对于任意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)最小支撑树科来网络分析。

在一个图的所有支撑树中,重量最小的那个叫做该图的最小支撑树科来网络分析。

二,地理网络的测度

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

树状型

地理网络

平面网络(二维的)

非平面网络(非二维的)

道路型

环状型

细胞型

图10科来网络分析。

  1科来网络分析。5 地理网络的拓扑分类

目前关于地理网络的拓扑研究,最多,最常见的是基于平面图描述的二维平面网络科来网络分析。

所谓平面图,被规定为:各连线之间不能交叉,而且每一条连线除顶点以外,不能再有其它的公共点(牛文元,1987)科来网络分析。

以下的讨论,除非特别申明外,都限于二维平面网络科来网络分析。

(一)关联矩阵与邻接矩阵

关联矩阵——测度网络图中顶点与边的关联关系科来网络分析。

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

gij为顶点vi与边ej相关联的次数科来网络分析。

v3

v1

v2

v4

v5

e1

e2

e3

e4

e5

e6

e7

该图的关联矩阵为:

例:

邻接矩阵——测度网络图中各顶点之间的连通性程度科来网络分析。

假设图G=(V,E)的顶点集为V={v1,v2,…,vn},则邻接矩阵是一个n阶方阵,可表示为:

aij表示连接顶点vi与vj的边的数目科来网络分析。

该图的邻接矩阵为:

v3

v1

v2

v4

v5

e1

e2

e3

e4

e5

e6

e7

例:

(二)有关测度指标

β指数

回路数k

α指数

γ指数

对于任何一个网络图,都存在着三种共同的基础指标:

① 连线(边或弧)数目m;

② 结点(顶点)数目n;

③ 网络中亚图的数目p科来网络分析。

由它们可以产生如下几个更为一般性的测度指标:

(1)β指数

◣β指数——线点率,是网络内每一个节点的平均连线数目科来网络分析。

◣β=0,表示无网络存在;网络的复杂性增加,则β值也增大科来网络分析。

◣没有孤立点存在的网络,连线数目为n- p,则β指数为

如果地理网络不包含次级亚图,即P=1,则其最低限度连接的 指数值为 科来网络分析。

(2) 回路数k

◣回路是一种闭合路径,它的始点同时也是终点科来网络分析。

◣若网络内存在回路,则连线的数目就必须超过n-p(最低限度连接网络的连接数目)科来网络分析。

◣回路数k——实际连线数目减去最低限度连接的连线数目,即

(3) 指数

◣ 指数——实际回路数与网络内可能存在的最大回路数之间的比率科来网络分析。

◣网络内可能存在的最大回路数目为连线的最大可能数目减去最低限度连接的连线数目,即

所以, 指数为

指数也可以用百分率表示

对于非平面网络,其 指数为

指数的变化范围,一般介于[0,1]区间, =0意味着网络中不存在回路; =1,说明网络中已达到最大限度的回路数目科来网络分析。

(4) γ指数

◣γ指数——网络内连线的实际数目与连线可能存在的最大数目之间的比率,对于平面网络,其计算公式为:

γ指数也可以用百分比表示

◣γ指数是测度网络连通性的一种指标,其数值变化范围为[0,1]科来网络分析。

◣γ=0,表示网络内无连线,只有孤立点存在;

γ=1,则表示网络内每一个节点都存在与其它所有节点相连的连线科来网络分析。