Day 13　图的基本概念：顶点、边与连通性

建议用时：18～24 分钟。请先打开今日知识卡完成复习，再独立提交本页答案。

今日学习资料

• 打开今日蓝白学习页
• 下载今日 PDF

复习目标：掌握有向图和无向图的度数关系，会计算完全图、树和森林的边数，并能用连通性判断图的基本性质。

今日练习

1. 【CSP-J 2021·第 6 题】一个有 $n$ 个顶点、$m$ 条边的无向连通图（$m>n$），需要删掉（　）条边才能使其成为一棵树。

{{ select(1) }}

• $n-1$
• $m-n$
• $m-n-1$
• $m-n+1$

2. 【CSP-J 2022·第 9 题】考虑由 $N$ 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（　）个非零元素。

{{ select(2) }}

• $N-1$
• $N$
• $N+1$
• $N^2$

3. 【CSP-J 2024·第 11 题】在无向图中，所有顶点的度数之和等于（　）。

{{ select(3) }}

• 边数
• 边数的两倍
• 顶点数
• 顶点数的两倍

4. 【CSP-J 2025·第 5 题】在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这个总和等于（　）。

{{ select(4) }}

• 顶点数
• 边数
• 顶点数加边数
• 顶点数的两倍

5. 【巩固题】无向完全图 $K_8$ 有（　）条边。

{{ select(5) }}

• 16
• 24
• 28
• 56

6. 【巩固题】一个含 10 个顶点的连通无向图至少有（　）条边。

{{ select(6) }}

• 8
• 9
• 10
• 45

7. 【巩固题】无向图中度数为奇数的顶点个数一定是偶数。（判断对错）

{{ select(7) }}

• 正确
• 错误

8. 【巩固题】一个森林有 20 个顶点和 4 个连通分量，它共有（　）条边。

{{ select(8) }}

• 15
• 16
• 19
• 24