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

建议用时：18～24 分钟
今日目标：掌握有向图和无向图的度数关系，会计算完全图、树和森林的边数，并能用连通性判断图的基本性质。

大纲定位：图的定义与相关概念，以及与树、邻接矩阵和邻接表学习直接相关的连通、度数、路径和环。

一、为什么需要“图”

数组强调先后位置，树强调父子层级；但道路、社交关系、网络连接往往既没有唯一的起点，也不只有一条向下的分支，这时用图表示更自然。

图记作 G=(V,E)：V 是顶点集合，E 是边集合。例如顶点可以表示城市，边可以表示城市之间的道路。

• 无向图的边没有方向，(u,v) 与 (v,u) 是同一条边，适合表示双向道路；
• 有向图的边有方向，u→ v 与 v→ u 是两条不同的边，适合表示单向道路；
• 自环是一条从顶点连回自己的边；重边是同一对顶点间出现多条边；
• 初赛中常说的简单图通常不含自环和重边。

必须先确认题目是否允许自环、重边，否则“最多有多少条边”会得到完全不同的答案。

二、相邻、关联与度

无向图中，若边 (u,v) 存在，就称 u,v 相邻，边与两个端点相关联。顶点的度是与它关联的边数。

一条普通无向边会给两个端点各贡献 1 度，因此把所有顶点的度相加时，每条边恰好被计算两次：

这叫握手定理。比如度数依次为 3,2,2,1，总和为 8，所以边数为 4。

由此还能推出：无向图中度数为奇数的顶点个数一定是偶数。因为总度数是偶数，而若奇数个奇数相加，结果会是奇数。

有向图要分开计算：

• 入度：有多少条边指向该点；
• 出度：有多少条边从该点出发。

每条有向边给起点贡献 1 个出度，给终点贡献 1 个入度，所以

而所有顶点的“入度加出度”总和是 2|E|。2024、2025 年 CSP-J 都直接考查过图的度数关系。

三、通路、回路与“能不能到达”

沿着相邻边从一个顶点走到另一个顶点，会形成一条通路。经过的边数叫通路长度。首尾相同的闭合通路称为回路；若题目强调“路径”，通常还要求途中顶点不重复。

在无向图中：

• 两点间存在通路，就说它们连通；
• 任意两点都连通，整张图就是连通图；
• 极大的连通部分叫连通分量，“极大”表示不能再加入同图中的其他顶点而仍保持这一部分连通。

在有向图中必须沿箭头走。若任意两个顶点 u,v 都能从 u 到 v，也能从 v 到 u，图才是强连通图。只看图形连在一起、不看箭头，是有向图连通题最常见的错误。

强连通有向图的每个顶点至少要有一条出边和一条入边，因此 n 个顶点至少需要 n 条有向边。这个下界可以达到：把所有顶点连成一个有向环即可。邻接矩阵中每条有向边对应一个非零元素，所以矩阵至少也有 n 个非零元素。

术语提醒：2022 年原题写的是“有向连通图”，其标准答案按“沿有向边任意两点可以互相到达”理解，也就是这里所说的强连通。若题目明确说“忽略方向后连通”，最少只需 n-1 条边。做题时要结合题目定义和选项判断。

四、完全图的边数从哪里来

n 个顶点的无向完全图记作 K_n，任意两个不同顶点之间恰有一条边。每条边对应“从 n 个顶点中选两个”，因此

也可以用度数验证：每个顶点都与其余 n-1 个顶点相邻，总度数为 n(n-1)，再除以 2。

不允许自环的有向简单图中，每个顶点可以向其余 n-1 个顶点各连一条边，因此最多有

条有向边，正好是无向完全图的两倍。若题目问“至少”，则要结合连通性等附加条件，不能直接套完全图公式。

五、树其实是一类特殊的图

无向图满足“连通且无环”时叫树。含 n 个顶点的树有 n-1 条边，而且下面几种说法彼此等价：

• 连通且无环；
• 连通，并且边数恰为 n-1；
• 无环，并且边数恰为 n-1；
• 任意两点之间恰有一条简单路径；
• 删除任意一条边都会不连通；
• 在任意两个原本不相邻的顶点间加一条边，都会出现唯一一个环。

但只知道“有 n-1 条边”还不够：一个图可能一部分成环、另一部分孤立，同样有 n-1 条边，却不是树。必须再知道它连通或无环。

若一张无环图由若干棵互不相连的树组成，就叫森林。假设共有 n 个顶点、c 个连通分量，第 i 棵树有 n_i-1 条边，相加得到

2021 年 CSP-J 曾用“树中删边后分成几部分”考查树的结构；图与树的边数关系也常作为后续遍历、生成树题的基础。

六、数量题的稳定检查法

1. 先写清有向还是无向，是否简单图；
2. 度数题画一个“每条边贡献几次”的小记号；
3. 看到“连通、无环、n-1 条边”时，检查已知的是哪两个条件；
4. 最后做奇偶性和上界检查：无向图度数和必须是偶数，简单图边数不能超过完全图。

今日练习

第 1～4 题选自 2021～2025 年 CSP-J 第一轮单选题，其中第 2 题只统一了字母大小写和数学格式；第 5～8 题巩固图的数量关系。

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

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

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

   A. N-1　 B. N　 C. N+1　 D. N²

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

   A. 边数　 B. 边数的两倍　 C. 顶点数　 D. 顶点数的两倍

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

   A. 顶点数　 B. 边数　 C. 顶点数加边数　 D. 顶点数的两倍

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

   A. 16　 B. 24　 C. 28　 D. 56

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

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

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

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

   A. 15　 B. 16　 C. 19　 D. 24