内容发布更新时间 : 2024/11/15 7:15:29星期一 下面是文章的全部内容请认真阅读。
（ , （ , （ , （ , （ , （ , （ ,
, , , , , , , ） ） ） ） ） ） ） （ , （ , （ , （ , （ , （ , （ , , , , , , , , ） ） ） ） ） ） ）
11. 有八项活动, 每项活动要求的前驱如下:
活动 前驱
(1) 试画出相应的AOV网络, 并给出一个拓扑排序序列。
(2) 试改变某些结点的编号, 使得用邻接矩阵表示该网络时所有对角线以下的元素全为0。
12. 试对下图所示的AOE网络
(1) 这个工程最早可能在什么时间结束。
(2) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。 10 2 4 2 6
1 19 6 4
15 11 5 5 3
13. 设带权有向图如图所示。试采用Dijkstra算法求从顶点0到其他各顶点的最短路径和最短路径长度。 8 0 1 4 4 1
7 2 9 2
5 3 4
14. 一项工程由六个子工程p1, p2, ?, p6组成。这些子工程之间有下列关系：p1 < p2, p3 < p6,
p4 < p3, p2 < p6, p4 < p5, p1 < p3, p5 < p6。符号“<”表示“领先于”的关系。例如，p2 < p6表示p2完成后p6才能开始。试给出该工程的三种可能的施工顺序。
15. 设一有向图如下所示，请问该有向图是否为强连通图，并画出该有向图所有的强连通分量。
a
b c
d e
f g
9
A0 无前驱 A1 A0 A2 A0 A3 A0, A2 A4 A1 A5 A2, A4 A6 A3 A7 A5, A6
参考答案：
1. 图G对应的邻接矩阵为
?0?1??1??1G.Edge??0??0?0??0?0?11100000?00110000??00101000??11000110?10000000??01000000?00100011??00100100?00000100??
执行广度优先搜索的结果为V0V1V3V2V4V7V6V5V8，搜索结果不唯一。
2. 图G对应的邻接表为：
0 V0
1 V1
2 V2
3 V3
4 V4
5 V5
6 V6
7 V7
8 V8
3. 图G中，从V0出发的深度优先生成树为： V0 V2 V5
V3
V8 V6
图G中的关节点为：V1, V2, V3, V6。
4. (1) 关节点为 ①, ②, ③, ⑦, ⑧
(2) 至少加四条边 (1, 10), (3, 4), (4, 5), (5, 6)。从 ③ 的子孙结点⑩到③的祖先结点①引一条边，从 ② 的子孙结点 ④ 到根 ① 的另一分支 ③ 引一条边，并将 ⑦ 的子孙结点 ⑤、⑥ 与结点 ④ 连结起来，可使其变为重连通图。（解答不唯一）
⑧ ⑨ ⑦ 10
⑩ ③ ① ② ④ ⑤ ⑥
1 0 0 0 1 ∧ 2 ∧ 3 3 6 ∧ 3 3 3 1 2 ∧ 1 ∧ 5 ∧ 2 6 7 ∧ 7 6 ∧ 8 ∧ 执行深度优先搜索的结果为：V0V1V4V3V6V7V8V2V5，搜索结果不唯一。
V1 V4
V7
5. 以顶点 ① 为根的深度优先生成树（不唯一）：
①
①
② ③ ② ③ ④ ⑤
④ ⑤
以顶点 ② 为根的广度优先生成树： ① ② ③
④
⑤
6. 深度优先生成森林为： V0 VV3
2 V1
V4 V5 V6 V7
广度优先生成森林为： V0 VV3
2 V1 V4 V5 V6 V7
7. 当图中的顶点个数等于边的条数时，ADJ = INC*INCT-I成立。
图G对应的邻接矩阵为：
01234567??01100000?0?10011000?1?10000110??2ADJ???01000001???3?01000001?4?00100001???5?00100001?6??00011110???7
11
对应的关联矩阵为：
0123456789??1100000000?0?1011000000?1?100110000??2INC??0?0010001000???3?0001000100?4?0000100010???5?0000010001?6??0000001111???7
8. 应用Kruskal算法顺序选出最小生成树的各条边为： ( 始顶点号，终顶点号， 权值 ) 0 ( 0, 3, 1 )
( 2, 5, 2 )
1 1 2 ( 1, 4, 3 )
( 3, 5, 4 )
3 5 3 4 2 ( 3, 4, 5 ) 4 5
9. 采用prim算法从顶点0开始构造最小生成树的过程：
S顶点号 Edge(顶点，顶点，权值) : : 0 ( 0， 1， 9 ) 0, 1 ( 1， 3， 5 ) 0, 1, 3 ( 1， 2， 7 ) 0, 1, 3, 2 ( 2， 4， 6 ) 0, 1, 3, 2, 4 ( 2， 5， 7 ) 0, 1, 3, 2, 4, 5 9 0 1 7 5 2 6 7 3 4 5
10. 最小生成树及其邻接矩阵如图所示
① 16
② ??016??1421?
5
?16059?19??? 14
⑥
③
11
Edge???506??? ????601811?? ⑤
④ 6
?14???026??
????11?0???选 择 的 边
去 掉 的 边 （顶点, 顶权值） （顶点, 顶权值）
点, 点,
12