第 7 章 图

7 - 1 画出 1 个顶点、 2 个顶点、 3 个顶点、 4 个顶点和 5 个顶点的无向完全图。试证明在 n 个顶点的无向完全图中，边的条数为 n(n - 1)/2 。

7 - 2 右边的有向图是强连通的吗？请列出所有的简单路径。

7-3用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？
【解答】

用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零元素的个数与边的条数有关。

7 -4 有 n 个顶点的无向连通图至少有多少条边？有 n 个顶点的有向强连通图至少有多少条边？试举例说明。

7 -5 对于有 n 个顶点的无向图，采用邻接矩阵表示，如何判断以下问题： 图中有多少条边？任意两个顶点 i 和 j 之间是否有边相连？任意一个顶点的度是多少？

7 -6 对于如右图所示的有向图，试写出：

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

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

7 -7 用邻接表表示图时，顶点个数设为 n ，边的条数设为 e ，在邻接表上执行有关图的遍历操作时，时间代价是 O(n*e) ？还是 O(n+e) ？或者是 O(max(n,e)) ？

7 -8 右图是一个连通图，请画出

(1) 以顶点①为根的深度优先生成树；
(2) 如果有关节点，请找出所有的关节点。

如果想把该连通图变成重连通图，至少在图中加几条边？

如何加？

7 - 9 编写一个完整的程序，首先定义堆和并查集的结构类型和相关操作，再定义 Kruskal 求连通网络的最小生成树算法的实现。并以右图为例，写出求解过程中堆、并查集和最小生成树的变化。

7 - 10 利用 Dijkstra 算法的思想，设计一个求最小生成树的算法。

7 - 11 以右图为例，按 Dijkstra 算法计算得到的从顶点① (A) 到其它各个顶点的最短路径和最短路径长度。

7- 12 试对右图所示的 AOE 网络，解答下列问题。

(1) 这个工程最早可能在什么时间结束。

(2) 求每个事件的最早开始时间 Ve[i] 和最迟开始时间 Vl[i] 。

(3) 求每个活动的最早开始时间 e( ) 和最迟开始时间 l( ) 。

(4) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。

答案

>>返回