5. 有n (n≥1) 个顶点的无向连通图最少有n-1条边。

6. 有n (n≥1) 个顶点的有向强连通图最少有n条边。

7. 图中各个顶点的编号是人为的，不是它本身固有的，因此可以因为某种需要改变顶点的编号。

8. 如果无向图中各个顶点的度都大于2，则该图中必有回路。

9. 如果有向图中各个顶点的度都大于2，则该图中必有回路。

10. 图的深度优先搜索（depth first search）是一种典型的回溯搜索的例子，可以通过递归算法求

解。

11. 图的广度优先搜索（breadth first search）算法不是递归算法。

12. 有n个顶点、e条边的带权有向图的最小生成树一般由n个顶点和n-1条边组成。

13. 对于一个边上权值任意的带权有向图，使用Dijkstra算法可以求一个顶点到其它各个顶点的最短路

径。

14. 对一个有向图进行拓扑排序（topological sorting），一定可以将图的所有顶点按其关键码大小

排列到一个拓扑有序的序列中。

15. 有回路的有向图不能完成拓扑排序。

16. 对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。

17. 用边表示活动的网络（AOE网）的关键路径是指从源点到终点的路径长度最长的路径。

18. 对于AOE网络，加速任一关键活动就能使整个工程提前完成。

19. 对于AOE网络，任一关键活动延迟将导致整个工程延迟完成。

20. 在AOE网络中，可能同时存在几条关键路径，称所有关键路径都需通过的有向边为桥。如果加速这样

的桥上的关键活动就能使整个工程提前完成。

21. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数

有关，而与图的边数无关。

22. 邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。

23. 邻接矩阵只适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平

方）

24. 存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（上）三角部分就可以了。

5

25. 连通分量是无向图中的极小连通子图。

26. 强连通分量是有向图中的极大强连通子图。

27. 在AOE网络中一定只有一条关键路径。

参考答案： 1. 否

6. 否 11. 是 16. 否 21. 是 26. 是

2. 否 7. 是 12. 否 17. 是 22. 否 27. 否

3. 是 8. 是 13. 否 18. 否 23. 是

4. 是 9. 否 14. 否 19. 是 24. 是

5. 是 10. 是 15. 是 20. 是 25. 否

四、运算题

1. 设连通图G如图所示。试画出该图对应的邻接矩阵表示，并给出对它执行从顶点V0开始的广度优先

搜索的结果。

V0

V2 V1

V5 V4

V3 V7 V8 V6

2. 设连通图G如图所示。试画出该图及其对应的邻接表表示，并给出对它执行从V0开始的深度优先搜

索的结果。

V0

V2 V1 V5 V4

V3 V7

V8 V6

3. 设连通图G如图所示。试画出从顶点V0出发的深度优先生成树，指出图G中哪几个顶点是关节点（即

万一它失效则通信网络将发生故障）。 V0 V2 V1 V5 V4

V3 V7

V8 V6

⑧ ⑨ ⑦ 4. 设连通图G如图所示，

(1) 如果有关节点，请找出所有的关节点。 ⑥ ⑩ ① ② (2) 如果想把该连通图变成重连通图，至少在图中加几条边？如何加？

④ ⑤ ③

6

5. 对于如图所示的有向图，试写出：

(1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树

①

③ ②

⑤ ④

6. 设有向图G如图所示。试画出从顶点V0开始进行深度优先搜索和广度优先搜索得到的DFS生成森林

和BFS生成森林。 V0 V3 V1 V2

V4

V5 V6 V7

7. 表示图的另一种方法是使用关联矩阵INC[ ][ ]。其中，一行对应于一个顶点，一列对应于一条边。

因此，如果边j依附于顶点i，则INC[i][j]=1。如果ADJ是图G =（V, E）的邻接矩阵，INC是关联矩阵，试说明在什么条件下将有ADJ = INC?INCT?I，其中，INCT是矩阵INC的转置矩阵，I是单位矩阵。两个n?n的矩阵的乘积C = A?B定义为

cij??aik?bkjk?0n?1?公式中的 定义为按位乘。 ?定义为按位加，

设无向图G如图所示。试画出该图的邻接矩阵和关联矩阵。

e0 0 e1

1 2 e2 e3 e4 e5 6 3 4 5 e e8 e6 7e9 7

8. 设有一个连通网络如图所示。试按如下格式，应用Kruskal算法给出在构造最小生成树过程中顺序选出的各条边。 0 6 6

1 1 8 2 7

3 3 5 4 2

6 5 4 7

( 始顶点号，终顶点号， 权值 ) ( , , ) ( , , ) ( , , ) ( , , ) ( , , )

9. 设有一个连通网络如图所示。试采用prim算法从顶点0开始构造最小生成树。（写出加入生成树顶点

集合S和选择边Edge的顺序）

0

9 10 7 1 2 5 7 6 11 8

3 4 5

S顶点号 :

10. 计算连通网的最小生成树的Dijkstra算法可简述如下：将连通网所有的边以方便的次序逐条加入到

初始为空的生成树的边集合T中。每次选择并加入一条边时，需要判断它是否会与先前加入T中的边构成回路。如果构成了回路，则从这个回路中将权值最大的边退选。如果以邻接矩阵作为连通网的存储结构（仅使用矩阵的上三角部分），并在邻接矩阵的下三角部分记录最小生成树的边信息。试以如下所示的图G为例，画出构造出最小生成树及其邻接矩阵，并在括号内填入每次选择的边和可能去掉的边。

16 ?016??1421??? ① ② ?059?19??5 21

???06???19 9 ⑥ ?14 ③ Edge?? 26 ????01811?11 6 ?????026???⑤ ④ ?18 0????????

选 择 的 边 （顶点, 顶权值）

点,

（ , , ） （ , , ） （ , , ）

Edge: (顶点，顶点，权值) ( ， ， ) ( ， ， ) ( ， ， ) ( ， ， ) ( ， ， ) 0 0 0 0 0 0 去 掉 的 边

权值） （顶点, 顶

点,

（ , , ） （ , , ） （ , , ）

8