6.2 习题解答

1. 在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。

A. 1/2　　B. 2　　C. 1　　D. 4

【解答】 在无向图中，由于任何一条边对应两个顶点，也就是在统计顶点的度时，一条边计算了两次，因此顶点度数之和是边数之和的2倍。所以选B。

2. 一个n个顶点的连通无向图，其边的个数至少为( )。

A.n-1　　B.nC.n+1　　D. logn

【解答】 在连通无向图中，所有顶点至少存在一条通路，即所有顶点是连通的，则每个顶点之间至少有一条与其他顶点相连的边。因此至少存在n-1条边，所以选A。

3. 下面关于AOE网的叙述中，不正确的是( )。

A. 关键活动不按期完成就会影响整个工程的完成时间

B. 任何一个关键活动提前完成，那么整个工程将会提前完成

C. 所有的关键活动提前完成，那么整个工程将会提前完成

D. 某项关键活动提前完成，那么整个工程将会提前完成

【解答】 在AOE网中，关键活动直接影响整个工程的完成时间。当存在多条关键路径时，整个工程的完成是由多个关键活动决定的。所以选B。

4. 填空题

(1)n个结点的连通无向图G，最多有

条边，最少有条边。

(2) 有29条边的无向连通图，至少有( )个顶点，至多有( )个顶点；有29条边的无向非连通图，至少有( )个顶点。

(3)n个结点的强连通有向图G，最多有

条边，最少有条边。

(4) 有29条(弧)的有向连通图，至少有( )个顶点，至多有( )个顶点；有29条边的有向非连通图，至少有( )个顶点。

【解答】

(1) 对于n个结点的无向连通图G,为完全图时边数达到最多：n(n-1)/2条边，为树时边数达到最少：n-1条边。

(2) 满足不等式n(n-1)/2≤29 的最大的n为8，即8个顶点的连通无向图最多28条边，因此有29条边的连通无向图至少有9个顶点，至多30个顶点。

29条边9个顶点的无向图必定是连通的，29条边的非连通无向图至少有10个顶点(一个子图为含8个顶点的完全图，另一个子图为含两个顶点的完全图)。

(3) 强连通图即是任何两个顶点之间有路径相通，当所有结点在一个环上时，必定是强连通图。因此n个结点的强连通图最多有n(n-1)条弧(完全图)，最少有n条弧。

(4) 5个顶点的有向完全图最多20条边，6个顶点的有向完全图最多30个结点。因此有29条弧的有向连通图至少有6个结点，至多有29个结点。

29条边6个顶点的有向图必定是连通的，若不连通至少有7个顶点。

5. 已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是。

【解答】 第i个结点出发的边对应于邻接矩阵中的第i行,因此删除所有从第i个结点出发的边，就等价于将第i行全部置为零。

课外作业题

6. 对于下图：

(1) 如果每个指针需要4个字节，每个顶点的标号占2个字节，每条边的权占2个字节，则采用哪种表示法所需的空间较多？为什么？

(2) 画出从顶点1开始的DFS树。

7. (1) 设已给出图的邻接矩阵，设计算法将邻接矩阵转换为邻接表。

(2) 设已给出图的邻接表，设计算法将邻接表转换成邻接矩阵。

8. 已知一个无向图如下所示，要求分别用普里姆和克鲁斯卡尔算法生成最小生成树(假设以1为起点，试画出构造过程)。

9. 已知一个有向图如图所示。

(1) 写出该图的邻接矩阵及邻接表。

(2) 按所写的邻接表求出从顶点D开始的深度和广度优先遍历序列。

(3) 画出从顶点D开始的深度优先和广度优先生成树。

(4) 给出该有向图的一个拓扑排序序列。