求真百科歡迎當事人提供第一手真實資料,洗刷冤屈,終結網路霸凌。

AOE网查看源代码讨论查看历史

跳转至: 导航搜索
AOE网

中文名: AOE网

外文名: Activity On Edge Network

形 式: 图

目 的: 描述和分析工程的计划和过程

在现代化管理中,人们常用有向图来描述和分析一项工程的计划和实施过程,一个工程常被分为多个小的子工程,这些子工程被称为活动(Activity),在带权有向图中若以顶点表示事件,有向边表示活动,边上的权值表示该活动持续的时间,这样的图简称为AOE网[1] 一个无环的有向图称作有向无环图(directed acyclic graph),简称DAG图。假设以有向图表示一个工程的施工图或程序的数据流图,则图中不允许出现回路,如果出现回路,说明了某项活动以它自己为先决条件,显然是荒谬的,工程将无法进行。  

拓扑排序

拓扑排序是一种对非线性结构的有向图进行线性化的重要手段。在给定的有向图G中,若顶点序列Vi1,Vi2,Vi3,....,Vin,。满足下列条件:若在有向图G中从顶点Vi,到顶点Vj有一条路径,则在序列中顶点Vi必在顶点Vj之前,便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。 拓扑排序的方法如下: (1)从图中选择一个入度为O的顶点并输出; (2)从图中删掉该顶点及其所有以该顶点为弧尾的弧。 反复执行这两个步骤,直到所有的顶点都被输出,输出的序列就是这个无环有向图的拓扑序列。 如果在带权有向图中,用顶点表示事件,用有向边表示活动,边上的权值表示活动的开销,则此带权有向图称为边活动网(activity on edge network),简称AOE网。AOE网是一个有向无环图。AOE网是用来描述由许多交叉活动组成的复杂计划和工程的方法,比如某工程的AOE网。 在工程中用边表示活动,边上的权表示完成这项活动所需要的时间,顶点表示某项活动的开始,顶点1称为源点(或起点),表示整个工程开始,顶点2称为汇点(或终点),表示整个工程的结束。用AOE网来估算工程的最短工期(完成整个工程至少需要多少时间)以及哪些活动是影响工程进展的关键。  

几个术语

路径长度:路径上各活动持续时间的总和(即路径上所有权之和)。 完成工程的最短时间:从工程开始点(源点)到完成点(汇点)的最长路径称为完成工程的最短时间。 关键路径:路径长度最长的路径称为关键路径。

性质

(1)只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始。 (2)只有在进入某点的各有向边所代表的活动都已结束,该顶点所代表的时事件才能发生。 关键路径(临界路径):在AOE网络中从源点到汇点(结束顶点)的最长路径。关键路径上的活动为关键活动。  

参考来源

  1. [1],搜狗百科 ,