在由许多项目组成的大型工程中,用顶点表示项目,有向边表示项目之间谁先开工的先后关系,这种用顶点表示活动的图称为AOV网络,其常用的一种存储结构是(40)。为规划整个工程的实现,通常要对上述图的顶点进行(41)排序,据此可获得项目的(42)序列。

admin2009-02-15  37

问题 在由许多项目组成的大型工程中,用顶点表示项目,有向边表示项目之间谁先开工的先后关系,这种用顶点表示活动的图称为AOV网络,其常用的一种存储结构是(40)。为规划整个工程的实现,通常要对上述图的顶点进行(41)排序,据此可获得项目的(42)序列。

选项 A、全序
B、综合
C、拓扑
D、优化

答案C

解析 所有的工程或者某种流程可以分为若干个小的工程或阶段,这些小的工程或阶段就称为活动。若以图中的顶点来表示活动,有向边表示活动之间的优先关系,则这样活动在顶点上的有向图称为AOV网。在AOV网中,若从顶点i到顶点j之间存在一条有向路径,称顶点i是顶点j的前驱,或者称顶点j是顶点i的后继。若<i,j>,是图中的弧,则称顶点i是顶点j的直接前驱,顶点j是顶点i的直接后继。AOV网中的弧表示了活动之间存在的制约关系。在AOV网络中不能出现有向回路,即有向环。如果出现了有向环,则意味着某项活动应以自己作为先决条件。因此,对给定的AOV网络,必须先判断它是否存在有向环。检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列,使得AOV网络中所有应存在的前驱和后继关系都能得到满足。这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中,则该网络中必定不会出现有向环。
转载请注明原文地址:https://kaotiyun.com/show/IoLZ777K
0

最新回复(0)