1、地理网络的地理网络的图论描述图论描述 地理网络地理网络 的测度的测度网络分析网络分析是运筹学的一个重要分支，它主要运用图论方法研究各类网络的结构及其优化 问题 ， 是 计量地理学必不可少的重要方法之一。 对于许多现实的地理问题， 譬如 城镇体系 问题、城市地域结构问题、交通问题、商业网点布局问题、物流问题、管道运输问题、供电与通讯线路问题 等等，都可以运用网络分析方法进行研究。最短路径与最短路径与选址问题选址问题 最大流最大流 与最与最小小 费用流费用流地理网络的图论描述地理网络的图论描述“ 图图 ” (Map/Picture/Graphic/Image/Chart/Drawing/Paint
2、ing)通俗意义 上， 主要是指各种各样的地图、遥感影像图，或者是由各种符号、文字代表的示意图，或者是由 各种数据 绘制而成的曲线图、 直方图等等 。图论图论 中的 “ 图图 ” (Graph)是一 个纯粹的数学 概念 ，能 从数学本质上揭示地理实体与地理事物 空间分布格局 ，地理要素之间的 相互联系 以及它们在地域空间上的 运动形式 、地理事件发生的 先后顺序 等。 （一）图的定义（一）图的定义图图 ： 设 V是一个由 n个点 vi (i=1， 2， ， n)所组成的集合 ，即 V=v1， v2， ， vn； E是一个由 m条线 ei（ i=1， 2， ， m） 所组成的集合 ，即 E=e1
3、， e2， ， em；而且 集合 E中任意一条线，都是 以 集合 V中的点为端点 ；而且 任意 两条线除了端点外没有其他的公共 点或交叉点 。那么 ，把 V与 E结合在一起就构成了一个图 G，记 作G (V, E)图 G由 点集合 V与 线集合 E构成V不允许是空集 E可以是空集（一）图的定义（一）图的定义顶点顶点 ： 点集合 V中的每一个点 vi（ i=1， 2， ， n） 称为图 G的顶点 。边边 ：线集合 E中每一条线称为图 G的 边（或弧）；若一条边 e连接u， v两个顶点，则记为 e (u, v)。例 ：在 如 下 图所 示的图中，顶点 集合为 V v1， v2， v3， v4， v
4、5， v6，v7， v8 ，边 集合为 E e1， e2， e3， e4， e5， e6， e7， e8， e9， e10， e11 。（一）图的定义（一）图的定义在现实地理系统中，对于地理位置、地理实体、地理区域以及它们之间的相互联系，可以经过一定的 简化与抽象简化与抽象 ，将它们描述为图论意义下的地理网络，即图。 地理位置、地理实体、地理区域，譬如，山顶、河流汇聚点、车站、码头、村庄、城镇等点点它们之间的相互联系，譬如，构造线、河流、交通线、供电与通讯线路、人口流、物质流、资金流、信息流、技术流等线线点与点的 连线一个由基本流域单元组成的复杂的 流域地貌系统 ，如果舍弃各种复杂的地貌 形态
5、： 各条河流 线河流分岔或汇聚处 点 河流水系网络河流水系网络（一）图的定义（一）图的定义列昂纳德列昂纳德 欧拉欧拉 哥尼斯堡七桥哥尼斯堡七桥 问题问题 东普鲁士 的哥尼斯堡城（现在的加里宁格勒）是建在两条河流的汇合处以及河中的两个小岛上的，共有 7座小桥将两个小岛及小岛与城市的其他部分连接起来，那么，哥尼斯堡人从其住所出发，能否恰好只经过每座小桥一次而返回原处？图论研究结果告诉我们，其答案是否定的。（一）图的定义（一）图的定义需要说明的是：图的定义只关注点之间是否连通，而不关注点之间的连结方式。对于任何一个图 ，它的 画法并不唯一。 图仅定义了节点之间是否存在连接的逻辑关系，而不涉及具体的连
6、接方式（二）图的（二）图的 一些一些 相关概念相关概念 （ 1） 无向图 与 有向图 ： 无向图 图的每条边都没有给定方向，即（ u， v）（ v， u） ；有向图 图的每条边都给定了方向，即（ u， v） （ v， u） 。有向图一般将有向图的边集记为 A， 无向图的边集记为 E。 这样， G=（ V， A） 就表示 有向图 ，而G=（ V， E） 则表示 无向图 。（二）图的（二）图的 一些一些 相关概念相关概念 （ 2） 赋权图 ：图的定义中并没涉及点和线的差异性，即所有的点和所有的线认为是无差异的，为体现点和线的实际区别，可以分别为点和线赋予权值 来实现， 这样的图 G称为 赋权图赋权
7、图 。 为图 G (V, E)中 的每一条 边 (vi, vj)都 相应地 赋一 个数值 wij， 其中 wij称为 边 (vi, vj)的 权值。为线赋权为点赋权 对于图 G中的每一顶点 vj， 也可以赋予一个载荷a(vj)，其中 a(vj)称为点 vj的权值。在同一个图 G中，可以同时为顶点和连接边都赋权值，并且， 可以为顶点和连接边赋予超过一个以上的的不同权重值 。（二）图的（二）图的 一些一些 相关概念相关概念 （ 3） 关联边 ：若 e (u,v)， 则称 u和 v是边 e的端点， e是 u和 v的关联边。 （ 4） 环 ： 若 连接边 e的两个端点相同，即 u v，则 称 e为环。 （ 5） 多重边 ：若 连接相同两 个端点的边多于一条以上，则称为多重边。 （ 6） 多重图 ：含有多重边的图，称为多重图。（ 7） 简单图 ：无环、无多重边的图，称为简单图。图的两个特殊结构
