图论基础

这一页把图论的基础语言一次讲透：从”图就是顶点和边”的精确定义出发，推导出握手定理、欧拉回路的判别法、树的等价刻画、邻接矩阵的路径计数和平面图的欧拉公式——每一条都给出证明或证明思路，而不是让你背结论。学完之后，你能判断一个具体图是否存在欧拉回路、用 $A^2$ 数出两点间长度为 2 的路径、用”删边归纳”证明平面图的边数上界，也能看懂谱聚类和 GNN 里反复出现的拉普拉斯矩阵从哪里来。

1. 图的定义、度与握手定理

图 $G=(V,E)$ 由顶点集 $V$ 与边集 $E$ 组成。无向图的边是顶点的二元子集，记作 $\{u,v\}$ 或简写 $uv$；有向图的边是有序对，记作 $(u,v)$，表示从 $u$ 指向 $v$ 的弧。简单图不允许两种东西：自环（$vv$ 这样的边）和重边（同一对顶点之间多条边）。本章没有特别说明时，“图”指有限简单无向图。

顶点 $v$ 的度 $d(v)$（也记 $\mathrm{deg}(v)$）是与它关联的边数。有向图中区分出度 $d^{+}(v)$（从 $v$ 出发的弧数）与入度 $d^{-}(v)$（指向 $v$ 的弧数），显然 $d^{+}(v)+d^{-}(v)$ 恢复无向意义下的”总关联数”。

定理 1（握手定理） 任何无向图满足

$$\sum _{v\in V}d(v)=2|E|.$$

证明： 对边数 $|E|$ 作归纳。边数为 0 时两边都为 0。设去掉任一边 $e=uv$ 后的图 $G^{\prime }$ 满足等式，把 $e$ 加回来：左边恰有两个顶点的度各加 1，总和加 2；右边 $|E|$ 加 1 再乘 2，也是加 2。等式保持成立。$■$

一个更”会计”的证法是按边计数：每条边有两个端点，对”度之和”贡献恰好 2，与顶点无关。两种证法都该会——前者是图论归纳法的标准起手式，后者体现”用两种方式数同一个量”的组合思想。

推论（聚会问题） 任意图中度为奇数的顶点个数必为偶数。特别地，聚会上握过奇数次手的人数永远是偶数。

证明： 由定理 1，度之和为偶数；偶度顶点贡献的度和也是偶数，所以奇度顶点的度和必为偶。奇数个奇数之和为奇数，故奇度顶点的个数不能是奇数。$■$

简单图 $G$ 的补图 $\bar{G}$ 与 $G$ 共用同一顶点集，两顶点在 $\bar{G}$ 中相邻当且仅当它们在 $G$ 中不相邻——补图把”有关系”和”没关系”互换，$G$ 与 $\bar{G}$ 的度满足 $d_G(v)+d_{\bar{G}}(v)=n-1$。

2. 路径、环与连通性

步道（walk）是顶点与边的交替序列 $v_0{e}_1{v}_1{e}_2\cdots e_k{v}_k$；所有顶点互不相同的步道叫路径（path），$v_0=v_k$ 且其余顶点互不相同的闭路径叫环（cycle）。长度为 $k$ 的环记作 $C_k$；只许经过、不许重复边的闭步道叫闭迹（closed trail），这个概念在欧拉图一节要用。

若任意两顶点间都有路径，称图 $G$ 连通；否则 $G$ 被唯一地分解成若干个连通分量——每个分量是一个极大连通子图，“极大”的意思是再加入任何一条外部边就不再连通（等价地说，分量内部两两互达，外部顶点不可达）。把”连通”当作顶点集上的等价关系（$u\sim v$ 当且仅当 $u,v$ 间有路径），连通分量就是这个等价关系的等价类——这正是 离散数学总览 里等价关系划分论域的图论实例。

割点是删去它（连同关联边）后连通分量数增加的顶点；桥（割边）是删去后其两端不再连通的边。一个有用的事实：桥恰好是不属于任何环的边——若边 $e$ 在某环上，删去 $e$ 后环的其余部分仍是一条绕行路径，两端照样连通。

3. 欧拉图与哈密顿图

欧拉回路是经过每条边恰好一次并回到起点的闭迹；存在欧拉回路的连通图叫欧拉图。欧拉通路（不强制回到起点）则只要求经过每条边恰一次。

定理 2（欧拉回路判别法） 非平凡连通图 $G$ 有欧拉回路，当且仅当每个顶点的度都是偶数。

证明思路： 必要性几乎免费：沿欧拉回路走的时候，每次”进入”一个顶点必然配套一次”离开”，所以每个顶点的度等于它进出次数之和，必为偶。充分性是这道题的实质，分两步。第一步（找一条闭迹）：从任一顶点出发，每次沿未用过的边走进邻点；由于度全偶，只要走进一个非起点的顶点就必然还有未用的边可以离开，所以走不下去时一定停在起点，得到一条闭迹 $T$。第二步（拼接）：若 $T$ 已含所有边则结束；否则删掉 $T$ 的边后，剩余图里仍每个顶点度为偶（$T$ 对每个顶点的消耗仍是”进一次出一次”），且在 $T$ 上必存在某顶点 $v$ 仍有剩余边——从 $v$ 出发在剩余图上重复第一步得到新闭迹，把它在 $v$ 处”缝”进 $T$。边数有限，重复有限次后所有边被缝进同一条闭迹。$■$

注意前提”非平凡连通”：所有边必须在同一个连通分量里，否则经过一个分量的边就到不了另一个分量。只要求欧拉通路时条件放松为：恰有 0 个或 2 个奇度顶点（0 个即回路情形；2 个时它们必为通路两端——奇度顶点个数总是偶数，不可能恰有 1 个）。

哈密顿回路是经过每个顶点恰好一次的环。名字与欧拉回路对称，难度却天差地别：欧拉问题有定理 2 这样干净的充要条件，哈密顿问题没有已知的多项式时间判别法，判定一个图是否有哈密顿回路是 NP 完全的。已知的都是充分条件，最经典的是 Dirac 定理。

定理 3（Dirac, 1952） 设 $G$ 是 $n\ge 3$ 个顶点的简单图，若每个顶点满足 $d(v)\ge n/2$，则 $G$ 有哈密顿回路。

Dirac 定理只给陈述不给证明，但它的证明工具值得知道：取一条最长的路径，端点的高度数迫使它有邻点落在路径内部，于是可以”弯折”出一条更长的环——这是处理哈密顿问题的标准手法。

旅行商问题（TSP）是哈密顿回路的加权版：给定城市间距离，找访问每个城市恰一次的最短回路。它是组合优化的标准 NP 难问题；当距离满足三角不等式（度量 TSP）时，“最小生成树加倍再捷径化”可以给出一个不超过最优解 2 倍的近似解——MST 的思想会在下一节用到。

4. 树：最少的连通，最多的无环

树是连通且无环的图；不含环但不必连通的图叫森林——森林就是若干棵树的并。

定理 4（树的等价刻画） 设 $G$ 是 $n$ 个顶点的图，下列命题等价：

1. $G$ 连通且无环（即 $G$ 是树）；
2. $G$ 连通且有 $n-1$ 条边；
3. $G$ 无环且有 $n-1$ 条边；
4. $G$ 中任意两顶点之间有唯一路径。

证明思路： 核心链条是 (1)⇒(2)⇒(3)⇒(1)，条件 4 作陪衬。(1)⇒(2) 用归纳：$n=1$ 显然；$n\ge 2$ 时树必有叶子（沿一条路径走到不能走为止，终点度为 1——否则会成环），删去这片叶子得到 $n-1$ 个顶点的树，由归纳假设它有 $n-2$ 条边，加回叶子恰为 $n-1$ 条。(2)⇒(3) 用反证：若连通图 $G$ 含环，删去环上任意一条边图仍连通，但边数变成 $n-2<n-1$；而对连通图反复删环边直到无环，留下的树按 (1)⇒(2) 必须有 $n-1$ 条边，矛盾。(3)⇒(1)：若无环但不连通，设各连通分量大小为 $n_1,\dots ,n_c$；每个分量本身是树，边数 $\sum (n_i-1)=n-c$。题设边数为 $n-1$，故 $c=1$，即连通。条件 4 等价于”连通且无环”是直接的：两条不同路径拼起来含环，有环则环上两点已有两条路径。$■$

三条推论都很好用：树至少有两片叶子（$n\ge 2$ 时）；树的任一边都是桥；在树上任加一条非树边恰好产生一个环。

生成树是连通图 $G$ 的生成子图（含全部 $n$ 个顶点）且本身是树——从 $G$ 中选出 $n-1$ 条边保持连通、不成环。边带权时，最小生成树（MST）是边权之和最小的生成树，有两个经典贪心算法：

• Kruskal：把所有边按权升序排列，依次考察，若当前边与已选边不成环则选中。用并查集判环，几乎是最短贪心代码。
• Prim：从任一顶点出发维护一棵”已长成”的树，每步选一条连接树内与树外且权最小的边，把新顶点拉进树。

两者的正确性共享同一个引理。切割引理：对图的任一顶点划分 $(S,V\setminus S)$（称为一个割），设 $e$ 是跨越该割的权最小边，则某棵 MST 必含 $e$。直觉是：任取一棵不含 $e$ 的 MST，把 $e$ 加进去产生一个环，环上必有另一条跨割边 $e^{\prime }$；用 $e$ 替换 $e^{\prime }$ 不增加总权，所以”最优解可以调整为含 $e$“。Kruskal 选边时，“已选边集的连通块划分”就是一个割，所选边恰是该割的最小跨割边；Prim 选的边则是”已长成顶点集 vs 其余”这个割的最小跨割边。每步都不排除最优解，归纳下去整体最优。

Cayley 公式：$n$ 个顶点的完全图 $K_n$ 共有 $n^{n-2}$ 棵生成树。这是计数层面的漂亮结论（证明常用 Prüfer 序列），此处只提结果：顶点数 $n$ 增长时生成树数量是超指数的，“枚举所有生成树找最小的”因此完全不现实——这正是贪心算法存在的理由。

5. 二分图与匹配

二分图是顶点集能划分成两部分 $X,Y$，使每条边都一端在 $X$、一端在 $Y$ 的图。判定二分图不需要去试所有划分：

定理 5 图 $G$ 是二分图，当且仅当 $G$ 不含奇数长度的环。

证明思路： 必要性：二分图里沿任何环走，顶点在 $X,Y$ 间交替出现，环长必为偶。充分性：给判定算法一个证明——从任一顶点 $s$ 出发做广度优先搜索，按层数的奇偶给顶点染两色。若每条边的两端都异色，染色成功，同色集即 $X,Y$，$G$ 二分。若某条边 $uv$ 两端同色，设它们在 BFS 树中到 $s$ 的距离分别为 $\text{dist}(s,u)$ 与 $\text{dist}(s,v)$；同色意味着距离同奇偶，而 BFS 树的性质给出 $|\text{dist}(s,u)-\text{dist}(s,v)|\le 1$，所以两距离相等。此时两条 BFS 树路径（$s$ 到 $u$、$s$ 到 $v$）加上边 $uv$ 构成一个环，其长度 $=\text{dist}(s,u)+\text{dist}(s,v)+1$ 为奇数。$■$

匹配是边的一个子集 $M\subseteq E$，其中任意两条边不共享端点；$M$ 中边的端点称为被饱和。二分图匹配回答”任务分配”类问题：$X$ 是任务、$Y$ 是人，边表示”这个人能做这个任务”，最多能同时完成多少任务？记 $N(S)$ 为 $S\subseteq X$ 的所有邻点组成的集合。

定理 6（Hall 婚配定理） 二分图 $G=(X,Y;E)$ 存在饱和 $X$ 全部顶点的匹配，当且仅当对任意 $S\subseteq X$ 都有

$$|N(S)|\ge |S|.$$

必要性一目了然：$S$ 中每个顶点在匹配里各占一个不同的邻点，邻点总数至少 $|S|$。充分性（只提思路）用反证加”极大匹配”的增广路论证：若某个极大匹配未饱和 $X$ 中顶点 $x$，从 $x$ 出发沿”非匹配边—匹配边”交替走，Hall 条件保证这条路不会”堵死”，必能走到 $Y$ 中未饱和顶点，翻转沿途边的匹配状态就得到更大的匹配——这就是匈牙利算法的原型。Hall 条件的意义在于把”存在性”翻译成可以直接验证的计数不等式。

6. 图的矩阵表示与谱

把图写成矩阵，图论问题就变成了线性代数问题。设 $G$ 顶点编号 $1,\dots ,n$。

邻接矩阵 $A=(a_{ij})$：无向简单图中 $a_{ij}=1$ 当且仅当 $ij\in E$，否则为 $0$；对角元为 0。$A$ 是对称矩阵，第 $i$ 行（列）之和恰是 $d(i)$。加权图把 1 换成边权即可。

定理 7（$A^k$ 计数路径） 对任意正整数 $k$，$(A^k{)}_{ij}$ 等于从顶点 $i$ 到顶点 $j$ 长度为 $k$ 的步道数。

证明： 对 $k$ 归纳。$k=1$ 即邻接矩阵定义。设 $A^k$ 已计数长度为 $k$ 的步道，由矩阵乘法

$$(A^{k+1}{)}_{ij}=\sum _{\ell =1}^n(A^k{)}_{i\ell }{a}_{\ell j}.$$

右端的每一项把”一条 $i$ 到 $\ell$ 的长 $k$ 步道”与”一条边 $\ell j$“拼接成长 $k+1$ 的步道，且按倒数第二个顶点 $\ell$ 分类，不重不漏；求和即得全部。$■$

两条常用推论：$(A^2{)}_{ii}=d(i)$；无向简单图中三角形个数 $=\frac{\mathrm{tr}(A^3)}{6}$——每个三角形贡献 6 条长度 3 的闭步道（3 个起点 × 2 个方向），其余闭步道都会在折返中成对抵消计数。

关联矩阵 $M$：行为顶点、列为边，$m_{ve}=1$ 当 $v$ 是边 $e$ 的端点（有向图用 $+1/-1$ 区分首尾）。它把”边”显式列出来，适合表达网络流约束；无向图中 $M{M}^{\mathsf{T}}=D+A$，其中 $D$ 是下面定义的度矩阵。

度矩阵 $D$ 是对角矩阵，$D_{ii}=d(i)$。拉普拉斯矩阵

$$L=D-A$$

是谱图论的中心对象。三个基本性质：(i) 每行之和为 0，故 0 必为特征值，全 1 向量是特征向量；(ii) 对任意向量 $x\in {\mathbb{R}}^n$ 有二次型

$$x^{\mathsf{T}}Lx=\sum _{ij\in E}(x_i-x_j{)}^2,$$

它度量 $x$ 在图上的”平滑度”——这正是把图上的函数（如图嵌入的坐标）向”相邻顶点取值接近”方向正则化的能量项；(iii) $L$ 半正定，特征值记 $0={\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_n$。性质 (iii) 由二次型非负直接得到；0 的特征值重数等于连通分量数——每个分量贡献一个”分量内恒 1、分量外为 0”的特征向量。

归一化拉普拉斯

$$\mathcal{L}=I-D^{-1/2}A{D}^{-1/2}=D^{-1/2}L{D}^{-1/2}$$

（要求无孤立顶点）把度的影响除掉，使不同密度的图可比。它与随机游走矩阵 $D^{-1}A$ 共享特征值，$1-\lambda$ 对应。

谱聚类的直觉：想给图做”软”的二分，就是找一个向量 $x$（划分坐标），让边两端坐标差尽量小（$x^{\mathsf{T}}Lx$ 小）、且 $x$ 不平庸（与全 1 向量正交）。瑞利商最小化告诉我们这样的 $x$ 就是第二小特征值 ${\lambda }_2$ 的特征向量——Fiedler 向量。按其分量正负把顶点劈成两半，就是谱二分；对 $\mathcal{L}$ 取前 $k$ 个特征向量做 $k$ 均值，就是谱聚类。图神经网络里消息传递”聚合邻居”的每一层，本质也是在拉普拉斯的多项式上做平滑——谱视角与 GNN 的过度平滑问题直接相关。

7. 平面图与欧拉公式

平面图是能画在平面上且边除端点外互不相交的图。注意区分”图”与”画法”：$K_4$ 画成带交叉的样子不平面，但换一种画法就平面了；而 $K_5$ 与 $K_{3,3}$ 无论如何画都要交叉（Kuratowski 定理说：非平面图当且仅当含有它们的”细分”）。平面画法把平面分成若干面（含无界面），记面数为 $f$。

定理 8（欧拉公式） 连通的平面图中

$$v-e+f=2,$$

其中 $v,e,f$ 分别是顶点数、边数、面数。

证明思路： 对边数归纳。若图是树，则 $f=1$（无环就没有被围住的有限面），而定理 4 给出 $e=v-1$，代入得 $v-(v-1)+1=2$。若图含环，删去环上的任意一条边 $e_0$：这条边两侧是两个不同的面（否则可用 Jordan 曲线定理造出一个更小的环把画法简化——标准论证），删去它使两个面合并，$f$ 减 1；剩余图仍连通、顶点数不变，由归纳假设满足 $v-(e-1)+(f-1)=v-e+f=2$。$■$

欧拉公式立刻给出边数上界：每个面至少由 3 条边围成、每条边至多属于 2 个面，故 $2e\ge 3f$，代入欧拉公式得

$$e\le 3v-6(v\ge 3).$$

于是 $K_5$ 有 $v=5,e=10$，不满足 $10\le 9$，非平面。无三角形的图每个面至少 4 条边，同理得 $e\le 2v-4$，于是 $K_{3,3}$（$v=6,e=9$）也不满足，非平面——这两个上界是用欧拉公式证非平面性的标准武器。

四色定理：任何平面图都可以用至多 4 种颜色给顶点染色，使相邻顶点不同色。它 1976 年由 Appel 与 Haken 借助计算机穷举证明，是首个重要的计算机辅助定理，至今没有人类可完整检验的纸笔证明。五色定理（每个平面图 5 色可染）则有一个漂亮的经典证明，核心一步是：欧拉公式推论保证平面图中必有度不超过 5 的顶点，删去它归纳染色，再把颜色不够时用一个”双色交换”的 Kempe 链论证腾出一种颜色。

例题

例 1（握手定理） 聚会上若干人互相握手（不跟自己握）。证明：任意时刻，握过奇数次手的人数必为偶数。

解： 构造图 $G$：顶点是人，两人握过手则连边。人 $v$ 的度 $d(v)$ 就是他握手的次数。由握手定理，${\sum }_{v}d(v)=2|E|$ 是偶数。把所有顶点按度的奇偶分组：

$$\sum _{v:d(v)\text{ 奇}}d(v)=\underset{\text{偶}}{\underbrace{2|E|}}-\underset{\text{偶}}{\underbrace{\sum _{v:d(v)\text{ 偶}}d(v)}},$$

右边是偶数减偶数，左边是若干个奇数之和。奇数个奇数相加为奇数，所以左边的项数——即奇度顶点数——必须是偶数。$■$

例 2（判定欧拉回路） 下图顶点为 $a,b,c,d,e$，边集为

$$E=\{ab,bc,ca,cd,de,ec\}.$$

(1) 判断它是否有欧拉回路，若有则写出一条；(2) 若删去边 $cd$，结论如何？

解： (1) 先算度：$d(a)=2$（$ab,ac$），$d(b)=2$（$ab,bc$），$c$ 关联 $bc,ca,cd,ce$ 故 $d(c)=4$，$d(d)=2$（$cd,de$），$d(e)=2$（$de,ec$）。每个顶点度均为偶数；图显然连通（每条边都能走到 $c$）。由定理 2，欧拉回路存在。按证明思路构造：从 $a$ 出发走 $a\to b$，到 $b$ 只有未用边 $bc$，走到 $c$；在 $c$ 选 $cd$，到 $d$ 只有 $de$，到 $e$ 只有 $ec$，回到 $c$；此时 $c$ 还有未用边 $ca$，走到 $a$ 停。合起来：

$$a\to b\to c\to d\to e\to c\to a,$$

依次经过 $ab,bc,cd,de,ec,ca$，每条边恰一次，是合法欧拉回路。

(2) 删去 $cd$ 后，$d(c)=3$、$d(d)=1$，出现两个奇度顶点（个数为偶，与推论一致）。由欧拉通路判别，图有欧拉通路（必以 $c,d$ 为两端，例如 $c\to a\to b\to c\to e\to d$），但欧拉回路不存在，因为回路要求每个顶点进出次数相等。$■$

例 3（用 $A^2$ 数路径与三角形） 设 $G$ 的顶点为 $1,2,3,4$，边集为 $\{12,23,34,13,24\}$（即 $K_4$ 去掉边 $14$）。写出邻接矩阵，求从 1 到 4 长度为 2 的路径数及图中三角形个数。

解： 邻接矩阵为

$$A=\left(\begin{array}{cccc}0& 1& 1& 0\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ 0& 1& 1& 0\end{array}\right).$$

直接相乘：

$$A^2=\left(\begin{array}{cccc}2& 1& 1& 2\\ 1& 3& 2& 1\\ 1& 2& 3& 1\\ 2& 1& 1& 2\end{array}\right).$$

由定理 7，$(A^2{)}_{14}=2$，即从 1 到 4 长度为 2 的步道恰有两条：$1\to 2\to 4$ 与 $1\to 3\to 4$（本图无重边，步道即路径）。顺便验证 $(A^2{)}_{ii}=d(i)$：$d(1)=d(4)=2$、$d(2)=d(3)=3$，与 $A^2$ 对角元一致。再算

$$\mathrm{tr}(A^3)=\sum _{i=1}^4(A^3{)}_{ii}=2+4+4+2=12,$$

故三角形个数 $=12/6=2$，即 $△123$ 与 $△234$——枚举验证无误。$■$

常见错误

• 把定理 4 的等价条件当显然。 “连通且无环”与”无环且 $n-1$ 条边”之间的每一步都要靠证明：前者推边数靠删叶子归纳，后者推连通靠”各分量边数之和为 $n-c$“。考试与推导中直接引用”显然等价”是常见的失分点。
• 混淆欧拉与哈密顿的条件。 欧拉回路判的是边（每条边走一次，条件是所有度为偶且连通）；哈密顿回路判的是顶点（每个点过一次，没有简洁判据）。把”度全偶”当成哈密顿的充分条件，或拿 Dirac 定理判欧拉，都是概念错位——奇度顶点再多也不妨碍哈密顿回路存在。
• 数路径时忘记”步道”与”路径”的区别。 $A^k$ 数的是允许重复顶点的步道；只有图结构简单（如例 3 中长度为 2 时不可能重复）才能直接读成路径数。数三角形时除以 6 也不能省。

练习

1. 证明：任意 $n$ 个顶点的简单图中，至少有两个顶点的度相同。（提示：度能取哪些值？$0$ 与 $n-1$ 能否同时出现？）
2. 一棵树有 5 个度为 2 的顶点、3 个度为 3 的顶点，其余顶点全是叶子（度 1）。求叶子数。
3. 完全二分图 $K_{3,3}$ 是否有欧拉回路？是否有欧拉通路？
4. 连通图 $G$ 有欧拉回路，它的补图 $\bar{G}$ 是否也一定有欧拉回路？证明或举反例。

答案：

1. 度在 $\{0,1,\dots ,n-1\}$ 中取值共 $n$ 种，看似可各不相同；但度为 $0$ 的顶点（孤立）与度为 $n-1$ 的顶点（与所有点相邻）不能同时存在。故实际可用的度值至多 $n-1$ 个，$n$ 个顶点的度落在其中，由鸽巢原理必有两个顶点度相同。
2. 设叶子数为 $x$。顶点数 $n=x+8$，边数 $n-1=x+7$。由握手定理 $2(x+7)=5\cdot 2+3\cdot 3+x\cdot 1=19+x$，解得 $x=5$。
3. $K_{3,3}$ 每个顶点度为 3（奇），有 6 个奇度顶点，故既无欧拉回路也无欧拉通路（欧拉通路至多允许 2 个奇度顶点）。
4. 不一定。反例：$G=C_3$（三角形，$n=3$）连通且每点度 2，有欧拉回路；但 $\bar{G}$ 是 3 个孤立顶点，不连通，无欧拉回路。

延伸

想把图论接到图学习与城市计算的应用侧，本站有配套笔记：图论笔记 从邻接表与图数据结构讲起，图学习专题 则延伸到消息传递与图神经网络；矩阵一节（邻接矩阵、拉普拉斯、谱）是理解这两者的代数入口。

学习路径

• 返回 离散数学总览
• 返回 数学基础专题首页
• PREV：组合计数
• NEXT：数论初步