图论的基本数学结构

本章主线：图与路径 → 连通与可达 → 树与生成树 → 割结构 → DAG、偏序与商结构。

1 图是什么

图用来描述对象之间的联系。

一张图记作 $G=(V,E)$，其中：

• $V$ 是顶点集合；
• $E$ 是边集合。

无向图中的边写作 $\{u,v\}$，表示 $u$ 与 $v$ 之间存在无方向的联系。

有向图中的边写作 $(u,v)$ 或 $u\to v$，表示联系从 $u$ 指向 $v$。

从集合与关系的角度看，有向图中的边集满足 $E\subseteq V\times V$，因此有向图可以看成集合 $V$ 上的一个二元关系。

无向图也可以表示为对称关系：若 $(u,v)\in E$，则同时有 $(v,u)\in E$。

---

2 简单图、重边与自环

若图中不存在自环与重边，则称其为简单图。

自环是形如 $(u,u)$ 的边。

重边是连接同一对顶点的多条边。

是否允许自环与重边取决于问题模型。使用定理前应先确认图的类型。

例如，在简单无向图中，一个顶点最多与其余 $n-1$ 个顶点相邻，因此其度数最多为 $n-1$。

---

3 游走、迹、路径与环

这些概念都描述顶点之间的连续移动，但限制不同。

3.1 游走

若顶点序列

$$v_0,v_1,\dots,v_k$$

满足每一对相邻顶点之间都有边，则称其为一条游走。

游走允许重复经过顶点，也允许重复经过边。

游走的长度是经过的边数，即 $k$。

---

3.2 迹

若一条游走不重复经过任何边，则称其为迹。

迹可以重复经过顶点，但不能重复经过边。

---

3.3 路径

若一条游走不重复经过任何顶点，则称其为简单路径，通常简称路径。

路径不重复顶点，因此也不会重复边。

---

3.4 回路与环

若一条游走的起点与终点相同，则称其为闭游走。

不重复边的闭游走称为闭迹。

除起点与终点外不重复顶点的闭游走称为简单环，通常简称环。

因此限制逐步增强：

$$\text{游走}\supseteq\text{迹}\supseteq\text{路径}.$$

---

3.5 为什么存在游走就存在路径

若从 $u$ 到 $v$ 存在一条游走，并且其中某个顶点重复出现，则重复部分形成一个闭合片段。

删除该闭合片段后，仍然得到一条从 $u$ 到 $v$ 的游走，而且长度更短。

不断删除重复部分，最终得到一条没有重复顶点的路径。

因此：

两点之间存在游走，当且仅当两点之间存在路径。

这说明在研究可达性时，只需要考虑路径。

---

4 连通与可达

4.1 无向图中的连通

在无向图中，若顶点 $u$ 与 $v$ 之间存在路径，则称 $u,v$ 连通。

定义关系 $u\sim v$ 表示 $u$ 与 $v$ 连通。

该关系满足：

• 自反性：顶点到自身存在长度为 $0$ 的路径；
• 对称性：无向路径可以反向行走；
• 传递性：两条首尾相接的路径可以拼接。

因此，无向图中的连通关系是等价关系。

它产生的等价类就是连通分量。

---

4.2 有向图中的可达

在有向图中，若存在从 $u$ 到 $v$ 的有向路径，则称 $v$ 从 $u$ 可达。

单向可达通常不具有对称性，因此一般不是等价关系。

若 $u$ 可以到达 $v$，且 $v$ 也可以到达 $u$，则称 $u,v$ 互相可达。

“互相可达”满足自反性、对称性和传递性，因此是等价关系。

它产生的等价类就是强连通分量。

---

5 连通分量与图的划分

无向图的顶点集合 $V$ 会被连通关系划分为若干互不相交的连通分量：

$$V=C_1\cup C_2\cup\cdots\cup C_k.$$

这些分量满足：

• 每个 $C_i$ 非空；
• 任意两个不同分量不相交；
• 同一分量中的任意两点连通；
• 不同分量中的两点不连通。

并查集维护的正是这种动态变化的集合划分。

在有向图中，强连通分量同样构成顶点集合的一个划分。

---

6 度数与握手定理

6.1 无向图的度数

顶点 $v$ 的度数 $\deg(v)$ 是与 $v$ 相接的边数。

计算所有顶点的度数之和时，每条边都会在两个端点处各被计算一次，因此

$$\sum_{v\in V}\deg(v)=2|E|.$$

这就是握手定理。

因为右边是偶数，所以所有顶点度数之和一定是偶数。

进一步地，奇数度顶点的数量一定是偶数。因为偶数个偶数与奇数个奇数相加才可能得到奇数，而总和必须为偶数。

---

6.2 有向图的入度与出度

有向图中，顶点 $v$ 的入度记作 $\deg^-(v)$，出度记作 $\deg^+(v)$。

每条有向边贡献一次出度和一次入度，因此

$$\sum_{v\in V}\deg^+(v)=|E|,$$

$$\sum_{v\in V}\deg^-(v)=|E|.$$

所以所有顶点的总入度等于总出度。

---

7 子图、生成子图与补图

若图 $H=(V_H,E_H)$ 满足 $V_H\subseteq V$ 且 $E_H\subseteq E$，则称 $H$ 是 $G$ 的子图。

若选定顶点集合 $S\subseteq V$，并保留原图中所有两个端点都属于 $S$ 的边，则得到由 $S$ 诱导的子图，记作 $G[S]$。

生成子图包含原图的全部顶点，但只保留部分边。

简单无向图的补图 $\overline G$ 与 $G$ 有相同顶点集合，并且两个不同顶点在 $\overline G$ 中相邻，当且仅当它们在 $G$ 中不相邻。

---

8 树

8.1 树的基本定义

连通且无环的无向图称为树。

不一定连通但无环的无向图称为森林。

森林的每个连通分量都是一棵树。

---

8.2 树中任意两点之间路径唯一

设 $T$ 是一棵树。

因为 $T$ 连通，所以任意两点 $u,v$ 之间至少存在一条路径。

若存在两条不同的简单路径，它们从某处分开，又在之后重新相遇。两条路径之间的不同部分会构成一个环。

这与树无环矛盾。

因此，树中任意两点之间存在唯一简单路径。

---

8.3 唯一路径推出无环

反过来，若一张无向图中任意两点之间存在唯一简单路径，则图一定连通。

若图中存在一个环，取环上两个不同顶点。沿环的两个方向可以得到两条不同路径，与路径唯一矛盾。

因此该图无环，从而是一棵树。

于是得到等价刻画：

$$\boxed{\text{树}\Longleftrightarrow\text{任意两点之间存在唯一简单路径}}$$

---

8.4 树的边数

一棵含有 $n$ 个顶点的树恰有 $n-1$ 条边。

可以用归纳法理解。

当 $n=1$ 时，树没有边，结论成立。

任意至少含两个顶点的树都存在叶子。删除一个叶子及其相连边后，剩余图仍是一棵含 $n-1$ 个顶点的树。

若剩余树有 $n-2$ 条边，加回删除的那一条边后，原树有 $n-1$ 条边。

---

8.5 连通图的最少边数

从 $n$ 个互不连通的顶点开始，每加入一条连接两个不同连通分量的边，连通分量数量至多减少 $1$。

要将 $n$ 个分量变成一个分量，至少需要 $n-1$ 条边。

因此，任意含 $n$ 个顶点的连通图至少有 $n-1$ 条边。

若连通图恰有 $n-1$ 条边，则它不能含环。否则删除环上一条边后仍然连通，只剩 $n-2$ 条边，与连通图至少需要 $n-1$ 条边矛盾。

因此：

$$\boxed{\text{连通且有 }n-1\text{ 条边}\Longleftrightarrow\text{树}}$$

---

8.6 无环图的最多边数

森林中每加入一条连接同一连通分量内部两个顶点的边都会产生环。

若森林有 $n$ 个顶点、$c$ 个连通分量，则每个分量是一棵树，因此

$$|E|=n-c.$$

特别地，若森林有 $n-1$ 条边，则 $c=1$，所以它连通，是一棵树。

因此：

$$\boxed{\text{无环且有 }n-1\text{ 条边}\Longleftrightarrow\text{树}}$$

---

8.7 树的常用等价刻画

对于含 $n$ 个顶点的简单无向图，下列条件等价：

1. 图连通且无环；
2. 任意两点之间存在唯一简单路径；
3. 图连通且有 $n-1$ 条边；
4. 图无环且有 $n-1$ 条边；
5. 删除任意一条边后图不再连通；
6. 加入任意一条原本不存在的边后恰好产生一个环。

使用树的性质时，应根据问题选择最方便的刻画，而不是始终使用“连通且无环”。

---

9 生成树

设 $G$ 是连通无向图。

若子图 $T$ 包含 $G$ 的全部顶点，并且 $T$ 是树，则称 $T$ 是 $G$ 的生成树。

生成树保留了原图的连通性，同时删除了所有多余的环。

任意连通图都存在生成树。可以从原图开始不断删除环上的边，连通性不会被破坏，最终得到无环连通图。

也可以从空边集开始，不断加入连接不同连通分量的边，直到图连通。

Kruskal 算法采用的是第二种视角。

---

10 桥、割点与割

10.1 桥

若删除一条边后，图的连通分量数量增加，则称该边为桥。

树中的每一条边都是桥。

一条无向边是桥，当且仅当它不属于任何环。

若边位于某个环上，删除它后仍可沿环的另一侧连接两个端点，因此不是桥。

若边不属于任何环，而删除后两端点仍连通，则存在一条不经过该边的替代路径，与原边共同构成环，产生矛盾。

---

10.2 割点

若删除一个顶点及与其相连的边后，图的连通分量数量增加，则称该顶点为割点。

割点描述顶点对整体连通性的关键作用。

桥与割点都属于“删除某个局部结构后，全局连通性发生变化”的问题。

---

10.3 割

设顶点集合被划分为 $S$ 与 $V\setminus S$。

一端位于 $S$、另一端位于 $V\setminus S$ 的边组成一个割。

最小生成树中的割性质、网络流中的最小割，都建立在这种顶点集合划分之上。

---

11 DAG 与偏序

DAG 是有向无环图。

在 DAG 中定义关系：

$$u\preceq v \Longleftrightarrow u=v\text{ 或存在从 }u\text{ 到 }v\text{ 的有向路径}.$$

该关系具有：

• 自反性；
• 反对称性；
• 传递性。

因此，DAG 的可达关系构成偏序关系。

若 $u,v$ 之间互不可达，则二者在偏序中不可比较。

---

11.1 拓扑序

DAG 的拓扑序是顶点的一个线性排列，使每条有向边 $u\to v$ 都满足 $u$ 排在 $v$ 之前。

拓扑排序将原本可能存在不可比较元素的偏序，扩展成一个全序。

如果某一步有多个入度为 $0$ 的顶点可选，说明这些顶点之间暂时没有确定的先后约束，因此拓扑序可能不唯一。

---

11.2 DAG 上的动态规划

拓扑序保证：处理顶点 $v$ 时，所有可能转移到 $v$ 的前驱都已经处理。

因此，DAG 上的动态规划本质上是在偏序结构上按合法顺序计算状态。

---

12 图的收缩与商结构

若将一个顶点子集看作一个整体，并把它缩成一个新顶点，则称为图的收缩。

最常见的例子是强连通分量缩点。

同一强连通分量中的顶点互相可达，因此可以视为同一个等价类。

将每个强连通分量缩成一个点后得到缩点图。

缩点图一定是 DAG。若缩点图中存在环，则环上的各个强连通分量实际上能够互相到达，应当属于同一个更大的强连通分量，与它们已经是不同分量矛盾。

因此，强连通分量缩点可以理解为：

$$\text{有向图} \longrightarrow \text{按互相可达关系取商} \longrightarrow \text{DAG}.$$

---

13 图上的距离

在无权图中，顶点 $u,v$ 之间的距离 $d(u,v)$ 定义为从 $u$ 到 $v$ 的最短路径长度。

若 $u,v$ 不连通，则距离可以记为 $+\infty$。

无向连通图中的最短路距离满足：

• 非负性：$d(u,v)\ge0$；
• 同一性：$d(u,v)=0$ 当且仅当 $u=v$；
• 对称性：$d(u,v)=d(v,u)$；
• 三角不等式：$d(u,w)\le d(u,v)+d(v,w)$。

三角不等式来自路径拼接：从 $u$ 到 $v$ 的最短路与从 $v$ 到 $w$ 的最短路可以拼成一条从 $u$ 到 $w$ 的路径，而真正的最短路不会更长。

在带严格正边权的无向连通图中，最短路距离仍满足这些性质。若允许零权边，则不同顶点之间的距离可能为 $0$，此时得到的是伪度量，而不是严格意义上的度量。

---

14 图论结构与算法

14.1 并查集

维护无向图连通关系产生的等价类。

14.2 DFS 与 BFS

通过遍历寻找可达顶点，构造搜索树或计算无权最短路。

14.3 Kruskal

逐步加入连接不同连通分量的边，最终构造生成树。

14.4 Tarjan 类算法

利用 DFS 树结构识别桥、割点、双连通分量或强连通分量。

14.5 拓扑排序

将 DAG 的偏序关系扩展成线性顺序。

14.6 缩点

将等价类压缩为单个顶点，把复杂图转化为更简单的 DAG 或树状结构。

---

15 与后续内容的联系

• 图可以看作集合上的二元关系，参见 关系；
• 连通分量与强连通分量分别来自不同的等价关系；
• DAG 的可达关系构成偏序，拓扑序是偏序的线性扩展；
• 生成树、最短路、连通性与缩点的具体算法，应在算法知识库中继续展开；
• 路径拼接与候选选择依赖不同运算，参见 代数运算结构。

---

16 本章思考题

1. 说明游走、迹、路径之间的区别。

2. 证明从 $u$ 到 $v$ 存在游走时，一定存在简单路径。

3. 证明无向图中的连通关系是等价关系。

4. 说明有向图中的单向可达为什么通常不是等价关系。

5. 利用握手定理证明奇数度顶点的数量一定是偶数。

6. 证明树中任意两点之间存在唯一简单路径。

7. 证明含 $n$ 个顶点的树有 $n-1$ 条边。

8. 证明含 $n$ 个顶点、$n-1$ 条边的连通图一定是树。

9. 证明一条无向边是桥，当且仅当它不属于任何环。

10. 解释为什么强连通分量缩点后一定得到 DAG。

11. 解释拓扑排序为什么可能不唯一。

12. 证明无向图最短路距离满足三角不等式。