第三章空间分布的测度(修改1).ppt

第三章 空间分布的测度 空间分布的测度 空间分布的类型 点状分布的测度 线状分布……网络 面状分布的测度 (一) 地理网络的图论描述 1、地理网络的图论描述 2、地理网络的测度 通俗意义上的“图”，主要是指各种各样的地图、遥感影像图，或者是由各种符号、文字代表的示意图，或者是由各种地理数据绘制而成的曲线图、直方图等等。 1、地理网络的图论描述 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中的点为端点；任意两条线除了端点外没有其他的公共点。 列昂纳德·欧拉——7桥问题 7）需要说明的是：图的定义只关注点之间是否连通，而不关注点之间的连结方式。对于任何一个图，他的画法并不唯一。 （2）图的一些相关概念 1）无向图与有向图： 无向图——图的每条边都没有给定方向， 即（u，v）＝（v，u）；有向图——图的每条边都给定了方向， 即（u，v）≠（v，u）。 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）连通图。在图G中，若任何两点之间至少存在一条路（对于有向图，则不考虑边的方向），则称G为连通图，否则称为不连通图。 5）回路：若一条路的起点与终点相同，即vi1=vik，则称它为回路。 6）基础图：从一个有向图D＝（V，A）中去掉所有边上的箭头所得到的无向图，就称为D的基础图，记之为G（D）。 2、地理网络的测度 （1）关联矩阵 测度网络图中顶点与边的关联关系。 假设网络图G＝（V，E）的顶点集为V={v1，v2，…，vn}，边集为E={e1，e2，…，em}，则该网络图的关联矩阵就是一个n×m矩阵，可表示为 测度网络图中各顶点之间的连通性程度。 假设图G＝（V，E）的顶点集为V={v1，v2，…，vn}，则邻接矩阵是一个n阶方阵，可表示为 （二） 最短路径与选址问题 对于许多地理问题，当它们被抽象为图论意义下的网络图时，问题的核心就变成了网络图上的优化计算问题。其中，最为常见的是关于路径和顶点的优选计算问题。 在路径的优选计算问题中，最常见的是最短路径问题；而在顶点的优选计算问题中，最为常见的是中心点和中位点选址问题。 1、最短路径问题 “纯距离”意义上的最短路径 例如，需要运送一批物资从一个城市到另一个城市，选择什么样的运输路线距离最短？ “经济距离”意义上的最短路径 例如，某公司在10大港口C1，C2，…，C10设有货栈，从Ci到Cj之间的直接航运价格，是由市场动态决定的。如果两个港口之间无直接通航路线，则通过第三个港口转运。那么，各个港口之间最廉价的货运线路是什么？ “时间”意义上的最短路径 例如，某家经营公司有一批货物急需从一个城市运往另一个城市，那么，在由公路、铁路、河流航运、航空运输等4种运输方式和各个运输线路所构成的交通网络中，究竟选择怎样的运输路线最节省时间？ （2）最短路径的算法 标号法 1959年E.W.Dijkstar 提出的标号法是最短路径问题最好的求解方法 。 标号法优点 不仅可以求出起点到终点的最短路径及其长度，而且可以求出起点到其他任何一个顶点的最短路径及其长度；同时适用于求解有向图或无向图上的最短路径问题。. 标号法具体计算步骤 ① 如果刚刚得到P标号的点是vi，那么，对于所有这样的点 将其T标号修改为：min[T(vj)，P(vi)+wij]。 ② 若G中没有T标号，则停止。否则，把点 vj0 的T标号修改为P标号，然后再转入①。 其中， vj0满足 2、选址问题 选址问题，是现代地理学研究的主要问题之一。选址问题涉及人类生产、生活、文化、娱乐等各个方面。 选址问题的数学模型取决于两个方面的条件 ：可供选址的范围、条件；怎样判定选址的质量。 本节