目标

• 运用握手定理、入度与出度关系完成度数计算；
• 辨析简单图、自环、路径、环、可达与连通；
• 判断连通分量、强弱连通以及图的稀疏程度。

前置知识

建议先阅读6.1 图的基本概念，掌握 $G=(V,E)$、度、路径和连通性的基本定义。

环境、输入与预期输出

• 环境：任意现代浏览器；建议准备纸笔画图或记录度数。
• 输入：本页按源文件顺序整理的 10 道四选一选择题。
• 预期输出：一份独立作答记录，以及每道错题的错误原因和正确推理。

作答方法

1. 阅读题面后先画图、列度数或写出可达关系，再选择答案；
2. 点击“提交答案”，核对正确答案、解析和其余选项；
3. 做错的题点击“重新作答”，不要只记答案字母；
4. 完成全部题目后再展开组件生成的答案总览。

题型覆盖与边界

类型	本 Lab 的处理方式
正常情况	计算简单图的度、边数、路径和连通分量
边界情况	单独考查自环、孤立顶点和有向图的单向可达
易错情况	区分逻辑边与度贡献、弱连通与强连通、路径与简单路径

选择题

答题进度已答 0/10正确 0

第 1 题

难度★★考点无向图、度、握手定理标识ch06-01-q01

一个无向图有 $5$ 个顶点、$8$ 条边。已知其中四个顶点的度依次为 $4,3,3,2$，则第五个顶点的度为（ ）。

查看提示

先计算 $2m$，再减去四个已知度数。

请选择一个答案

A2

B3

C4

D5

第 2 题

难度★考点有向图、入度、出度标识ch06-01-q02

一个有向图有 $12$ 条边。该图所有顶点的入度之和与出度之和分别为（ ）。

请选择一个答案

A$12,12$

B$12,24$

C$24,12$

D$24,24$

第 3 题

难度★★考点简单图、无向图、最大边数标识ch06-01-q03

一个不含自环和重边的简单无向图有 $8$ 个顶点，最多可以有多少条边？

查看提示

无向边 $\{u,v\}$ 不区分两个端点的先后。

请选择一个答案

A16

B28

C56

D64

第 4 题

难度★★考点无向图、自环、度标识ch06-01-q04

无向图的边集为 $E=\{\{0,0\},\{0,1\},\{0,2\}\}$。按图论中自环对度贡献两次的约定，顶点 $0$ 的度为（ ）。

请选择一个答案

A2

B3

C4

D6

第 5 题

难度★★★考点无向图、奇数度、握手定理标识ch06-01-q05

关于任意有限无向图中奇数度顶点的个数，下列结论正确的是（ ）。

请选择一个答案

A一定是奇数

B一定是偶数

C一定等于边数

D只在连通图中才是偶数

第 6 题

难度★★★考点有向图、强连通、弱连通、可达标识ch06-01-q06

有向图的顶点集为 $\{0,1,2\}$，边集为 $\{0\to 1,1\to 2,2\to 1\}$。关于整张图的连通性，下列说法正确的是（ ）。

查看提示

先忽略方向判断弱连通，再检查是否每一对顶点都能双向到达。

请选择一个答案

A既强连通又弱连通

B弱连通但不强连通

C强连通但不弱连通

D既不强连通也不弱连通

第 7 题

难度★★考点无向图、连通分量、孤立顶点标识ch06-01-q07

无向图有顶点 $\{0,1,2,3,4,5,6\}$，边集为 $\{\{0,1\},\{1,2\},\{3,4\}\}$。该图有多少个连通分量？

请选择一个答案

A2

B3

C4

D5

第 8 题

难度★★考点路径、简单路径、回路标识ch06-01-q08

在一张无向图中，顶点序列 $0,1,2,1,3$ 的每对相邻顶点之间都有边。关于该序列，下列判断正确的是（ ）。

请选择一个答案

A它不是路径

B它是简单路径

C它是路径但不是简单路径

D它是简单环

第 9 题

难度★考点无权图、路径、路径长度标识ch06-01-q09

在无权图中，路径 $0\to 2\to 4\to 5$ 的长度通常定义为（ ）。

请选择一个答案

A3

B4

C$0+2+4+5=11$

D无法定义

第 10 题

难度★★考点稀疏图、稠密图、数量级标识ch06-01-q10

某简单图有 $n=10000$ 个顶点、$m=30000$ 条边。仅从 $m$ 与 $n^2$ 的数量级比较，该图通常应视为（ ）。

请选择一个答案

A稀疏图，因为 $m$ 远小于 $n^2$

B稠密图，因为 $m>n$

C完全图，因为每个顶点平均有多条边

D无法讨论，因为稀疏图必须满足 $m<n$

答案总览（建议完成全部题目后查看）

1. 第 1 题：C
2. 第 2 题：A
3. 第 3 题：B
4. 第 4 题：C
5. 第 5 题：B
6. 第 6 题：B
7. 第 7 题：C
8. 第 8 题：C
9. 第 9 题：A
10. 第 10 题：A

完成清单

• 10 道题均在展开答案前独立作答；
• 能用度数和检查无向图答案，并说明奇数度顶点为何成对出现；
• 能画出至少一道有向图的可达关系并判断强、弱连通；
• 每道错题都记录了错误前提，而不只抄写正确答案。

思考题

1. 为什么无向图的自环对同一顶点贡献两次度？
2. “忽略方向后连通”为何不能推出有向图强连通？
3. 稀疏与稠密为什么更适合作为数量级判断，而不是固定阈值？

复盘

• 我最容易混淆的是边数、邻接记录数，还是度数贡献？
• 遇到连通性题时，我是否明确了图是有向还是无向？
• 哪个干扰项利用了“把无向图结论直接套到有向图”的错误？