§1
图是"点 + 连线"的极简模型，却能刻画道路网、社交关系、电路、依赖、状态转移。图论的强大之处在于：把纷杂的实际问题抽象成顶点与边之后，通性通法立刻可用。本章建立图的基本语言——度、通路、连通、子图，然后走进两个经典判定：欧拉图（一笔画）与哈密顿图，最后引出结构最简的连通图：树。
一、图的定义与类型
定义（无向图）. 图 $G=(V,E)$ 由非空顶点集 $V$ 与边集 $E$ 组成，每条边是一个无序顶点对 $\{u,v\}$。若边为有序对 $(u,v)$，称 $G$ 为有向图。
- 简单图：无自环（连接自身的边）、无重边。本章除注明外均指简单图。
- 完全图 $K_{n}$：任意两顶点间都有边，边数 $\dbinom{n}{2}=\dfrac{n(n-1)}{2}$。
- 二分图：$V$ 可分为两个不交子集 $X,Y$，每条边一端在 $X$ 一端在 $Y$。
- 子图：$H=(V',E')$ 满足 $V'\subseteq V,\ E'\subseteq E$ 且 $E'$ 的端点都在 $V'$ 中。
常用存储结构：邻接矩阵（$n\times n$，稠密图友好）与邻接表（稀疏图友好）。例如三角形 $K_{3}$ 的邻接矩阵为
$$A=\begin{bmatrix}0&1&1\\1&0&1\\1&1&0\end{bmatrix}.$$
二、度与握手定理
顶点 $v$ 的度 $\deg(v)$ 是与之关联的边数（有向图区分入度 $\deg^{-}$ 与出度 $\deg^{+}$）。
定理（握手定理）. 对任意无向图，
$$\sum_{v\in V}\deg(v)=2\lvert E\rvert.$$
证明：每条边有两个端点，在求和时被它的两个端点各贡献一次。
推论. 奇度顶点的个数必为偶数。因为总和为偶数，偶度顶点之和为偶，剩下奇度顶点之和也必为偶，而奇数之和为偶要求项数为偶。
在有向图中 $\sum\deg^{+}(v)=\sum\deg^{-}(v)=\lvert E\rvert$。
三、通路、回路与连通性
- 通路（walk）：顶点与边交替的序列 $v_{0}e_{1}v_{1}\cdots e_{k}v_{k}$，$k$ 为长度。
- 迹（trail）：边不重复的通路；路径（path）：顶点不重复的通路。
- 回路（circuit）：起点与终点相同的迹；圈（cycle）：除首尾外顶点不重复的回路。
若任意两顶点间存在通路，称图连通；否则分解为若干连通分支。有向图中区分强连通（任意有序对互相可达）与弱连通（忽略方向后连通）。
两种基础遍历：深度优先搜索（DFS） 用栈沿一条路走到底再回溯，广度优先搜索（BFS） 用队列逐层扩展。两者都在 $O(\lvert V\rvert+\lvert E\rvert)$ 时间内访问一个连通分支的所有顶点；BFS 还能给出无权图的最短路层数。
四、欧拉图（一笔画）
定义. 经过图中每条边恰好一次的迹称为欧拉迹；若还回到起点则称欧拉回路，含欧拉回路的图称欧拉图。
定理（欧拉，1736）. 设 $G$ 连通（忽略孤立点），则
- $G$ 有欧拉回路 $\iff$ 每个顶点的度都是偶数；
- $G$ 有欧拉迹但无欧拉回路 $\iff$ 恰有 $2$ 个奇度顶点（此时迹必从一个奇度点出发、在另一个奇度点结束）。
必要性直观：每次"进入"一个顶点必须再"离开"，边成对使用，故中间顶点度为偶；起点与终点若不同，各多出一条未配对的边，度为奇。
这就是"一笔画"的完整判据，也是欧拉解决哥尼斯堡七桥问题的答案：该图四个顶点度分别为 $5,3,3,3$，奇度点有 $4$ 个，超过 $2$，故不可一笔画。
五、哈密顿图
定义. 经过每个顶点恰好一次的路径称哈密顿路径；若首尾相接成圈则称哈密顿圈，含哈密顿圈的图称哈密顿图。
欧拉关心边、哈密顿关心点，但难度天差地别：欧拉图有充要条件且可在线性时间判定，哈密顿图至今没有实用的充要条件，判定问题是 NP 完全的。只有充分条件可用：
狄拉克定理. 若简单图有 $n\ge3$ 个顶点且每个顶点度 $\ge n/2$，则 $G$ 是哈密顿图。
| 概念 | 遍历对象 | 判定难度 | 充要条件 |
|---|---|---|---|
| 欧拉回路 | 每条边一次 | 线性时间 | 连通且全为偶度 |
| 哈密顿圈 | 每个顶点一次 | NP 完全 | 未知，仅有充分条件 |
六、树与生成树
定义. 连通且无圈的图称为树，常记 $T$。度为 $1$ 的顶点称叶子。
定理. $n$ 个顶点的树恰有 $n-1$ 条边。
证明（对 $n$ 归纳）. $n=1$ 时树只有一个孤立点，边数 $0=1-1$，成立。设结论对不超过 $k$ 个顶点的树成立，考虑有 $k+1$ 个顶点的树 $T$。因 $T$ 连通无圈，必存在叶子（否则每点度 $\ge2$，沿边不断前行必回到已访问顶点而成圈）。删去一片叶子 $v$ 及其唯一关联边，剩下的图仍连通无圈，是有 $k$ 个顶点的树，由归纳假设有 $k-1$ 条边。加回 $v$ 与那条边，得 $T$ 的边数为 $k=(k+1)-1$。证毕。
等价刻画. 对 $n$ 个顶点的图，下列命题两两等价：连通无圈；连通且恰有 $n-1$ 条边；无圈且恰有 $n-1$ 条边；任意两顶点间有唯一路径。
生成树. 连通图 $G$ 的生成树是包含 $G$ 全部顶点的树型子图。DFS 与 BFS 在遍历过程中自然产出生成树；带权图上求总权最小的生成树即下一章的最小生成树问题。
七、例题与解答
例题1（判断欧拉图）
图 $G$ 的顶点集 $V=\{A,B,C,D,E\}$，边集为
$$E=\{AB,\ AC,\ BC,\ BD,\ CD,\ DE,\ CE\}.$$
判断 $G$ 是否为欧拉图，是否存在欧拉迹。
解： 先算各顶点度：
| 顶点 | 关联边 | 度 |
|---|---|---|
| $A$ | $AB,AC$ | $2$ |
| $B$ | $AB,BC,BD$ | $3$ |
| $C$ | $AC,BC,CD,CE$ | $4$ |
| $D$ | $BD,CD,DE$ | $3$ |
| $E$ | $DE,CE$ | $2$ |
度数之和 $2+3+4+3+2=14=2\times7$，与握手定理 $2\lvert E\rvert$ 吻合（$\lvert E\rvert=7$）。✓
奇度顶点为 $B$ 与 $D$，恰好 $2$ 个，且图连通。由欧拉定理：不存在欧拉回路，但存在欧拉迹，且必以 $B$ 与 $D$ 为两端。给出一条：
$$B\to A\to C\to B\to D\to C\to E\to D,$$
依次用边 $AB,AC,BC,BD,CD,CE,DE$，共 $7$ 条边且互不重复。✓
例题2（树的边数）
某连通图有 $10$ 个顶点、$15$ 条边，问它的生成树有多少条边？至少要删去多少条边才能使其无圈？
解： 生成树含全部 $10$ 个顶点，由定理其边数为 $10-1=9$ 条。原图 $15$ 条边中须删去 $15-9=6$ 条。这个差值 $\lvert E\rvert-\lvert V\rvert+1=6$ 称为图的圈秩，表示独立圈的个数。✓
练习
1. 一个图有 $6$ 个顶点、各顶点度为 $3,3,3,3,2,2$，问它有多少条边？又能否存在度序列为 $1,2,3,4,5$ 的简单图？
2. 判断完全图 $K_{4}$ 与 $K_{5}$ 是否为欧拉图。
3. 证明树中任意两顶点间的路径唯一，并说明 $n$ 个顶点的连通图至少有多少条边。
参考答案.
1. 度数之和 $=3+3+3+3+2+2=16$，由握手定理 $\lvert E\rvert=16/2=8$ 条。度序列 $1,2,3,4,5$ 不存在：奇度顶点为 $1,3,5$ 共 $3$ 个，是奇数个，违反"奇度顶点个数必为偶数"的推论。
2. $K_{4}$ 每点度 $3$（奇），有 $4$ 个奇度点，非欧拉图且无欧拉迹；$K_{5}$ 每点度 $4$（偶）且连通，是欧拉图。
3. 若两顶点间有两条不同路径，把它们拼接（去掉公共部分）即得一个圈，与树无圈矛盾。连通图至少 $n-1$ 条边，此时恰为树；少于 $n-1$ 条必不连通。
本章小结
- 图由顶点与边构成，分无向 / 有向、简单 / 多重，可用邻接矩阵或邻接表存储。
- 握手定理 $\sum\deg(v)=2\lvert E\rvert$，推论是奇度顶点个数为偶。
- 通路、迹、路径、回路、圈层层加强限制；连通性由 DFS / BFS 在线性时间判定。
- 欧拉图判据极简：连通且全偶度有欧拉回路，恰两个奇度点有欧拉迹。
- 哈密顿问题只关心顶点却是 NP 完全，仅有狄拉克等充分条件。
- 树是连通无圈图，$n$ 个顶点恰 $n-1$ 条边，任意两点路径唯一；生成树是遍历的副产品。
本章互动演示见页面底部交互图（DFS 与 BFS 遍历动画 graphTraversal）。
互动演示
拖动下方控件观察动态过程。