2. 考研
  3. 对给定的有7个顶点v1，v2，…，v7的有向图的邻接矩阵，如表1—3所示，要求： 若将图看成AOE网，列出其关键活动及相应的有向边＜i，j．W＞，i，j为顶点，w为权值，试问其关键路径的长度是多少？

对给定的有7个顶点v1，v2，…，v7的有向图的邻接矩阵，如表1—3所示，要求： 若将图看成AOE网，列出其关键活动及相应的有向边＜i，j．W＞，i，j为顶点，w为权值，试问其关键路径的长度是多少？

admin2017-04-28  107
问题 对给定的有7个顶点v1，v2，…，v7的有向图的邻接矩阵，如表1—3所示，要求：

若将图看成AOE网，列出其关键活动及相应的有向边＜i，j．W＞，i，j为顶点，w为权值，试问其关键路径的长度是多少？
选项
答案表1—12中的阴影部分为最早发生时间=最晚发生时间的活动。 [*] 关键活动：v1，v3，v4，v5，v7；相应的有向边：＜v1，v3，5＞，＜v3，v4，1＞，＜v4，v5，5＞，＜v5，v7，9＞；关键路径的长度是20。 补充：求关键路径的手动方法。 求出每个事件的最早发生时间和最晚发生时间，求解方法如下： 1) —个事件的最早发生时间为指向它的边（设为a）的权值加上发出a这条边的事件的最早发生时间，若有多条，取最大值，把最大值的边保留，其余边去除。 2) —个时间的最晚发生时间为由它发出的边（设为b）所指向的事件的最迟发生时间减去b这条边的权值，若有多条，取最小者，把最小值的边保留，其余边去除。 然后找出最早发生时间和最迟发生时间相同的活动，即为关键活动；剩余的边都是组成关键路径的边。
解析
转载请注明原文地址:https://kaotiyun.com/show/fXRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)