nd: if visited[(=0)and(G( ind=0)then dfs(G,i); if count< n then write(排序失败); 8-26试对右图所示的AOE网络 (1)这个工程最早可能在什么时 2 间结束 19 (2)求每个活动的最早开始时间 ()和最迟开始时间l) (3)确定哪些活动是关键活动 【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间距和最迟允许开始时间 l然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l,根据l-e=0?来 确定关键活动,从而确定关键路径。 19 15 37 8 17 15 27 19 27 37 38 17 12 此工程最早完成时间为43。关键路径为<1,3><3,2><2,5><5,6 8-27若AOE网络的每一项活动都是关键活动。令G是将该网络的边去掉方向和权 后得到的无向图 (1)如果图中有一条边处于从开始顶点到完成顶点的每一条路径上,则仅加速该边 表示的活动就能减少整个工程的工期。这样的边称为桥( bridge)。证明若从连通图中删去 桥,将把图分割成两个连通分量 (2)编写一个时间复杂度为On+e)的使用邻接表表示的算法,判断连通图G中是否 有桥,若有。输出这样的桥。 8.28.48.7 8.238.24 8.178.28 8.258.268.27end; for i := 1 to n do if ( visited[i] = 0 ) and ( G[i].ind = 0 ) then dfs ( G, i ); if count < n then write (‘排序失败’); 8-26 试对右图所示的 AOE 网络 (1) 这个工程最早可能在什么时 间结束。 (2) 求每个活动的最早开始时间 e( )和最迟开始时间 l( )。 (3) 确定哪些活动是关键活动。 【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间 Ve 和最迟允许开始时间 Vl。然后再计算各个活动的最早可能开始时间 e 和最迟允许开始时间 l，根据 l - e = 0? 来 确定关键活动，从而确定关键路径。 1 2 3 4 5 6 Ve 0 19 15 29 38 43 Vl 0 19 15 37 38 43 <1, 2> <1, 3> <3, 2> <2, 4> <2, 5> <3, 5> <4, 6> <5, 6> e 0 0 15 19 19 15 29 38 l 17 0 15 27 19 27 37 38 l-e 17 0 0 8 0 12 8 0 此工程最早完成时间为 43。关键路径为<1, 3><3, 2><2, 5><5, 6> 8-27 若 AOE 网络的每一项活动都是关键活动。令 G 是将该网络的边去掉方向和权 后得到的无向图。 (1) 如果图中有一条边处于从开始顶点到完成顶点的每一条路径上，则仅加速该边 表示的活动就能减少整个工程的工期。这样的边称为桥(bridge)。证明若从连通图中删去 桥，将把图分割成两个连通分量。 (2) 编写一个时间复杂度为 O(n+e)的使用邻接表表示的算法，判断连通图 G 中是否 有桥，若有。输出这样的桥。 8.8 8.11 8.15 8.9 8.2 8.4 8.7 8.23 8.24 8.17 8.28 8.25 8.26 8.27