问答题
已知AOE网中顶点υ1，υ2，υ3，…υ7分别表示7个时间，有向线段α1，α2，α3，…α1。分别表示10个活动，线段旁的数值表示每个活动花费的天数，如下图所示。请填写下面两个表格，并用顶点序列表示出关键路径，给出关键活动。
【正确答案】[解答]
关键路径：V1 V2 V5 V7
V1 V4 V5 V7
关键活动：a1 a2 a4 a8 a9
| 事件 | V1 | V2 | V3 | V4 | V5 | V6 | V7 |
| 最早发生时问 | 0 | 3 | 2 | 6 | 7 | 5 | 10 |
| 最晚发生时间 | 0 | 3 | 6 | 7 | 6 | 10 |
| 活动 | a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 | a10 |
| 最早开始时间 | 0 | 0 | 0 | 3 | 3 | 2 | 2 | 6 | 7 | 5 |
| 最晚开始时间 | 0 | 0 | 1 | 3 | 4 | 5 | 3 | 6 | 7 | 6 |
| 时问余量 | 0 | 0 | 1 | 0 | 1 | 3 | 1 | 0 | 0 | 1 |
V1 V4 V5 V7
关键活动：a1 a2 a4 a8 a9
【答案解析】[解析] AOE网中从源点到终点的最大路径长度(这里的路径长度是指该路径上的各个活动所需时间之和)的路径称为关键路径。关键路径长度是整个工程所需的最短工期。关键路径上的活动称为关键活动。要缩短整个工期，必须加快关键活动的进度。
寻找关键活动时所用到的几个参量的定义。
假设第i条弧为＜j，k＞，dut(＜j，k＞)为弧＜j，k＞上的权值。
(1)事件的最早发生时间ve[k]=从源点到顶点k的最长路径长度。
ve(源点)=0；
re(k)=Max{ve(j)+dut(＜j，k＞)}
(2)事件的最迟发生时间vl[j]=从顶点j到汇点的最短路径长度。
vl(汇点)=ve(汇点)；
vl(j)=Min{vl(k)-dut(＜j，k＞)}
(3)活动i的最早开始时问e(j)=ve(j)。
(4)活动i的最晚开始时问l(i)=vl(k)-dut(＜j，k＞)。
e[i]=l[i]的活动就是关键活动，关键活动所在的路径就是关键路径。
寻找关键活动时所用到的几个参量的定义。
假设第i条弧为＜j，k＞，dut(＜j，k＞)为弧＜j，k＞上的权值。
(1)事件的最早发生时间ve[k]=从源点到顶点k的最长路径长度。
ve(源点)=0；
re(k)=Max{ve(j)+dut(＜j，k＞)}
(2)事件的最迟发生时间vl[j]=从顶点j到汇点的最短路径长度。
vl(汇点)=ve(汇点)；
vl(j)=Min{vl(k)-dut(＜j，k＞)}
(3)活动i的最早开始时问e(j)=ve(j)。
(4)活动i的最晚开始时问l(i)=vl(k)-dut(＜j，k＞)。
e[i]=l[i]的活动就是关键活动，关键活动所在的路径就是关键路径。