2019/8/19 图

图中的关键路径的学习和研究：
对一个有向无环图DAG（Directed Acyclic Graph）进行拓扑排序，就是得到一个具有点的先后顺序的线性序列。在工程中具有比较重要的应用意义。通过拓扑排序后的序列，我们可以得到哪些子工程必须要先执行，哪些必须要在某些工程之后执行。可以采用有向图来反映这种关系，其中有向图的顶点被称之为事件（子工程），有向的边被称为活动，这样的图也被叫做AOE网（Activity On Edge network）。
AOE网和AOV网的区别就是在于边是否具有权值，如果有权值就是AOE网。
AOE网研究的问题主要有两个：

1. 完成整个工程所需要的时间。
2. 哪些活动是影响工程进度的关键。
   名词解释：
3. 关键路径：AOE网中，从起点到终点最长的路径的长度（长度是指路径上的权重之和）
4. 关键活动：关键路径的边。
5. 源点：入度为0的点。
6. 汇点：出度为0的点。
7. 事件Vk的最早发生时间Ve(k)：从源点V到Vk的最长路径长度。前到后
8. 事件Vk的最晚发生时间Vl(k)：从汇点V到Vk的最短路径长度。后到前
9. 活动ai的最早开始时间e(i)：表示时间最早发生的时间，和对应起点的结点的最早发生时间相同。
10. 活动ai的最迟开始时间l(i)：表示时间最迟发生时间和该活动所需要的时间的差值，对应终点的最迟发生时间减该边的权值。
11. 活动完成的时间余量d(i)：最早开始时间和最晚开始时间的差值。

该图片中分析可以得到源点为V1，汇点为V6，以及其他的答案以图片表格形式给出。

根据时间余量可以得到关键路径，所有的时间余量为0的对应的结点就是该AOE图所对应的关键路径。所以关键路径为：(V1,V3,V4,V6)