地理网格表达与分析.pdf

地理网络表达与分析 地理网络表达与分析 陆陆 锋锋 010010--6644888888966966,, luluff@@lreilreiss..aacc..cncn 中国科中国科学学院地院地理科理科学与资学与资源源研究所研究所 .0044..1212 课程内容 课程内容 地理网络概念 网络表达的数学基础 地理网络表达与存储 地理网络建模特殊需求 地理网络分析类型与特征 地理网络表达与分析研究热点 网络与地理网络 网络与地理网络 工程化网络 工程化网络 社会关系网络 社会关系网络 计算机与通讯网络 （有线、无线） 计算机与通讯网络 （有线、无线） 地理网络 （交通、管网、电力、水系） 地理网络 （交通、管网、电力、水系） 地理网络：相互连接及作用的线状空间实体基 地理网络：相互连接及作用的线状空间实体基 本结构形式。 本结构形式。 地理网络要素的相互作用及能流、物流在网络 地理网络要素的相互作用及能流、物流在网络 上的传输，形成了丰富的地理与社会现象， 上的传输，形成了丰富的地理与社会现象， 且将地理实体有机地联系在一起。 且将地理实体有机地联系在一起。 网络表达的数学基础 网络表达的数学基础 图论的起源 图论的起源 Leonard Euler 1736 哥尼斯堡七桥问题 Leonard Euler 1736 哥尼斯堡七桥问题 一笔画的Euler原则： 偶点数可任意，奇点 只能是0或2个 图的定义 图的定义 Graph = V,E Graph = V,E – V ：节点集合 – V ：节点集合 – E ：两节点间关系的集合 – E ：两节点间关系的集合 图的基本概念 图的基本概念 – 有向图、无向图、子图 – 有向图、无向图、子图 – 节点数、边数 – 节点数、边数 – 起始节点、终止节点 – 起始节点、终止节点 – 邻接点 – 邻接点 – 节点的度、出度、入度 – 节点的度、出度、入度 – 路径，回路 – 路径，回路 示例：Euler图与Hamilton图 示例：Euler图与Hamilton图 给定无孤立顶点图G ，若存在一条经过每边仅一次的路径，称为 给定无孤立顶点图G ，若存在一条经过每边仅一次的路径，称为 Euler路；若存在经过每边仅一次的回路，称为Euler回路。具有 Euler路；若存在经过每边仅一次的回路，称为Euler回路。具有 Euler回路的图称作Euler图。 Euler回路的图称作Euler图。 图具有Euler路条件：连通，有0或2个顶点度数为奇数 图具有Euler路条件：连通，有0或2个顶点度数为奇数 图具有Euler回路条件：连通，所有结点度数为偶数 图具有Euler回路条件：连通，所有结点度数为偶数 给定无孤立顶点图G 若存在一条经过每个顶点恰好一次 给定无孤立顶点图G 若存在一条经过每个顶点恰好一次 的路径，称作Hamilton路。若存在一条经过每个顶点恰好 的路径，称作Hamilton路。若存在一条经过每个顶点恰好 一次的回路，称作Hamilton 回路。具有Hamilton回路的图 一次的回路，称作Hamilton 回路。具有Hamilton回路的图 称为Hamilton 图 称为Hamilton 图 实例：游览线路问题 旅游景点的线路规划及游客游览线路安排 有向图的连通性 有向图的连通性 1)