2026-05-25 练习题答案与解析

单项选择题

1. n 个顶点的无向完全图的边数

答案：C. n(n-1)/2

解析： 无向完全图中任意两个不同顶点之间均存在一条边，共 $\binom{n}{2} = \dfrac{n(n-1)}{2}$ 条边。

---

2. 关于生成树的错误描述

答案：B. G' 是 G 的连通分量

解析： 生成树是包含原图全部顶点（V=V'）的极小连通子图，它是无环子图、也是原图的子图；但"连通分量"指的是原图中的极大连通子图，与"极小连通子图"含义完全相反，故 B 错误。

---

3. 18 条边的无向图最少顶点数

答案：C. 13

解析： 由握手定理，所有顶点度数之和等于边数的两倍，即 $2 \times 18 = 36$。已知度为 4 的顶点贡献 $4 \times 3 = 12$，度为 3 的顶点贡献 $3 \times 4 = 12$，剩余度数和为 $36 - 12 - 12 = 12$。其他顶点度数均小于 3，为使顶点数最少，应让每个顶点度数尽可能大，取最大值 2，需要 $12 / 2 = 6$ 个顶点。总计 $3 + 4 + 6 = 13$。

---

4. 不能出现在 G 中的边

答案：C. (V4, V3)

解析： 在无向图的 DFS 中，非树边只能是"回边"（连接当前结点与其祖先），不存在横叉边。

• (V0,V2)：V0 是 V2 的祖先，回边，可存在；
• (V4,V6)：V4 是 V6 的祖先，回边，可存在；
• (V0,V6)：V0 是 V6 的祖先，回边，可存在；
• (V4,V3)：V4 与 V3 分属 V0 的两棵不同子树，互为非祖先关系。若该边存在，DFS 在访问 V3 时会发现 V3 的邻居 V4 尚未访问，于是树边应为 (V3, V4) 而非给定的 (V0, V4)，矛盾。

---

5. 逆邻接表 DFS 序列

答案：A. V0 V1 V4 V3 V2

解析： 由逆邻接表（"指向我"的顶点列表）反推出射边邻接表：

• v0 → v1
• v1 → v0, v4
• v2 → v1, v3
• v3 → v0
• v4 → v3

从 v0 开始 DFS：v0 → v1 → v4 → v3（v3 的邻居 v0 已访问，回溯）。此时 v2 未被访问，从外层循环继续：访问 v2。因此序列为 V0, V1, V4, V3, V2。

判断题

6. 强连通分量是有向图中的最小强连通子图

答案：N

解析： 强连通分量是有向图的极大强连通子图（不能再向外扩展且仍保持强连通），而非"最小"。

---

7. 邻接矩阵存储空间只与结点数有关

答案：Y

解析： 邻接矩阵规模固定为 $n \times n$（n 为顶点数），与图中实际边数无关。

---

8. 有向图中至少有一个根

答案：N

解析： "根"要求能到达图中所有其他顶点。例如两个互不相连的强连通分量构成的有向图就没有这样的顶点。

---

9. 连通无环无向图移除任一边后不连通

答案：Y

解析： 连通且无环的无向图就是树。树有 $n - 1$ 条边且无冗余路径，移除任意一条边都会破坏连通性。

---

10. 拓扑排序可以通过 DFS 或 BFS 求解

答案：Y

解析： Kahn 算法（基于入度的 BFS）和基于 DFS 完成时间逆序两种方法都可以得到有向无环图的拓扑序。

---

11. 权值最小的边必属于任何一个 MST

答案：N

解析： 若最小权值边唯一，它必属于所有 MST；但若存在多条相同最小权值的边，则它只一定属于某个 MST，未必属于任何一个 MST。

例：三角形 A-B、B-C、A-C 权值均为 1，则任一最小生成树只包含其中两条边，每条边都可能被某个 MST 排除。

---

12. Dijkstra 能处理带负权边的图

答案：N

解析： Dijkstra 算法基于"已确定最短路径的顶点的距离不会再被更新"这一贪心性质，要求边权非负。负权边会破坏该性质，需使用 Bellman-Ford 或 SPFA。

填空题

13. 稀疏图的存储方式

答案：邻接表

解析： 邻接矩阵空间复杂度为 $O(V^2)$，与边数无关；邻接表为 $O(V + E)$，对边稀疏的图节省大量空间。

---

14. 可判断有向图是否有环的算法

答案：拓扑排序

解析： 当且仅当有向图存在环时，拓扑排序无法将所有顶点排入序列（Kahn 算法中会有顶点入度始终大于 0；基于 DFS 的拓扑排序会检测到回边）。广度优先遍历和单源最短路径算法本身不具备判环职责。

---

15. n 个顶点的有向强连通图的最少边数

答案：n

解析： 至少需要 n 条边才能使有向图强连通——典型构造为一条有向环 $v_1 \to v_2 \to \cdots \to v_n \to v_1$，恰好 n 条边即可让任意两顶点互相可达。少于 n 条边时图无法形成回路，必存在出度或入度为 0 的顶点，从而不可能强连通。