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

用图来表示各类地理事物，可以说是地理学的一个基本特征。在早期的地理学研究中，几乎无一例外地都使用各种符号和图象，来代表所要描述的地理实体。因此，对于地理学来说，图一直是一种传统的方法，它的直观性， 形象性和使用上的方便性是人人皆知的。但是，这些所谓的图对地理事物之间的相互联系的本质还未能给予充分的揭示，因此，在可比性与地理学的定量分析方面都表现出某些不足，有值得探讨的必要。

一、地理网络的图论描述

在一个现实的地理系统中，许多地理事物及其之间的相互联系，均可以直接地或者经过适当的简化取舍之后间接地抽象为“网络图”的概念。在这种网络图中，地理系统的地理事物被抽象为点，譬如，山岭制高点，河川汇流点，居民点，城市，工矿分布点，交通站点等，甚至人口密度，工业产值， 生物种的数量等抽象的概念也可以被看作为分布点。而地理事物之间的相互联系则被抽象为点的连线，譬如，河流，构造带，交通线，通讯线路等，甚至人口流，物质流，能量流，经济流，价值流，信息流等都可以被抽象为地理事物分布点之间的连线。对于许多复杂的地理实体，也可以经过适当的简化取舍将其抽象为地理网络的形象与直观。譬如，由各种基本地貌单元构成的流域地貌系统，就可以被简化为该流域的水系格局，即树状网络图。著名的数学家列昂纳德·欧拉（Euler)于 1736 年首次提出的图论问题“七桥问题”，其实质就是一个地理问题。东普鲁士的哥尼斯堡城（现在的加里宁格勒)是建在两条河流的汇合处以及河中的两个小岛上的（见图 7-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)。V 中的每一个点 vi（i=1，2，⋯，n)称为 G 的顶点；E 中每一条线称为 G 的边，若一条边 e 连接 u，v 两顶点，则记为 e=（u，v)。如果 G 的每条边给定了方向， 即（u，v)≠（v，u)，则称 G 为有向图；如果 G 的每条边都没有方向，即（u， v)=（v，u)，则 G 称为无向图。

在网络图 G＝（V，E)中，V 不允许是空集，但 E 可以是空集合。从以上定义可以看出，网络图包含了两个方面的要素：（1)点集（或者称顶点集)；

（2)边集（或称弧集)。例如在图 7-2 的网络图（a)中，顶点集为 V＝{v1，v2， v3，v4，v5，v6}，边集为 E＝{e1，e2，e3，e4，e5，

e6，e7，e8}，记为图 G＝{V，E}。在图（b)中，顶点集为 V＝{v1，v2，v3， v4，v5，v6}，边集为 A={a1，a2，a3，a4，a5，a6，a7，a8}，记为图 D=（V， A)。图（a)与图（b)的差别是：G 中的边（联线)没有方向，而 D 中的边（联线)是有方向的。因此 G 是无向图，而 D 是有向图。如果顶点 v1，v2，v3，v4， v5，v6 分别代表某区域的城镇，而顶点的联线（边)e1，e2，e3，e4，e5，e6， e7，e8 分别代表连接城镇之间的公路，则（a)所示的图 G＝（V，E)就表示了该区域的公路交通网络，（b)所示的有向图 D＝（V，A)则可以理解为由单行线所形成的交通网络。

同理，如果令顶点集 V 表示全国各地所有的铁路站点所构成的集合，边集 E 表示连接所有铁路站点的铁路线构成的集合，则图 G=（V，E)就表示了全国铁路交通网络；若令顶点集 V 为某一流域地貌系统中所有的河流汇流点组成的集合，而边集 A 代表该流域的所有河流组成的集合，则图 D=（V，A) 就表示了该流域的水系网络；⋯⋯。

事实上，如果严格地按照图论关于图的定义，只关注点之间是否流通， 而不去注重点间的连通方式，那么任何一个图的画法就不是唯一的一种。由地理事物抽象而来的点（顶点)，可以画成平面上的点，也可以随意地画成没有特定的物理位置的点。而由地理事物之间的相互联系抽象而来的连线

（边)，可以是直线也可以是曲线；可以是有向的，也可以是无向的。其最为重要的概念是表示顶点的“点”和表示连线的“边”，而其相对位置并不是至关重要的。譬如，下图（图 7-3)中的（a)与（b)只不过是同一个图的不同画法。

为了更进一步地对地理网络进行分析，以下我们对图的一些基本概念作一简单介绍。

  1. 关联边。若 e＝（u，v)∈E，则称 u，v 是边 e 的端点，称 e 是 u，v 的关联边。

  2. 环。若 e 的两个端点相同，即 u=v，则称为环。

  3. 多重边。若联结两个端点的边多于一条以上，则称为多重边。

  4. 简单图。无环、无多重边的图称为简单图。

  5. 多重图。含有多重边的图称为多重图。

  6. 点与次。

（1)次。以顶点 v 为端点的边的个数称为点 v 的次，记为 d（v)。

（2)悬挂点、悬挂边、孤立点。次等于 1 的点称为悬挂点；与悬挂点关联的边称为悬挂边；次为零的点称为孤立点。

（3)奇点与偶点。次为奇数的点称为奇点；次为偶数的点称为偶点。

  1. 路（链)。若图 G＝（V，E)中的顶点和边交替出现的序列 P＝{vi1，ei1， vi2，ei2，⋯，eik-1，vik}（对于有向图来说，要求排在每一条边之前和之后的顶点分别是这条边的起点和终点)满足：

eit＝（vit，vi，t+1)（t＝1，2，⋯，k-1) （1)

则称 P 为一条从 vi1 到 vik 的路（链)。简记为 P＝{vi1，vi2，⋯，vik}。8.回路。若路的第一点与最后一个点相同，即 vi1＝vik，则称为回路。

  1. 连通图。在图 G 中，若任何两点之间至少存在一条路（对于有向图， 则不考虑其边的方向)，则称 G 为连通图。否则称为不连通图。

  2. 树。不含回路的连通的无向图称为树。

  3. 赋权图。如果图 G＝（V，E)中的每一条边（vi，vj)都相应地赋有一个数值ωij，则称 G 为赋权图。其中，ωij 称为边（vi，vj)的权值。

  4. 基础图。从一个有向图 D＝（V，A)中去掉所有边上的箭头所得到的一个无向图，就称为 D 的基础图，记之为 G（D)。

  5. 截。从图中移去边的一个集合将增加亚图的数目时，被移去的边集合就称为截。

  6. 子图。设 G＝（V，E)是一个无向图，V1 与 E1 分别是 V 与 E 的子集，即V1 ⊆ V，E1 ⊆ E。如果对于任意ei ∈E1 ，其两个端点都属于V1 , 则称G1=（V1，E1)是图 G 的一个子图。

  7. 支撑子图。设 G1=（V1，E1)是图 G=（V，E)的子图，如果 V1=V，则称G1 是 G 的支撑子图。

  8. 支撑树。设 G＝（V，E)是一个无向图，如果 T＝（V1，E1)是 G 的支撑子图，并且 T 是树，则称 T 是 G 的一个支撑树。

  9. 树的重量。一个树的所有边的权值之和称为该树的重量。

  10. 最小支撑树。在一个图的所有支撑树中，重量最小的那个叫做该图的最小支撑树。

二、地理网络的有关测度矩阵与测度指标

当一个现实地理系统中的客观地理事物及其之间的相互联系被抽象为图论描述的地理网络图时，我们就可以借助于有关的测度矩阵或者测度指标对其性质、特征及复杂性等进行定量化描述。

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

1.关联矩阵 关联矩阵是对网络中的顶点与边的关联关系的一种描述。假设网络图 G＝（V，E)的顶点集为 V＝｛v1，v2，⋯，vn｝，边集为 E=｛e1， e2，⋯，em｝，则该网络图的关联矩阵为一个 n×m 矩阵，可表示为：

g11

L(G) = g 21

g n1

g12 g22

gn2

g1m 

2 m 

g nn 

(2)

（2)式中，gij 为顶点 vi 与边 ej 相关联的次数，显然，gij 的取值只能是 0，1，或者 2。

例如，图 7-3 中（a)或（b)的关联矩阵为：

 1 1

 

 0

L(G) =  0 1

 

2.邻接矩阵 邻接矩阵是对网络图中各顶点之间的连通性程度进行描述的一种矩阵。假设图 G=（V，E)的顶点集为 V={v1，v2，⋯，vn}，则邻接矩

阵是一个 n×n 的方阵，可表示为：

 a11 A(G) = a 21

an1

a12

a22

a n2

a1n 

a 2n 

a nn 

(3)

（3)式中，aij 表示连接顶点 vi 与 vj 的边的数目。例如，图 7-3 中（a)或（b)的邻接矩阵为：

 0 1 1 0 1

1 0 1 0 0

 

A(G) =  1 1 0 1 1

 

 0 0 1 0 1

 1 0 1 1 0

 

（二)有关的测度指标

对于任何一个网络图，都存在着三种共同的基础指标：①在网络中次级亚网图的分割数目，即互不连接数目；②在网络中的连线数目；③网络中的接点数目。如果将以上三个基础指标分别记为 p、m 和 n，则我们可以得到关于网络结构的一般性测度指标如下。

  1. β指数。β指数也称为线点率，它是网络内每一个接点的平均联线数目，即

β = m

n

β指数是关于地理网络的复杂性程度的简单度量，其数值的范围在[0， 3]区间上。β=0，表示无网络存在；网络的复杂性增加，则β值增大。一种最低限度的连结，被定义为没有孤立点存在的网络，其连线的个数为 n-P， 此时的β指数为

β1 =

n − P (5)

n

如果地理网络不包含次级亚网，即 P＝1，则其最低限度连接的β指数

值为1 - 1 。

n

  1. 回路数。通过前面的介绍，我们知道回路是一种闭合路径，其始点同时为终点。除非联线连接两个亚网络，回路就可能存在。如果网络内存在回路，则连线的数目就必须超过 n-P，因为这个数目定义着一个最低限度的连接网。那么回路数目为实际连线数目减去最低限度连结的联线数目，即

k=m-n+P （6)

  1. α指数。α指数是测度网络回路的指标，它是网络中实际回路的观察数与网络内可能存在的回路最大数目之间的比率。在任何接点超过 2 的网络中，增添一个额外接点，增加的最多连线数为 3。因此，一个网络的连线的最大可能数目为：3（n-2P)。所以，网络内可能存在的回路最大数目为联线的最大可能数目减去最低限度连结的联线数目，即

3（n-2P)-（n-P)

=2n-5P

所以α指数为

m − n + P

α = 2n − 5P

(7)

α指数的变化范围介于[0，1]区间，α＝0 意味着网络中不存在回路； α＝1，说明网络中已达到最大限度的回路数目。α指数亦可用百分率来表示，即

m − n + P

α = 2n − 5P

×100% (8)

4)γ指数。γ指数是网络内连线的实际观察数与连线可能存在的最大数目之间的比率，即

m

γ = 3(n − 2P)

（9）

γ指数是测度网络连通性的一种度量指标，其数值变化范围为 0≤γ≤1。γ

＝0，表示网络内无连线，只有孤立点存在；γ =1，则表示网络内每一个接点都存在与其它所有接点相连的连线。γ指数亦可以用百分比来表示，即

m

γ = 3(n − 2P) ×100%

(10)

表 7-1 给出了网络图 7-4 中（a)，（b)，（c)，（d)四个不同网络的有关测度指标。

通过对以上四个不同的测度指标的计算和分析，不但使我们比较容易地定量地了解我们所研究的地理网络的一些基本特征，如网络的复杂性程度、连通性状况等，而且还可以通过这些指标间接地反映该网络所描述的地理系统的其它内容。譬如，通过对一个国家或地区交通网络的β指数的计算和分析，我们不但可以了解该国家或地区交通网络的连通性和复杂性，同时由于交通网络的连通性和复杂性也是一个国家或地区的社会经济发展状况的反映，因而