数据结构—图论的习题

图的习题

8-1-1

在下图所示的各无向图中：

8-1-2

在下图所示的各无向图中：

(1) 该图是强连通的吗? 若不是，则给出其强连通分量
(2) 请给出所有的简单路径及有向环
(3) 请给出每个顶点的度，入度和出度
(4)请给出其邻接表、邻接矩阵及逆邻接表

答案：

8-2-1

在一个具有n个顶点的无向连通图中至少有（n-1）条边

若要把n个顶点连接为一个连通图，则至少需要 n-1条边
最小生成树时为边数最少的连通图

8-2-2

设G是一个含有6个顶点的无向图，该图至多有（ 15）条边

每两个顶点间都有一条边 那么n(n-1)/2

8-2-3

在一个具有n个顶点的有向图中，构成强连通图时至少有（ ）条边

有n个顶点的强连通图最多有n(n-1)条边，最少有n条边
强连通图是指一个有向图中任意两点v1、v2间存在v1到v2的路径及v2到v1的路径的图

8-2-4

非空无向图的邻接矩阵是一个（ 对称矩阵）

8-2-5

一个图的邻接矩阵是对称矩阵，则该图是（ 非空无向图）

8-2-6

在含有n个顶点e条边的不带权无向图的邻接矩阵中，零元素的个数为（ ）

8-2-7

一个图的邻接表表示中有奇数个边结点，则该图是（ ）

8-2-8

如果从无向图的任一顶点出发进行一次广度优先遍历即可访问所有顶点，则该图一定是（ ）

8-2-9

对有n个顶点、e条边且使用邻接表存储的有向图进行深度优先遍历，其算法的时间复杂度是（ ）

8-2-10

对有n个顶点、e条边且使用邻接表存储的有向图进行深度优先遍历，其算法的时间复杂度是（ ）

8-2-11

对n个顶点的有向图G，采用邻接表存储，请回答下列有关问题：
（1）如何求图中的边数？
（2）如何判断顶点i到顶点j是否有边相连？
（3）如何求任意一个顶点i的入度？

8-3-1

在用邻接表表示图时，拓扑排序算法时间复杂度为（ O(n＋e) ）

8-3-2

设无向图的顶点个数为n，则该图最多有（ n(n-1)/2 ）条边

8-3-3

无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）

=a,e,b,c,f,d ==
== a,e,d,f,c,b

8-3-4

n个结点的完全有向图含有边的数目为（n(n-1) ）