|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
对地理网络（如交通网络）、城市基础设施网络（如各种网线、电力线、电话线、供排水管线等）进行地理分析和模型化，是GIS中网络分析功能的主要目的。
分析和解决网络模型的有力工具是图论, 在此介绍了网络分析中几个概念：图、有向图、回路、连通图、树及其性质，赋权图。
GIS中的路径分析包含了最短路径分析、最小生成树、最小费用最大流等问题：
(一)、最短路径分析
在最短路径选择中，两点之间的距离可以定义为实际的距离，也可定义为两点间的时间、运费、流量等，可定义为使用这条边所需付出的代价。因此，可以对不同的专题内容进行最短路径分析。下面介绍的最短路径搜索的算法是狄克斯特拉（Dijkstra）在1959年提出的，被公认为是最好的算法之一。它的基本思想是:把图的一了页顶点分为S,T两类,若起始点u到某顶点x的最短通路己求出,则将x归入S,其余归入T,开始时S中只有u,随着程序运行,T的元素逐个转入S, 直到目标顶点v转入后结束。(最短路径的详细算法)
(二)、最小生成树
生成树是图的极小连通子图。一个连通的赋权图G可能有很多的生成树。设T为图G的一个生成树，若把T中各边的权数相加，则这个和数称为生成树T的权数。在G的所有生成树中，权数最小的生成树称为G的最小生成树。
在实际应用中，常有类似在n个城市间建立通信线路这样的问题。这可用图来表示，图的顶点表示城市，边表示两城市间的线路，边上所赋的权值表示代价。对n个顶点的图可以建立许多生成树，每一棵树可以是一个通信网。若要使通信网的造价最低，就需要构造图的最小生成树。(最小生成树生成的算法)
在地理网络中进行着物质和能量的流动，形成各种各样的流。
设有一个水管网络，只有一个进水口和一个出水口。每个管道用其截面积作为权数，用于反映单位时间内可能通过的最大流量(称为容量)。有稳定水流注入进水口，经过网络从出水口流出。这样的一个稳定的流动称为“流”，具有如下性质：
1）流是有向的。
2）管道的流量不可能超过最大流量。
3）每个内部节点处流入和流出节点的流量相等。
4）进水口的流量等于出水口的流量。
最大流问题讨论的是，在一个地理网络中怎样安排网上的流，使从发点到收点的流量最大。在实际应用中，不仅要考虑使网络上的流量最大，而且要使运送流的费用或代价最小。这就是最小费用最大流量问题。(最小费用最大流的具体算法)。
定位与分配模型是根据需求点的空间分布，在一些候选点中选择给定数量的供应点以使预定的目标方程达到最佳结果。不同的目标方程就可以求得不同的结果。在运筹学的理论中，定位与分配模型常可用线性规划求得全局性的最佳结果。由于其计算量以及内存需求巨大，所以在实际应用中常用一些启发式算法(heuristic algorithms)来逼近或求得最佳结果。在众多的启发算法中以下两个算法是常用的：
(一)、用来解决P—中心的定位分配问题的Teitz-Bart算法
(二)、引入全局和区域性算法的Densham-Rushton算法