数据结构之图的概念题目

选择题

01. 图中有关路径的定义是()

A. 由顶点和相邻顶点序偶构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是

正确答案：A
解释：路径的定义通常指的是由顶点和相邻顶点构成的边所形成的序列。因此，选项A是正确的。

02. 一个有n个顶点和n条边的无向图一定是()

A. 连通的
B. 无环的
C. 不连通的
D. 有环的

正确答案：D
解释：一个无向图有 $ n $ 个顶点和 $ n $ 条边，必然存在环。因为在无环的情况下，最多只能有 $ n-1 $ 条边使图连通。因此，如果边数达到 $ n $，则必然会构成环。

03. 若从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是()。

A. 强连通图
B. 连通图
C. 有回路
D. 一棵树

正确答案：B
解释：对于无向图，如果从任意顶点出发的深度优先搜索能够访问到所有顶点，则该图一定是连通图。选项A中的强连通图是针对有向图的定义，因此不适用；选项C中有回路的无向图不一定是连通图；选项D中连通图可能是树，也可能存在环。

04. 以下关于图的叙述中，正确的是()

A. 图与树的区别在于图的边数大于等于顶点数
B. 假设有图 $ G={V, E} $，顶点集 $ V V, E' E $，则 $ V $ 和 $ E' $ 构成 $ G $ 的子图
C. 无向图的连通分量是指无向图中的极大连通子图
D. 图的遍历就是从图中某一顶点出发访遍图中其余顶点

正确答案：C
解释：无向图的连通分量确实是指无向图中的极大连通子图，因此选项C正确。选项A错误，因为图与树的区别不只在于边数；选项B错误，因为 $ E' $ 中的边必须对应于 $ V $ 中的顶点，否则无法构成子图；选项D不准确，因为图的遍历要求每个结点只能被访问一次，而如果图是非连通的，则从某一顶点出发无法访问到其他所有顶点。

05. 以下关于图的叙述中，正确的是()

A. 强连通有向图的任何顶点到其他所有顶点都有弧
B. 图的任意顶点的入度等于出度
C. 有向完全图一定是强连通有向图
D. 有向图的边集的子集和顶点集的子集可构成原有向图的子图

正确答案：C
解释：有向完全图中，任意两个顶点之间都有一条有向边，因此它一定是强连通的。因此选项C是正确的。选项A错误，因为强连通图的任意顶点到其他所有顶点都有路径，但不一定有直接的弧；选项B错误，因为在有向图中，任意顶点的入度不一定等于出度；选项D错误，因为如果边集中的某条边对应的某个顶点不在顶点集中，则无法构成有效的子图。

06. 一个有28条边的非连通无向图至少有( )个顶点。

A. 7
B. 8
C. 9
D. 10

正确答案：C
解释：在非连通的情况下，为了使边数达到28，考虑极端情况：假设一个完全图加上一个独立的顶点。对于一个完全无向图，边数与顶点数的关系为 $ E = $。令 $ n $ 为8，则 $ = 28 $条边。再加上一个独立的顶点，总共最少需要9个顶点。因此选项C是正确的。

07. 对于一个有 $ n $ 个顶点的图:

若是连通无向图，其边的个数至少为();若是强连通有向图，其边的个数至少为()。
A. $ n-1, n $
B. $ n-1, n(n-1) $
C. $ n, n $
D. $ n, n(n-1) $

正确答案：A
解释：对于连通无向图，边的最小数量是 $ n-1 $（即构成一棵树的情形）；对于强连通有向图，至少需要 $ n $ 条边来形成一个有向环，因此选项A是正确的。

08. 无向图 $ G $ 有 23 条边，度为 4 的顶点有 5 个，度为 3 的顶点有 4 个，其余都是度为 2 的顶点，则图 $ G $ 有()个顶点。

A. 11
B. 12
C. 15
D. 16

正确答案：D
解释：根据无向图的度数和公式，$\sum_{v \in V} \text{deg}(v) = 2e$，其中 $ e $ 是边数。已知度为4的顶点有5个，度为3的顶点有4个，剩余的顶点度为2。设度为2的顶点有 $ x $ 个，则：

$ 4 + 3 + 2 x = 2 $ $ 20 + 12 + 2x = 46 $ $ 2x = 14 x = 7 $

因此，总顶点数 $ 5 + 4 + 7 = 16 $。所以选项D是正确的。

09. 在有 $ n $ 个顶点的有向图中，每个顶点的度最大可达( )。

A. $ n $
B. $ n-1 $
C. $ 2n $
D. $ 2n-2 $

正确答案：D
解释：在有向图中，顶点的度等于入度与出度之和。在有 $ n $ 个顶点的有向图中，每个顶点的最大入度和出度可以分别为 $ n-1 $，因此每个顶点的度最大可达 $ 2(n-1) = 2n - 2 $，所以选项D是正确的。

10. 具有6个顶点的无向图，当有()条边才能确保是一个连通图。

A. 8
B. 9
C. 10
D. 11

正确答案：D
解释：5个顶点构成一个完全无向图需要10条边。为了确保第6个顶点与其他5个顶点构成一个连通图，至少需要再加1条边，使得总边数为11条。因此选项D是正确的。

11. 设有无向图 $ G=(V,E) $ 和 $ G'=(V,E) $，若 $ G' $ 是 $ G $ 的生成树，则下列不正确的是( )

I. $ G' $ 为 $ G $ 的连通分量
II. $ G' $ 为 $ G $ 的无环子图
III. $ G $ 为 $ G' $ 的极小连通子图且 $ V=V $

A. I、III
B. 只有 III
C.I、III D. 只有 I

正确答案：D
解释：生成树是一个极小的连通子图，因此它必定是无环的（II正确）。关于I，生成树 $ G' $ 本身是一个连通图，因此不能称其为 $ G $ 的连通分量；如果 $ G $ 是连通的， $ G' $ 是 $ G $ 的一个生成树，$ G' $ 不会是 $ G $ 的连通分量。III 的描述是正确的。因此选项D是正确的。

12. 若具有 $ n $ 个顶点的图是一个环，则它有()棵生成树。

A. $ m $
B. $ n $
C. $ n-1 $
D. 1

正确答案：B
解释：一个具有 $ n $ 个顶点的环图有 $ n $ 条边，去掉任意一条边都会形成一棵生成树，因此环图可以有 $ n $ 棵不同的生成树。所以选项B是正确的。

13. 若一个具有 $ n $ 个顶点、$ e $ 条边的无向图是一个森林，则该森林中必有( )棵树。

A. $ n $
B. $ e $
C. $ n-e $
D. 1

正确答案：C
解释：设森林中有$x$棵树,则再用$x-1$条边就能把所有的树连接成一棵树,此时,边数+1=顶点数，即$e+(x-1)+1=n$，故$x=n-e。$

14. 下列关于无向连通图特性的叙述中，正确的是()。

I. 所有顶点的度之和为偶数
II. 边数大于顶点个数减1
III. 至少有一个顶点的度为1

A. 只有 I
B. 只有 II
C. I 和 II
D. I 和 III

正确答案：C
解释：在无向连通图中，所有顶点的度之和为偶数（I正确），因为每条边连接两个顶点。边数必定大于等于顶点个数减1（II正确），以确保图的连通性。对于III，可能所有顶点的度均大于1（例如，形成一个环的情况），因此III不一定正确。选项C是正确的。

15. 若无向图 $ G=(V,E) $ 中含有7个顶点，要保证图 $ G $ 在任何情况下都是连通的，则需要的边数最少是()。

A. 6
B. 15
C. 16
D. 11

正确答案：C
解释：见第10题，方法都是先构建出完全图，加上一条边即可。

16. 下列关于图的叙述中，正确的是( )。

I. 回路是简单路径
II. 存储稀疏图，用邻接矩阵比邻接表更省空间
III. 若有向图中存在拓扑序列，则该图不存在回路

A. 仅 I
B. 仅 I、II
C. 仅 III
D. 仅 I、III

正确答案：C
解释：

I 错误：回路可以是简单路径，但不一定是。简单路径是指不重复顶点的路径，而回路可以包含重复的顶点。
II 错误：稀疏图的边数少，用邻接矩阵存储会浪费很多空间，邻接表更为高效。
III 正确：若有向图存在拓扑序列，则该图必须是无环的，因此不存在回路。
因此选项C是正确的。

17. 设图的邻接矩阵 $ A $ 如所示，各顶点的度依次是()。

A. 1, 2, 1, 2
B. 2, 2, 1, 1
C. 3, 4, 2, 3
D. 4, 4, 2, 2

正确答案：C
解释：邻接矩阵中每个元素表示对应顶点之间的边。度数是出度与入度之和，需统计每个顶点在矩阵中的行和列的非零元素。根据邻接矩阵的非对称性质，计算结果显示度数依次为 3, 4, 2, 3。选项C是正确的。

18. 已知无向图 $ G $ 含有 16 条边，其中度为 4 的顶点个数为 3，度为 3 的顶点个数为 4，其他顶点的度均小于 3。图 $ G $ 所含的顶点个数至少是()。

A. 10
B. 11
C. 13
D. 15

正确答案：B

解释：
根据无向图的性质，边数的2倍等于所有顶点度数之和。设图中其他顶点的度数均为2，并设这些顶点的数量为 $ x $。

首先，计算度数之和：
- 度为4的顶点：$ 3 = 12 $
- 度为3的顶点：$ 4 = 12 $
- 度为2的顶点：$ 2x $
因此，总度数为： $ 12 + 12 + 2x = 24 + 2x $
由无向图的性质，边数为16，所以： $ 2 = 32 $ 因此，有以下方程： $ 24 + 2x = 32 $ 解这个方程： $ 2x = 32 - 24 = 8 \ x = 4 $
计算总顶点数： $ = + + = 3 + 4 + 4 = 11 $

因此，图 $ G $ 至少有11个顶点，选项B是正确的。

综合应用题

问题

01. 图 $ G $ 是一个非连通无向图，共有 28 条边，该图至少有多少个顶点？

02. 如何对无环有向图中的顶点号重新安排，可使得该图的邻接矩阵中所有的 1 都集中到对角线以上？

答案及解释

01. 解答

图 $ G $ 是一个非连通无向图，设该图至少由两个连通子图构成。在边数固定的情况下，顶点数最少的情况是一个子图只含一个顶点，而另一个子图为完全图。

完全图 $ K_n $ 的边数为 $ $。
设包含 $ n $ 个顶点的完全图有 28 条边： $ = 28 n(n-1) = 56 $

解这个方程： $ n^2 - n - 56 = 0 $

利用求根公式计算得： $ n = 8 ( n = -7) $
由于一个子图只含一个顶点且没有边，因此该图至少有的顶点数为： $ 1 + n = 1 + 8 = 9 $

所以，该图至少有 9 个顶点。

02. 解答

为了使无环有向图中的邻接矩阵中所有的 1 都集中到对角线以上，可以按照以下步骤重新安排顶点编号：

按出度排序：计算每个顶点的出度，并将顶点按出度从大到小排序。
- 出度最大的顶点编号为 1，出度次大的顶点编号为 2，依此类推。
调整编号：在重新编号时，如果存在边 $ (u, v) $，则将顶点 $ u $ 的编号调整为在顶点 $ v $ 之前，因为在邻接矩阵中，边 $ (u, v) $ 只会在上三角部分出现（即 $ u $ 的编号小于 $ v $ 的编号）。
拓扑排序：使用拓扑排序方法可以更方便地对无环有向图的顶点进行编号，从而确保所有边都能对应到邻接矩阵的上三角部分。

综上所述，通过出度排序和拓扑排序的方法，可以有效地将邻接矩阵中的 1 集中到对角线以上。