网络结构模型

网络空间

网络拓扑系统研究的创始人被公认为数学家Leonard Euler,他在1736年解决了当时一个著名的问题,叫做Konigsberg桥问题。图3-16-a显示了该桥的一个概略的路线图。该问题就是找到一个循环的路,该路只穿过其中每个桥一次,最后返回到起点。一些实验表明这项任务是不可能的,然而,从认为没有这样的路线到说明它的步骤并不是这样容易的。

../../_images/img_12.jpg

Konigsberg Park中的图形理论模型

Euler成功地证明了这是一项不可能的任务;或者,换一句话来说,这个问题是没有解的。为了做这件事,他建立了该桥的一个空间模型,该模型抽象出了所有的仅有的桥之间的拓扑关系,见图3-16-b。实心圆表示结点或顶点。它们被标上w、x、y、z,并且抽象为陆地面。线表示弧段或边线,它们抽象为陆地之间的直线,并且在每种情况下需要使用一个桥,完整的模型叫做网络或图形。Euler证明了不可能从一个结点开始,沿着图形的边界,遍历每个边界只有一次,最后到达第一个结点。他所采用的论点是非常简单的,依据的是经过每个结点的边的奇数/偶数。我们看到:除了开始的结点和末端的结点外,经过一个结点的路径必须是沿着一个边界进入,又沿着另一个边界出去。这说明了两个边界对应着那个结点。因此,如每个中间结点相连的边界的数量必须是偶数,当然,如果这个问题是有解的话。图3-15中,没有一个结点的边界数是偶数的。因此,这个图论的问题是没有解的,并且与Konigsberg桥问题有关的最初的问题也是无解的。

网络模型

在网络模型中,地物被抽象为链、节点等对象,同时要关注其间连通关系。基于网络的空间模型与基于要素的模型在一些方面有共同点,因为它们经常处理离散的地物,但是最基本的特征就是需要多个要素之间的影响和交互,通常沿着与它们相连接的通道。相关的现象的精确形状并不是非常重要的,重要的是具体现象之间距离或者阻力的度量。网络模型的典型的例子就是研究交通,包括陆上、海上及航空线路,以及通过管线与隧道分析水、汽油及电力的流动。例如,一个电力供应公司对它们的设施管理可能既采用了一个基于要素的视点,同时又采用了一个基于网络的视点,这依赖于他们关心的是否是替换一个特定的管道,在这种情况下,一个基于要素的视点可能是合适的;或者例如他们关心的是分析重建线路的目的,在这种情况下,网络模型将是合适的。

网状模型的基本特征是,结点数据间没有明确的从属关系,一个结点可与其它多个结点建立联系。网状模型将数据组织成有向图结构。结构中结点代表数据记录,连线描述不同结点数据间的关系。有向图(Digraph)的形式化定义为:

Digraph = (Vertex,{Relation})

其中Vertex为图中数据元素(顶点)的有限非空集合;Relation是两个顶点(Vertex)之间的关系的集合。

有向图结构比树结构具有更大的灵活性和更强的数据建模能力。网状模型可以表示多对多的关系,其数据存储效率高于层次模型,但其结构的复杂性限制了它在空间数据库中的应用。

网状模型反映了现实世界中常见的多对多关系,在一定程度上支持数据的重构,具有一定的数据独立性和共享特性,并且运行效率较高。但它在应用时也存在以下问题:

.网状结构的复杂,增加了用户查询和定位的困难。它要求用户熟悉数据的逻辑结构,知道自身所处的位置。

.网状数据操作命令具有过程式性质。

.不直接支持对于层次结构的表达。

.基本不具备演绎功能。

.基本不具备操作代数基础。