概念

有向无环图

一个无环的有向图称作有向无环图(directed acyclic graph)，简称DAG图。假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路，如果出现回路，说明了某项活动以它自己为先决条件，显然是荒谬的，工程将无法进行。1

拓扑排序

拓扑排序是一种对非线性结构的有向图进行线性化的重要手段。在给定的有向图G中，若顶点序列Vi1，Vi2，Vi3，....,Vin，。满足下列条件：若在有向图G中从顶点Vi，到顶点Vj有一条路径，则在序列中顶点Vi必在顶点Vj之前，便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。拓扑排序的方法如下：(1)从图中选择一个人度为O的顶点并输出；(2)从图中删掉该顶点及其所有以该顶点为弧尾的弧。反复执行这两个步骤，直到所有的顶点都被输出，输出的序列就是这个无环有向图的拓扑序列。

如果在带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的开销，则此带权有向图称为边活动网(activity on edge network)，简称AOE网。AOE网是一个有向无环图。AOE网是用来描述由许多交叉活动组成的复杂计划和工程的方法，比如某工程的AOE网。

AOE网

在工程中用边表示活动，边上的权表示完成这项活动所需要的时间，顶点表示某项活动的开始，顶点1称为源点（或起点），表示整个工程开始，顶点2称为汇点（或终点），表示整个工程的结束。用AOE网来估算工程的最短工期（完成整个工程至少需要多少时间）以及哪些活动是影响工程进展的关键。1

几个术语

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

关键路径：路径长度最长的路径称为关键路径。

性质

（1）只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。

（2）只有在进入某点的各有向边所代表的活动都已结束，该顶点所代表的时事件才能发生。

关键路径（临界路径）：在AOE网络中从源点到汇点（结束顶点）的最长路径。关键路径上的活动为关键活动。2

参考资料