|
|
知识路径: > 应用数学 > 图论应用 > 图论应用 >
|
|
被考次数:1次
|
|
被考频率:
低频率
|
|
总体答错率:
76%
|
|
知识难度系数:
|
|
考试要求:
掌握
|
|
相关知识点:6个
|
|
|
|
在AOV网络中,如果边上的权表示完成该活动所需的时间,则称这样的AOV为AOE网络。例如,下图表示一个具有10个活动的某个工程的AOE网络。图中有7个节点,分别表示事件1~7,其中1表示工程开始状态,7表示工程结束状态,边上的权表示完成该活动所需的时间。
|
|
|
|
|
因AOE网络中的某些活动可以并行地进行,所以完成工程的最少时间是从开始节点到结束节点的最长路径长度,称从开始节点到结束节点的最长路径为关键路径(临界路径),关键路径上的活动为关键活动。为了找出给定的AOE网络的关键活动,从而找出关键路径,先定义几个重要的量。
|
|
|
Ve(j)、Vl(j):节点j事件最早、最迟发生时间。
|
|
|
|
从源点Vl到某结点Vj的最长路径长度,称为事件Vj的最早发生时间,记作Ve(j)。Ve(j)也是以Vj为起点的出边<Vj,Vk>所表示的活动ai的最早开始时间e(i)。
|
|
|
在不推迟整个工程完成的前提下,一个事件Vj允许的最迟发生时间,记作Vl(j)。显然,l(i)=Vl(j)-(ai所需时间),其中j为ai活动的终点。满足条件l(i)=e(i)的活动为关键活动。
|
|
|
求结点Vj的Ve(j)和Vl(j)可按以下两步来做:
|
|
|