第10章 地理网络分析——第1节 地理网络的图论描述.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第十章 网络分析方法,对于许多现实的地理问题，譬如，城镇体系问题，城市地域结构问题，交通问题，商业网点布局问题，物流问题，管道运输问题，供电与通讯线路问题，等等，都可以运用网络分析方法进行研究。,网络分析，是运筹学的一个重要分支，它主要运用图论方法研究各类网络的结构及其优化问题。,网络分析方法是计量地理学必不可少的重要方法之一。,本章主要内容：,地理网络的图论描述,最短路径与选址问题,最大流与最小费用流,10.1,地理网络的图论描述,通俗意义上的“图”，,主要是指各种各样的地图、遥感影像图，或者是由各种符号文字代表的示意图，或者是由各种地理数据绘制而成的曲线图、直方图，等等。,图论中的“图”,，是一个数学概念，这种“图”能从数学本质上揭示地理实体与地理事物空间分布格局，地理要素之间的相互,联系,以及它们在地域空间上的运动形式，地理事件发生的先后顺序，等等。,（1）图：,设,V,是一个由,n,个点,v,i,(,i,=1，2，,n,),所组成的集合，即,V,=,v,1,，,v,2,，,v,n,，,E,是一个由,m,条线,e,i,（,i,=,1,，,2,，,m,）,所组成的集合，即,E,=,e,1,，,e,2,，,e,m,，,而且,E,中任意一条线，都是以,V,中的点为端点；任意两条线除了端点外没有其它的公共点。,一、地理网络的图论描述,（一）图的定义,那么，把,V,与,E,结合在一起就构成了一个,图,G,，,记作,G,（,V,，,E,）,。,（3）,边：,E,中每一条线称为,图,G,的边,（或,弧,）；若一条边,e,连接,u,，,v,两个顶点，则记为,e,（,u,，,v,）。,（2）,顶点：,V,中的每一个点,v,i,（,i,=1，2，,n,）,称为,图,G,的顶点,。,（4）,在图,G,（,V,，,E,）,中，,V,不允许是空集，但,E,可以是空集。,（5）,从以上定义可以看出，图包含两个方面的基本要素：,点集（或称顶点集）；边集（或称弧集）。,例,：在如图10.1.1所示的图中，,顶点集为,V,v,1,，,v,2,，,v,3,，,v,4,，,v,5,，,v,6,，,v,7,，,v,8,，,边集为,E,e,1,，,e,2,，,e,3,，,e,4,，,e,5,，,e,6,，,e,7,，,e,8,，,e,9,，,e,10,，,e,11,。,图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,）,中的每一条边（,v,i,，,v,j,）,都相应地赋有一个数值,w,ij,，,则称,G,为赋权图，其中,w,ij,称为边（,v,i,，,v,j,）,的权值。,除了可以给图的边赋权外，也可以给图的顶点赋权。这就是说对于图,G,中的每一顶点,v,j,，,也可以赋予一个载荷,a,(,v,j,)。,（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,v,i1,，,e,i1,，,v,i2,，,e,i2,，,e,ik-1,，,v,ik,满足,e,it,=(,v,it,，,v,i,，,t+1,)(,t,=,1,2,k-1,),则称,P,为一条从,v,i1,到,v,ik,的路（或链），简记为P,v,i1,，v,i2,，,，v,ik,。,（11）回路。,若一条路的起点与终点相同，即,v,i1,=,v,ik,，,则称它为回路。,（12）树。,不含回路的连通的无向图称为树。,（13）基础图。,从一个有向图,D,（,V,，,A,）,中去掉所有边上的箭头所得到的无向图，就称为,D,的基础图，记之为,G,（,D,）。,（14）截。,如果从图中移去边的一个集合将增加亚图的数目时，被移去的边的集合就称为截。,（15）子图。,设,G,（,V,，,E,）,是一个无向图，,V,1,与,E,1,分别是,V,与,E,的子集，即,V,1,V,，,E,1,E,。,如果对于任意,e,i,E,1,，,其两个端点都属于,V,1,，,则称,G,1,（,V,1,，,E,1,）,是图,G,的一个子图。,（16）支撑子图。,设,G,1,（,V,1,，,E,1,）,是图,G,（,V,，,E,）,的一个子图，如果,V,1,V,，,则称,G,1,是,G,的支撑子图。,（17）支撑树。,设,G,（,V,，,E,）,是一个无向图，如果,T,（,V,1,，,E,1,）,是,G,的支撑子图，并且,T,是树，则称,T,是,G,的一个支撑树。,（18）树的重量。,一个树的所有边的权值之和称为该树的重量。,（19）最小支撑树。,在一个图的所有支撑树中，重量最小的那个叫做该图的最小支撑树。,二、地理网络的测度,许多现实的地理问题，只要经过一定的简化和抽象，就可以将它们描述为图论意义下的地理网络，点和线的排布格局，并可以进一步定量化地测度它们的拓扑结构，以及连通性和复杂性。,树状型,地理网络,平面网络（二维的）,非平面网络（非二维的）,道路型,环状型,细胞型,图,10.1.5,地理网络的拓扑分类,目前关于地理网络的拓扑研究，最多、最常见的是基于平面图描述的二维平面网络。所谓平面图，被规定为：各连线之间不能交叉，而且每一条连线除顶点以外，不能再有其它的公共点（牛文元，1987）。以下的讨论，除非特别申明外，都限于二维平面网络。,（一）关联矩阵与邻接矩阵,关联矩阵,测度网络图中顶点与边的关联关系。假设网络图,G,（,V,，,E,）,的顶点集为,V,=,v,1,，,v,2,，,v,n,，,边集为,E,=,e,1,，,e,2,，,e,m,，,则该网络图的关联矩阵就是一个,n,m,矩阵，可表示为：,g,ij,为顶点,v,i,与边,e,j,相关联的次数。,v,3,v,1,v,2,v,4,v,5,e,1,e,2,e,3,e,4,e,5,e,6,e,7,该图的关联矩阵为：,例：,邻接矩阵,测度网络图中各顶点之间的连通性程度。假设图,G,（,V,，,E,）,的顶点集为,V,=,v,1,，,v,2,，,v,n,，,则邻接矩阵是一个,n,阶方阵，可表示为：,a,ij,表示连接顶点,v,i,与,v,j,的边的数目。,该图的邻接矩阵为v,3,v,1,v,2,v,4,v,5,e,1,e,2,e,3,e,4,e,5,e,6,e,7,例：,（二）有关测度指标,指数,回路数,k,指数,指数,对于任何一个网络图，都存在着三种共同的基础指标：,连线（边或弧）数目,m,；,结点（顶点）数目,n,；,网络中亚图的数目,p,。,由它们可以产生如下几个更为一般性的测度指标,：,指数线点率，是网络内每一个节点的平均连线数目。,=0，,表示无网络存在；网络的复杂性增加，则,值也增大。,没有孤立点存在的网络，连线数目为,n-p,则,指数为,（1）,指数,如果地理网络不包含次级亚图，即,P1，,则其最低限度连接的 指数值为,。,(2)回路数,k,回路是一种闭合路径,它的始点同时也是终点。,若网络内存在回路，则连线的数目就必须超过,n-p,（,最低限度连接网络的连接数目）。,回路数,k,实际连线数目减去最低限度连接的连线数目，即,(3),指数,指数实际回路数与网络内可能存在的最大回路数之间的比率。,网络内可能存在的最大回路数目为连线的最大可能数目减去最低限度连接的连线数目，即,所以，,指数为,指数也可以用百分率表示,对于非平面网络，其 指数为,指数的变化范围，一般介于0，1区间，0意味着网络中不存在回路；1，说明网络中已达到最大限度的回路数目。,(4),指数,指数网络内连线的实际数目与连线可能存在的最大数目之间的比率，,对于平面网络，其计算公式为：,指数是测度网络连通性的一种指标，,其数值变化范围为0，1,。,0,，,表示网络内无连线，只有孤立点存在；,1,，,则表示网络内每一个节点都存在与其它所有节点相连的连线。,指数也可以用百分比表示,对于非平面网络，指数的计算公式为：,表10.1.1 几种简单网络图的有关测度指标,