有回路的有向图不存在拓扑排序。 Q 5V4 输出V1 输出V3 不能输出
V2 V6 V4 V3 V1 V5 V2 V6 V4 V3 V5 V2 V6 V5 V3 输出V1 输出V3 不能输出 有回路的有向图不存在拓扑排序
7.5.2关键路径 AOEp (Activity On Edge 是一个带权的有向无环图,其中以顶点表示事件,弧表 示活动,权表示活动持续的时间 当AOE网用来估算工程的完成时间时,只有一个开始点 (入度为0,称为源点)和一个完成点(出度为0,称为汇点) 2. d a7=9 a7 a5 a8-7 78al14 a6=2
7.5.2 关键路径 AOE网（Activity On Edge）： 是一个带权的有向无环图，其中以顶点表示事件，弧表 示活动，权表示活动持续的时间。 当AOE网用来估算工程的完成时间时，只有一个开始点 （入度为0,称为源点）和一个完成点（出度为0，称为汇点） V2 V1 V6 V3 V4 V5 V7 V8 V9
AOE网研究的问题: (1)完成整项工程至少需要多少时间; (2)哪些活动是影响工程进度的关键。 在AOE网中,部分活动可并行进行,所以完成工程的最 短时间是从开始点到完成点的最长路径长度。路径长度 最长的路径称为关键路径( Critical Path)
AOE网研究的问题： （1） 完成整项工程至少需要多少时间； （2） 哪些活动是影响工程进度的关键。 在AOE网中，部分活动可并行进行，所以完成工程的最 短时间是从开始点到完成点的最长路径长度。路径长度 最长的路径称为关键路径（Critical Path）
(顶点)事件v的最早发生时间ve(i): 从开始点到v的最长路径长度。(ve(v1)=0) 既表示事件vi的最早发生时间,也表示所有以ⅵi为尾的 弧所表示的活动ak的最早发生时间e(k)。(如下例的a7,a8) y2、 a a2=4 3a5=1 N5)8=7 了5 仅有一个前驱顶点: ve(v2)=ve(v1)+6=0+6=6 有多个前驱顶点: ve(v5)=max{ve(前驱顶点)+ ve(v3)=ve(v1)+4=0+6=4 前驱活动时间} ve(v4)=ve(v1)+6=0+5=5 =max{6+1,4+1,5+5}=10 完成点(汇点)的ve(vn)为工程完成所需要的时间
(顶点）事件vi的最早发生时间ve(i)： 从开始点到vi的最长路径长度。（ve(v1)=0） 既表示事件vi的最早发生时间，也表示所有以vi为尾的 弧所表示的活动ak的最早发生时间e(k)。(如下例的a7,a8) V2 V1 V3 V4 V5 仅有一个前驱顶点： ve(v2)=ve(v1)+6=0+6=6 ve(v3)=ve(v1)+4=0+6=4 ve(v4)=ve(v1)+6=0+5=5 有多个前驱顶点： ve(v5)=max{ve(前驱顶点)+ 前驱活动时间} =max{6+1,4+1,5+5}=10 完成点（汇点）的ve(vn)为工程完成所需要的时间