本讲定位：半讲体量的”快讲快练”专题。七年真题统计（见
cspj-exam-analysis-2019-2025.md）：图论 2020 年起雷打不动每年 1 题、恒定 2 分，考法集中在数边数、判连通、一笔画三板斧，从不深挖算法实现（DFS/BFS 的代码属于复赛范围）。目标明确：这 2 分用十分钟的公式和一套手算流程稳稳拿下，省下的课时还给第 06 讲的遍历还原与哈夫曼练习。前置知识：第 05 讲的组合数 $\binom{n}{2}$；第 06 讲的树（树 = 无环连通图，是本讲的特例）。
适合对象：CSP-J 初赛。标注 ⭐ 的小节为进阶内容，第一遍学习可以跳过。
图 = 顶点 + 边。术语一张表记完：
| 术语 | 含义 | 备注 |
|---|---|---|
| 无向边 / 有向边 | $(u, v)$ 不分方向 / $\langle u, v \rangle$ 从 $u$ 指向 $v$ | 全是无向边的图叫无向图 |
| 顶点的度 | 与它相连的边数 | 有向图分入度（指进来）与出度（指出去） |
| 路径 | 沿边走出的顶点序列 | 顶点不重复的叫简单路径 |
| 环（回路） | 起点 = 终点的路径 | 无环连通的无向图就是树（第 06 讲） |
| 连通 | 任意两点间都有路径 | 不连通的图分成若干连通分量 |
| 简单图 | 无重边、无自环 | 初赛数边数的题默认简单图 |
注意与树的用词区分：图的”度”数的是所有相连的边（树的”度”只数孩子）——同一个词两套定义，题目在哪个专题就用哪套。
每条无向边给两个端点各贡献 1 度，所以：
$$ \sum_{v} \deg(v) = 2|E| \qquad \text{（度数之和 = 边数的两倍）} $$
有向图版本：入度之和 = 出度之和 = 边数（每条边贡献一入一出）。
例 1：无向图有 8 个顶点、每个顶点度数都是 3，边数 $= \dfrac{8 \times 3}{2} = 12$。
两个免费推论，都是判断题素材：
完全图（任意两点间都有边）：
$$ \text{无向完全图边数} = \binom{n}{2} = \frac{n(n-1)}{2} \qquad \text{有向完全图弧数} = n(n-1) $$