lecture9网络分析

1、空间网络分析空间网络分析 空间对象分类看得见的线状分布：如河流、道路、铁路、输电线路、供水管道、政区边界等。上述线状分布在三维空间中是实际存在的，是看得见，摸得着的；看不见的线状分布：如地理区域之间、城市之间、工厂之间的联系，无线通讯网和航空线路等。这些线状分布是不可见的，只有通过设计和调查在相关图件上加以表达。 无论是何种线状分布，它们都是通过线连接在点上的。这些点称为顶点或节点，两个点之间的线称为环、弧或边，节点和环线系统就称为网络。节点和环线是构成网络的两个基本要素。空间网络的类型空间网络的拓扑分类平面网络（二维）非平面网络（非二维）线型“流”系统线型栅格系统线型立体系统道路型树型环网型

2、细胞型交错型网络图基本概念网络图基本概念有向图和无向图路与回路路与回路图中的一条路，就是由图中的一个顶点、一条边，再一个顶点、一条边排列而成，而且要求排在它前面的顶点和排在它后面的顶点都是它的端点。对于有向路来说，要求排在每一条边之前和之后的顶点分别是这条边的起点和终点 连通性连通性如果无向图内任意两个顶点之间存在着一如果无向图内任意两个顶点之间存在着一条连接它们的路，则称这个无向图是连通条连接它们的路，则称这个无向图是连通的，如图的，如图5-22(a)，反之，则称为不连通，反之，则称为不连通的，如图的，如图5-22(b)。连通性也可以用来研。连通性也可以用来研究有向图。一个有向图，如果不考虑

3、它的究有向图。一个有向图，如果不考虑它的边的方向，如果它是连通的，则称这个有边的方向，如果它是连通的，则称这个有向图是连通的；如果在一个有向图中，它向图是连通的；如果在一个有向图中，它的任意两个顶点都存在着一条连接它们的的任意两个顶点都存在着一条连接它们的有向路，那么这个有向图就称为具有强连有向路，那么这个有向图就称为具有强连通性。图通性。图5-22(c)是不连通图，而图是不连通图，而图5-22(d)则是强连通图。则是强连通图。网络图的矩阵表达 邻接矩阵：G的顶点集V中每两点间的邻接关系唯一确定。（顶点与顶点之间的邻接关系） dij=1 Vi 和Vj邻接 dij=0 Vi和Vj不邻接 关联矩阵

4、：G的v个顶点和e条边的无向关联矩阵。（顶点与边之间的关联关系） aij=1 ei 和Vj邻接 bij=0 ei和Vj不邻接路径分析 n1）静态求最佳路径：在给定每条链上的属性后，求最佳路径。n2）N条最佳路径分析：确定起点或终点，求代价最小的N条路径，因为在实践中最佳路径的选择只是理想情况，由于种种因素而要选择近似最优路径。n3）最短路径或最低耗费路径：确定起点、终点和要经过的中间点、中间连线，求最短路径或最小耗费路径。n4）动态最佳路径分析：实际网络中权值是随权值关系式变化的，可能还会临时出现一些障碍点，需要动态的计算最佳路径。路径分析路径分析例题路径分析（path analysis） 迪

5、克斯查（E.W.Dijkstra）提出的标号法是解决最短路径问题最好的方法。这个方法的突出优点是：它不仅求出了起点到终点的最短路径及其长度，而且求出了起点到图中其它各顶点的最短路径和长度。路径分析：n设 是一个有向图的网络，对于它的每条边或每一对顶点都可以对应一个数。在实际应用过程中，对于 的取值是这样规定的：n1.如果边以 为起点， 为终点，则取这个边的长度；n2.如果顶点 不是某一条边为起点和终点，那么取值为：n3.如果 ，取值为0。Gjivv ,),(jivvMivjvjivv 标号法过程v1v2v3v4v5v6V7v8v10 12V210333V323024V4320233V53203

6、V63301V7101v84310W=v1v2v3v4v5v6V7v8起点0() () () () () () ()v10 (1)(2)() () () () ()V201(2)(4)(4)() () ()V3012(4)(4)() ()(6)V40124(4)(7)()(6)V501244(7)()(6)V801244(7)(7)6v701244(7)76标定定位配置分析(location-allocation analysis )服务点的最优区位问题 在城市管理中，利用GIS技术确定服务点的最优区位问题十分重要，如确定幼儿园、商场、消防队、医院、交通场站等的最优位置，以达到服务、资源的最优

7、配置。最优服务点的最优区位问题有两种算法供选择 服务点的最优区位问题算法1n设G是一个n有个顶点： m条边： 的无向连通图，那么对于每一个顶点，它与各顶点间的最短路径的长度为： 最大数称为顶点的最大服务距离，用 表示 ,.,21nvvvV ,.,21meeeE iniiddd,.,21iniiddd,.,21)(ive服务点的最优区位问题算法1求出一个点 使得 具有最小的值。这样处理数据的含义是很明显的。因为在图上找出这个 点后，把服务点设在这个位置上，对于分散在各个顶点上的服务对象来说，最远的服务对象与服务点之间的距离达到了最小。这个点称为图的中心。 0iv)(0ive0iv首先计算出的距离

8、表最后求 ，定出 均是G的中心 027474205256750343423036754303463630其次，计算每一行的最大值 , 7)(, 6)(, 7)(, 6)(, 7)(, 6)(654321veveveveveve6)(min61ivei531,vvv服务点的最优区位问题算法2 设G是一个n有个顶点： m条边： 的无向连通图，那么对于每一个顶点，它与各顶点间的最短路径的长度为： 并设每个顶点有一个正负荷 。现求出一个顶点，使得 最小，此点被认为是G点的中央点 ,.,21nvvvV ,.,21meeeE iniiddd,.,21nivai,.,2 , 1),(njjijidvavS1

9、,)()(首先，计算G的距离方阵其次求出05 . 13 . 63 . 35365 . 108 . 48 . 15 . 35 . 15 . 43 . 68 . 40353 . 63 . 93 . 38 . 13023 . 33 . 635 . 35202535 . 13 . 63 . 320365 . 43 . 93 . 65303 .95)(8 .72)(5 .108)(5 .69)(5 .69)(3 .71)(3 .122)(7654321vSvSvSvSvSvSvS 最后得到的中央点是 和 3v4vP-中心问题 在m个候选点中选择p个供应点，为n个需求点服务，并使得服务中心到各个需求点之间

10、的总距离(时间，费用)为最小。可以描述为：111min()nmijijijw dx111mijjmjxypTeitz-Bart算法p选取选取p个候选点作为起始供应点集个候选点作为起始供应点集Pt:C1,C2,.Cpp将所有的需求点分配给他们最临近的供应点，使其距离最短。计算总的将所有的需求点分配给他们最临近的供应点，使其距离最短。计算总的加权距离加权距离Btp从未选取的候选点中选取一候选点从未选取的候选点中选取一候选点Cbp对对Pt中的每个供应点中的每个供应点Cj用用Cb替换之，并计算总加权距离的变化替换之，并计算总加权距离的变化p如果供应点如果供应点Cj用用Cb替换后总加权距离减少，那么就替换总加权距离减少替换后总加权距离减少，那么就替换总加权距离减少最多的供应点。最多的供应点。p重复重复3-5步，直至未被选取的点集为空步，直至未被选取的点集为空p当所有不在当所有不在Pt中的候选点试过后其结果记为中的候选点试过后其结果记为Ptp重复重复2-7步，直到总加权距离不变为止步，直到总加权距离不变为止中心服务范围的确定中心服务范围为满足下列条件的网络边和结点的集合：,iiciijicijiFv rcw vre rwcw vr