🏷️ 知识点：图的概念

设无向图 G=(V,E) 和 G’=(V’,E’)，如果 G’ 是 G 的生成树，则下面说法错误的是（ ）。

A. G’ 是 G 的子图 B. G’ 是 G 的连通分量 C. G’ 是 G 的极小连通子图且 V’=V D. G’ 是 G 的一个无环子图

最小生成树 图的概念

[tag_link]

正确答案：B

生成树是无向连通图的一个子图，它包含原图的所有顶点，并且是树结构，因此是无环的连通图。 选项A正确，因为生成树的顶点集和边集都是原图的子集，所以它是原图的子图。 选项B错误，因为连通分量是极大连通子图，即不能再添加任何顶点或边而保持连通。 生成树是极小连通子图，不是极大连通子图。 对于连通图，其唯一的连通分量是图本身，而生成树是它的一个真子图（除非原图本身就是树），因此生成树不是连通分量。 选项C正确，生成树是极小连通子图，意味着去掉任意一条边都会破坏其连通性，并且顶点集与原图相同（V’=V）。 选项D正确，生成树作为树结构，不包含任何环，因此是无环子图。

一个有 n 个顶点和 n 条边的无向图一定是（ ）。

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

图的概念

[tag_link]

正确答案：D

一个无向图若有 $n$ 个顶点和 $n$ 条边，则它一定包含环。

这是因为无环图（即森林）最多只有 $n-1$ 条边：若图无环，则每个连通分量都是一棵树，设共有 $k$ 个连通分量，总边数 $e=n-k\le n-1$ 。 但题中边数为 $n$ ，大于 $n-1$ ，因此不可能无环，即必有环。

对于其他选项，图不一定连通或不连通。 例如，当

$n=6$ 时，可以构造一个连通的六边形（6 个顶点和 6 条边），也可以构造两个不连通的三角形（每个三角形 3 个顶点和 3 条边）。

因此，连通性无法确定，但环的存在是必然的。

下列关于图的叙述中，正确的是（ ）。

图的概念

A. 有向图必定存在入度为 0 的顶点 B. 有向无环图的拓扑排序有序序列存在且唯一 C. 各顶点的度均大于等于 2 的无向图必有回路 D. 可用 BFS 算法求出带权图中每一对顶点的最短路径

[tag_link]

正确答案：C

逐项判断：

• A 错。一个有向环中每个顶点的入度都为 1，因此有向图不一定有入度为 0 的顶点。
• B 错。DAG 一定存在拓扑序，但某一步若有多个零入度候选，选择顺序不同就会产生多个拓扑序。
• C 对。若无向图无环，则每个非空有限森林至少有一个度为 0 或 1 的顶点；反过来，每个顶点度至少为 2 的无向图不可能是森林，必有回路。
• D 错。BFS 只能直接求无权图或各边等权图的单源最短路径，不能求一般带权图的每对最短路径；非负权单源问题可用 Dijkstra，多源问题可用 Floyd。

若 G 是一个具有 36 条边的非连通无向简单图，则图 G 的结点数至少是（ ）。

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

图的概念

[tag_link]

正确答案：B

首先，由于 G 是非连通无向简单图，它至少包含两个连通分支。 设结点总数为 n，边数为 36。 为了最小化 n，应使一个连通分支尽可能大（边数多），而其他分支尽可能小（如孤立点，不贡献边数）。 因此，考虑图由一个具有 m 个结点的连通分支和若干孤立点组成，其中所有边均来自该连通分支，即该分支有 36 条边。

对于 m 个结点的简单连通图，边数最多为 m(m-1)/2，因此需满足 m(m-1)/2 ≥ 36。 计算得 m(m-1) ≥ 72。 当 m=9 时，9×8=72，即完全图 K9 恰有 36 条边。 此时若图仅含 K9，则为连通图，但要求非连通，故需至少增加一个孤立点，使结点数 n ≥ m+1=10。 因此 n=10 是可能的构造：一个 9 结点的完全图（36 条边）和一个孤立点，图是非连通的，总边数 36。

验证更小的 n：若 n=9，则非连通图的最大边数出现在两个分支分别为 8 和 1 个结点时，最大边数为 8×7/2+0=28<36，无法达到 36 条边。 n=8 时更不可能。 因此，满足条件的结点数至少为 10。

无向图 G 有 23 条边，度为 4 的顶点有 5 个，度为 3 的顶点有 4 个，其余都是度为 2 的顶点，则图 G 最多有（ ）个顶点。

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

图的概念

[tag_link]

正确答案：D

设图 G 的总顶点数为 n。 根据题意，度为 4 的顶点有 5 个，度为 3 的顶点有 4 个，其余顶点均为度为 2，故度为 2 的顶点数为 n - 5 - 4 = n - 9。 在无向图中，所有顶点的度之和等于边数的两倍。 已知边数为 23，因此总度之和为 2 × 23 = 46。 计算度之和：5 个度为 4 的顶点贡献 5×4=20，4 个度为 3 的顶点贡献 4×3=12，(n-9) 个度为 2 的顶点贡献 2(n-9)。 故有方程：20 + 12 + 2(n-9) = 46。 简化得 32 + 2n - 18 = 46，即 2n + 14 = 46，解得 2n = 32，n = 16。 因此，图 G 的顶点数为 16。 验证可行性：度序列由 5 个 4、4 个 3 和 7 个 2 组成，总度之和为 46，与边数一致，且满足图存在的基本条件（如握手引理）。 故最多有 16 个顶点，对应选项 D。

以下关于图的表述中，正确的是（ ）。

A. 强连通有向图的任何顶点到其他所有顶点都有弧 B. 图与树的区别在于图的边数大于或等于顶点数 C. 无向图的连通分量指无向图中的极大连通子图 D. 假设有图 $G=⟨V,\{E\}⟩$ ，顶点集 $V^{\prime }\subseteq V$ ， $E^{\prime }\subseteq E$ ，则 $V^{\prime }$ 和 $\{E^{\prime }\}$ 构成 $G$ 的子图。

图的概念

[tag_link]

正确答案：C

首先分析选项 A：强连通有向图要求任意两个顶点之间存在双向路径，但并不要求直接有弧（即直接的边）。

例如，一个包含三个顶点的有向环，顶点间通过路径相连而非都有直接弧，因此该表述错误。

接着看选项 B：图与树的区别在于树是无环连通图，且对于 n 个顶点的树，边数为 n-1。 图的边数可以小于、等于或大于顶点数，例如孤立顶点图边数少于顶点数，因此该表述不准确。

选项 C 正确，因为无向图的连通分量定义为极大连通子图，即不能再添加其他顶点和边而保持连通的子图，这是图论中的标准概念。

最后检查选项 D：子图需要顶点集 V’⊆V 和边集 E’⊆E，且 E’中边的端点必须都在 V’中。 选项仅说明 V’和 E’是子集，未强调边的端点限制，因此表述不完整，错误。

综上，正确选项为 C。

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

I. 所有顶点的度之和为偶数

Ⅱ.边数大于顶点个数

Ⅲ.至少有一个顶点的度为1

A. 只有I

B. 只有Ⅱ

C. I 和Ⅱ

D. I 和 Ⅲ

[tag_link]

正确答案：A

每条边都连接了两个结点，在计算顶点的度之和时每条边都被计算了两次（出度和入度），故所有顶点的度之和为边数的两倍，I 正确。n 个顶点、n-1 条边可以构成无向连通图，比如树，II 错误。顶点数为 N (N≥1) 的无向完全图中不存在度为 1 的顶点，III 错误。

下列关于图的叙述中，正确的是（ ）。

Ⅰ. 回路是简单路径

Ⅱ. 存储稀疏图，用邻接矩阵比邻接表更省空间

Ⅲ. 若有向图中存在拓扑序列，则该图不存在回路

图的概念

A. 仅 Ⅱ

B. 仅 Ⅰ、Ⅱ

C. 仅 Ⅲ

D. 仅 Ⅰ、Ⅲ

[tag_link]

正确答案：C

第一个顶点和最后一个顶点相同的路径称为回路；序列中顶点不重复出现的路径称为 简单路径 ；简单回路除首尾顶点外不重复，但“简单路径”要求路径中的顶点不重复，所以回路不是简单路径，Ⅰ错误。稀疏图的边数远小于 n²，邻接矩阵固定占用 O(n²)，邻接表只占 O(n+e)，Ⅱ错误。存在拓扑序列等价于有向图无环，若 拓扑排序 输出结束后仍有顶点未输出，则剩余子图存在有向环。因此Ⅲ正确，仅Ⅲ正确，选 C。

下列可用于表示有向图的存储结构有（ ）。

A. I 和 II B. II 和 IV C. I、II 和 III D. I、II 和 IV

邻接表 图的概念

[tag_link]

正确答案：C

邻接矩阵、邻接表和十字链表均适用于有向图的存储。 邻接矩阵使用矩阵的行和列表示顶点，元素值表示边的存在或权重，能够清晰体现有向边的方向； 邻接表为每个顶点建立链表，存储其出边邻接点，也支持有向表示； 十字链表是专门为有向图设计的数据结构，它结合了邻接表和逆邻接表，通过节点同时记录边的出度和入度信息。 而邻接多重表主要用于无向图，它将每条边作为一个节点，并链接到相关顶点的边表中，但无法区分边的方向，因此不适合表示有向图。