离散数学 · 图、路径与圈 学习笔记

目录

章节	标题	内容概要
1	图的基本概念	图的定义与术语、度与握手定理、度数列与 Havel-Hakimi 定理、特殊图类、同构、运算、子图与补图
2	图的矩阵表示	邻接矩阵、关联矩阵、邻接矩阵的幂与路径计数、可达矩阵
3	连通性	无向/有向连通性、距离与短程线、极大路径法、点/边连通度、Whitney 定理
4	路径与圈的基本概念	Walk / Trail / Path / Cycle 的严格定义与层级关系；简单回路与圈的辨析；通路长度定理；$\delta \ge 2$ 则含圈
5	Euler 路径与 Euler 回路	Euler 定理（必要性、充分性）、Hierholzer 算法与 Fleury 算法、Euler 图的圈分解定理
6	Hamilton 路径与 Hamilton 圈	Hamilton 路径/圈/图/半 Hamilton 图的定义；NP-完全性说明；典型正负例
7	Hamilton 图的充分条件	Ore 定理（1960）、Dirac 定理（1952）及其证明思路；闭包与 Bondy-Chvátal 定理简介
8	Hamilton 图的必要条件	连通度条件；Whitney 定理；度为 2 的顶点约束；二部图必要条件；Petersen 图非 Hamilton 证明
9	应用与拓展	马踏棋盘（Knight’s Tour）问题、TSP、中国邮路问题、邻接矩阵幂与路径计数
10	总结	核心概念层级图，Walk / Trail / Path / Cycle 的关系梳理，Euler 与 Hamilton 问题对比，注意事项

---

前言：

本章作为图论的第一章，将系统建立图的基本概念体系，并深入探讨图论中最经典的主题——路径与圈。具体安排如下：

• 图的基础概念：从图的定义出发，讨论度、握手定理、度数列与可图化（Havel-Hakimi 定理）、特殊图类（完全图、圈图、二部图等）、图的同构与运算、子图与补图。
• 图的矩阵表示：邻接矩阵、关联矩阵，以及邻接矩阵的幂与路径计数——将图的结构代数化。
• 连通性：无向图与有向图的连通性、距离与短程线、极大路径法、点/边连通度与 Whitney 定理。
• 路径与圈的层级体系：从 walk 到 trail 到 path 到 cycle，逐层施加约束，严格辨析简单回路与圈的区别，建立通路长度定理。
• Euler 问题与 Hamilton 问题：前者遍历每条边恰好一次，有完美的充要判定（TONCAS）；后者遍历每个顶点恰好一次，是 NP-完全问题
• 从理论到应用：旅行商问题（TSP）、中国邮路问题、马踏棋盘等经典场景。

---

1. 图的基本概念

1.1 图的定义

定义（图 / Graph）：
一个图是一个二元组 $G=⟨V,E⟩$（或记作 $G=(V,E)$），其中：

• $V$ 是顶点集，其元素称为顶点；
• $E$ 是边集，其元素称为边。
• $|V|=n$ 称为图的阶，$|E|=m$ 称为图的大小。

边的形式取决于图是有向还是无向：

• 无向图：边是无序对，记作 $(u,v)$ 或 {u,v}\{u, v\}{u,v}，表示 $u$ 与 $v$ 之间有一条无方向的连接；
• 有向图：边是有序对，称为弧，记作 $⟨u,v⟩$，表示从 $u$ 指向 $v$ 的有方向连接。

定义（基图）：
忽略有向图 $D$ 中所有边的方向，得到的无向图称为 $D$ 的基图。

解读：

• 图论研究的核心不是顶点和边本身，而是它们之间的连接结构；
• 同样的顶点集，不同的边集，可以形成完全不同的图；
• 基图的概念让我们可以把有向问题转化为无向问题来分析。

---

1.2 关联、环与孤立点

定义（关联）：
若边 $e=(u,v)$（或 $e=⟨u,v⟩$），则称 $u,v$ 为 $e$ 的端点，$e$ 与 $u,v$ 关联。

定义（环 / Loop）：
两端点重合的边称为环，即形如 $(v,v)$ 的边。

定义（孤立点）：
不与任何边关联的顶点称为孤立点，其度数为 0。

定义（相邻）：

• 顶点相邻：若两个顶点是同一条边的端点，则称这两个顶点相邻；
• 边相邻：若两条边有公共的顶点，则称这两条边相邻。

关联次数的说明：

• 若 $e$ 不是环，顶点 $v$ 与边 $e$ 的关联次数为 1（$v$ 是 $e$ 的一个端点）；
• 若 $e$ 是环（$e=(v,v)$），则顶点 $v$ 与边 $e$ 的关联次数为 2。

---

1.3 邻域与关联集

定义（邻域）：
在无向图中，顶点 $v$ 的邻域定义为
N(v)={u∈V∣(u,v)∈E}N(v) = \{u \in V \mid (u, v) \in E\}N(v)={u∈V∣(u,v)∈E}
即与 $v$ 相邻的所有顶点构成的集合。

定义（闭邻域）：
N[v]=N(v)∪{v}N[v] = N(v) \cup \{v\}N[v]=N(v)∪{v}

定义（关联集）：
I(v)={e∈E∣e 与 v 关联}I(v) = \{e \in E \mid e \text{ 与 } v \text{ 关联}\}I(v)={e∈E∣e 与 v 关联}

有向图中的特殊概念：

• 后继集：N+(v)={u∈V∣⟨v,u⟩∈E}N^+(v) = \{u \in V \mid \langle v, u \rangle \in E\}N+(v)={u∈V∣⟨v,u⟩∈E}，即从 $v$ 出发的弧所到达的顶点集；
• 前驱集：N−(v)={u∈V∣⟨u,v⟩∈E}N^-(v) = \{u \in V \mid \langle u, v \rangle \in E\}N−(v)={u∈V∣⟨u,v⟩∈E}，即到达 $v$ 的弧所来自的顶点集。

---

1.4 简单图与多重图

定义（平行边）：
连接同一对顶点的多于一条边称为平行边。

定义（简单图）：
既没有环也没有平行边的图称为简单图。

定义（多重图 ）：
含有平行边的图称为多重图。

---

1.5 顶点的度数

定义（度数）：

• 无向图：顶点 $v$ 的度数（degree）记为 $d(v)$，是与 $v$ 关联的边数（环计算两次）。
• 有向图：
  • 入度：$d^{-}(v)$，以 $v$ 为终点的边数；
  • 出度：$d^{+}(v)$，以 $v$ 为起点的边数；
  • 度数：$d(v)=d^{-}(v)+d^{+}(v)$。

定义（度数为 0 或 1 的顶点）：

• 孤立点：度数为 0 的顶点；
• 叶点（leaf）：度数为 1 的顶点。

定义（最小度与最大度）：

• 最小度：δ(G)=min⁡{d(v)∣v∈V(G)}\delta(G) = \min\{d(v) \mid v \in V(G)\}δ(G)=min{d(v)∣v∈V(G)}；
• 最大度：Δ(G)=max⁡{d(v)∣v∈V(G)}\Delta(G) = \max\{d(v) \mid v \in V(G)\}Δ(G)=max{d(v)∣v∈V(G)}。
• 对于有向图，可以定义最小入度，最小出度，这里不详细写出来了

---

1.6 握手定理（Handshaking Lemma）

定理（握手定理）：

1. 无向图：所有顶点的度数之和等于边数的两倍，即
   $$\sum _{v\in V}d(v)=2|E|$$
2. 有向图：所有顶点的入度之和等于出度之和，且都等于边数，即
   $$\sum _{v\in V}{d}^{-}(v)=\sum _{v\in V}{d}^{+}(v)=|E|$$

证明：每条边有两个端点（无向图）或一个起点一个终点（有向图），对度数总和的贡献恰好是 2（无向图）或分别计入入度和出度（有向图）。对所有边求和即得。

推论：
任何图中，度数为奇数的顶点个数必为偶数。

证明：设 $V_{odd}$ 为奇度顶点集，$V_{even}$ 为偶度顶点集。由握手定理，${\sum }_{v\in V_{odd}}d(v)+{\sum }_{v\in V_{even}}d(v)=2|E|$。右边为偶数，第二项也为偶数，故第一项必为偶数。而奇数个奇数之和为奇数，所以 $|V_{odd}|$ 必为偶数。

意义：握手定理是图论中最基础、最常用的定理之一。它是 Euler 定理必要性证明的核心依据——奇度顶点的个数只能是 0、2、4、6、…，从而为"0 或 2"的结论埋下伏笔。

例子：设图 $G$ 有 10 条边，4 个 3 度顶点，其余顶点的度数均为 2，求 $G$ 的顶点数。

解：设顶点数为 $n$。由握手定理：$4\times 3+(n-4)\times 2=2\times 10$，即 $12+2n-8=20$，解得 $2n=16$，$n=8$。故顶点数为 8。

---

1.7 度数列与可图化

定义（度数列）：
设 $G=(V,E)$ 为一个 $n$ 阶图，称 $d(v_1),d(v_2),\dots ,d(v_n)$ 为 $G$ 的度数列。

定义（可图化）：
给定一个非负整数列 $d=(d_1,d_2,\dots ,d_n)$，若存在一个图 $G$，使得 $G$ 的度数列恰好是 $d$，则称 $d$ 是可图化的。

定义（可简单图化）：
若存在一个简单图 $G$，使得 $G$ 的度数列恰好是 $d$，则称 $d$ 是可简单图化的。

可图化的必要条件：
由握手定理，${\sum }_{i=1}^n{d}_i$ 必须是偶数。这是可图化的必要但非充分条件。

---

1.8 Havel-Hakimi 定理（度序列可图性判断）

定理（哈维尔-哈基米）：
设 $d=(d_1,d_2,\dots ,d_n)$ 是一个非负整数序列（$d_1\ge d_2\ge \cdots \ge d_n$），$d$ 是可简单图化的当且仅当序列
$$d^{\prime }=(d_2-1,d_3-1,\dots ,d_{d_1+1}-1,d_{d_1+2},\dots ,d_n)$$
（将其后 $d_1$ 个元素各减 1，再排序为非增序列后）也是可简单图化的。

• 证明略

算法步骤：

1. 将序列按降序排列；
2. 移除最大元素 $d_1$；
3. 将其后的 $d_1$ 个元素各减 1；
4. 若出现负数，则不可简单图化；若全为 0，则可简单图化；否则返回步骤 1。

例子：下列度数列中可简单图化的是哪一个？

• A. $(4,4,4,4,2)$：移出 4，后 4 个减 1 得 $(3,3,3,1)$，再移出 3 后 3 个减 1 得 $(2,2,0)$，再移出 2 后 2 个减 1 得 $(1,-1)$，出现负数，不可简单图化。
• B. $(4,4,3,3,1)$：度数之和为 15（奇数），由握手定理可知不可图化。
• C. $(4,4,3,3,2,1)$：度数之和为 17（奇数），不可图化。
• D. $(4,4,3,3,2,2)$：移出 4，后 4 个减 1 得 $(3,2,2,1,2)$，排序为 $(3,2,2,2,1)$；移出 3，后 3 个减 1 得 $(1,1,1,1)$；移出 1，后 1 个减 1 得 $(0,1,1)$，排序为 $(1,1,0)$；移出 1，后 1 个减 1 得 $(0,0)$，全为 0，可简单图化。

解读：Havel-Hakimi 定理提供了一个可操作的判定算法，将"是否存在这样的简单图"这一存在性问题转化为反复进行的代数操作。

---

1.9 特殊图类

以下介绍图论中几种最常见、最重要的特殊图类。

1.9.1 完全图

定义（完全图）：
每对顶点间都有一条边的简单图称为完全图，记为 $K_n$（$n$ 为顶点数）。

性质：

• $K_n$ 的边数为 $\frac{n(n-1)}{2}$；
• $K_n$ 中每个顶点的度均为 $n-1$。
• $K_n$是 $(n-1)$-正则图。

1.9.2 圈图

定义（圈图）：
由一个圈围成的图称为圈图（或回路图），记为 $C_n$（$n\ge 3$）。

性质：

• $C_n$ 有 $n$ 个顶点和 $n$ 条边；
• $C_n$ 中每个顶点的度均为 2，即 $C_n$ 是 2-正则图。

1.9.3 轮图

定义（轮图）：
在 $C_n$ 的基础上增加一个中心点，并将该中心点与 $C_n$ 的所有顶点相连，得到的图称为轮图，记为 $W_n$。

性质：

• $W_n$ 有 $n+1$ 个顶点和 $2n$ 条边；
• 中心点度为 $n$，外围点度为 3。

1.9.4 正则图

定义（正则图）：
每个顶点的度数都相等的图称为正则图。若度数均为 $k$，则称为 $k$-正则图。

• $K_n$ 是 $(n-1)$-正则图；
• $C_n$ 是 2-正则图；

1.9.5 竞赛图

定义（竞赛图）：
基图为完全图 $K_n$ 的有向图称为竞赛图。

性质：

• 竞赛图中任意两个顶点 $u,v$ 之间恰有一条有向边（$⟨u,v⟩$ 或 $⟨v,u⟩$）（竞赛图由完全图得来）；
• $n$ 阶竞赛图的边数为 $\frac{n(n-1)}{2}$；
• 所有顶点的出度之和等于 $\frac{n(n-1)}{2}$。（对于有向图而言，出度之和 = 总边数）

1.9.6 二部图

定义（二部图）：
设 $G=(V,E)$ 为一个无向图，如果可以将 $V$ 划分为两个不相交的子集 $V_1$ 和 $V_2$（$V=V_1\cup V_2$，$V_1\cap V_2=\varnothing$），使得每条边都连接 $V_1$ 中的一个顶点与 $V_2$ 中的一个顶点（即 $V_1$ 内部和 $V_2$ 内部都没有边），则称 $G$ 为二部图（或二分图、偶图）。

定义（完全二部图）：
若二部图 $G$ 中 $V_1$ 的每个顶点都与 $V_2$ 的每个顶点相邻，则称 $G$ 为完全二部图，记为 $K_{m,n}$，其中 $m=|V_1|$，$n=|V_2|$。

性质：

• $K_{m,n}$ 的边数为 $m\cdot n$；
• $K_{m,n}$ 中 $V_1$ 中每个顶点度为 $n$，$V_2$ 中每个顶点度为 $m$。

定理（二部图的判定）：
一个图是二部图当且仅当它不含奇数长度的圈（即不含奇圈）。

---

1.10 图的同构

定义（同构）：
设 $G_1=(V_1,E_1)$ 和 $G_2=(V_2,E_2)$ 是两个图。若存在双射 $f:V_1\to V_2$，使得 $(u,v)\in E_1$ 当且仅当 $(f(u),f(v))\in E_2$，则称 $G_1$ 与 $G_2$ 同构，记为 $G_1\cong G_2$。

直观理解：
两个图同构，意味着它们"结构相同"，只是顶点的标签不同。如果把一个图的顶点重新命名，就可以得到另一个图。

同构的必要条件（用于排除非同构）：

• 顶点数相同；
• 边数相同；
• 度数列相同。

注意：以上条件都是必要但不充分的。存在顶点数、边数、度数列都相同但仍不同构的图。（例如$K_{3,3}$）和三角柱图并不同构）

定义（自补图）：
若图 $G$ 与其补图 $\overline{G}$ 同构，则称 $G$ 为自补图。

性质：$n$ 阶自补图的边数为 $m=\frac{n(n-1)}{4}$，故 $n$ 必须满足 $n\equiv 0$ 或 $1(\mathrm{mod}4)$。

---

1.11 图的运算

定义（删除点）：
从图 $G$ 中删除顶点 $v$ 及其所有关联的边，记作 $G-v$。若删除顶点子集 $V^{\prime }\subseteq V$，记作 $G-V^{\prime }$。

定义（删除边）：
从图 $G$ 中删除边 $e$，但保留其端点，记作 $G-e$。

定义（加新边）：
在图 $G$ 的不相邻顶点 $u,v$ 之间添加一条新边 $e=(u,v)$，记作 $G+e$。

定义（边的收缩）：
删除边 $e=(u,v)$，并将 $u$ 与 $v$ 合并为一个新顶点，使原先与 $u$ 或 $v$ 关联的所有边都与这个新顶点关联，记作 $G\cdot e$。

例子：

• 设 $G$ 是 $n$ 阶 $m$ 条边的图，求 $G-v$ 的顶点数和边数（设 $d(v)=k$）。解：$G-v$ 有 $n-1$ 个顶点和 $m-k$ 条边。
• 设 $G$ 是 $n$ 阶 $m$ 条边的简单图，收缩一条边 $e$ 后，新图的顶点数是 $n-1$ 个。

---

1.12 子图与补图

定义（子图）：
设 $G=(V,E)$ 和 $G^{\prime }=(V^{\prime },E^{\prime })$ 是两个图。若 $V^{\prime }\subseteq V$ 且 $E^{\prime }\subseteq E$，则称 $G^{\prime }$ 是 $G$ 的子图。

定义（生成子图）：
若 $G^{\prime }$ 是 $G$ 的子图且 $V^{\prime }=V$（即包含 $G$ 的所有顶点），则称 $G^{\prime }$ 是 $G$ 的生成子图。

定义（导出子图）：
设 $V^{\prime }\subseteq V$，由 $V^{\prime }$ 及其在 $G$ 中所有两端点都在 $V^{\prime }$ 中的边构成的子图，称为 $G$ 的导出子图。

定义（补图）：
设 $G=(V,E)$ 是 $n$ 阶简单图，$G$ 的补图 $\overline{G}$ 定义为：顶点集仍为 $V$，边集为 $K_n$ 中不在 $G$ 中的所有边。即
$$E(\overline{G})=\{(u,v)\mid u,v\in V,u\ne v,(u,v)\notin E\}$$

定理：若 $G$ 是不连通的图，则其补图 $\overline{G}$ 必连通。（连通见3.）

证明：设 $u,v$ 是 $\overline{G}$ 中任意两个顶点。

• 若 $u,v$ 在 $G$ 中属于不同的连通分支，则 $u,v$ 在 $G$ 中不相邻，故在 $\overline{G}$ 中相邻，连通。
• 若 $u,v$ 在 $G$ 中属于同一个连通分支，设 $w$ 是 $G$ 中另一个连通分支的顶点。则 $u,w$ 和 $v,w$ 在 $G$ 中均不相邻（因属于不同分支），故在 $\overline{G}$ 中均相邻。从而 $u-w-v$ 是 $\overline{G}$ 中的一条通路，连通。

---

2. 图的矩阵表示

图除了用集合论的顶点-边二元组描述外，还可以用矩阵来描述。矩阵表示将图的结构代数化，使得我们可以借助线性代数的工具来分析图的性质——特别是路径计数、连通性判定等问题。

2.1 邻接矩阵

定义（邻接矩阵）：
设 $G=(V,E)$ 是一个 $n$ 阶图，V={v1,v2,…,vn}V = \{v_1, v_2, \ldots, v_n\}V={v1​,v2​,…,vn​}，则 $G$ 的邻接矩阵 $A=(a_{ij}{)}_{n\times n}$ 定义为：
$$a_{ij}=\text{从 }{v}_i\text{ 到 }{v}_j\text{ 的边数}$$

对于无向简单图，aij∈{0,1}a_{ij} \in \{0, 1\}aij​∈{0,1}，且 $A$ 是对称矩阵（$a_{ij}=a_{ji}$）。

性质：

• $A$ 的对角元 $a_{ii}$ 为顶点 $v_i$ 上环的个数（无环简单图为 0）；
• 第 $i$ 行元素之和等于顶点 $v_i$ 的出度（有向图）或度（无向图）；
• 第 $j$ 列元素之和等于顶点 $v_j$ 的入度（有向图）或度（无向图）。

2.2 关联矩阵

定义（关联矩阵）：
设 $G=(V,E)$ 是一个 $n$ 阶 $m$ 条边的无向图，V={v1,…,vn}V = \{v_1, \ldots, v_n\}V={v1​,…,vn​}，E={e1,…,em}E = \{e_1, \ldots, e_m\}E={e1​,…,em​}，则 $G$ 的关联矩阵 $M=(m_{ij}{)}_{n\times m}$ 定义为：
$$m_{ij}=\{\begin{array}{ll}1,& \text{若 }{v}_i\text{ 与 }{e}_j\text{ 关联}\\ 0,& \text{否则}\end{array}$$

注：若有环，则对应元素记为 2（因为环与顶点的关联次数为 2）。

与邻接矩阵的对比：

• 邻接矩阵是 $n\times n$ 方阵，行/列对应顶点，元素表示顶点间的连接；
• 关联矩阵是 $n\times m$ 矩阵，行对应顶点，列对应边，元素表示顶点与边的关联关系。

2.3 邻接矩阵的幂与路径计数

定理（邻接矩阵的幂）：
设 $A$ 是图 $G$ 的邻接矩阵，则 $A^k$（$k\ge 1$）中第 $(i,j)$ 个元素 $(A^k{)}_{ij}$ 等于从顶点 $v_i$ 到顶点 $v_j$ 的长度为 $k$ 的通路（walk）数目。

证明思路（数学归纳法）：

• 基例 $k=1$：$A^1=A$，$a_{ij}$ 就是从 $v_i$ 到 $v_j$ 的长度为 1 的通路数（即边数），成立。
• 归纳步骤：设 $A^k$ 的元素表示长度为 $k$ 的通路数。$A^{k+1}=A^k\cdot A$，其 $(i,j)$ 元为
  $$\sum _{l=1}^n(A^k{)}_{il}\cdot a_{lj}$$
  这恰好枚举了"从 $v_i$ 出发，用 $k$ 步走到某个中间顶点 $v_l$，再用 1 步走到 $v_j$"的所有路径。

特别地：

• $(A^2{)}_{ii}=d(v_i)$（对角元为对应顶点的度）；
• 若所有对角元 $(A^n{)}_{ii}>0$，则图中存在经过 $v_i$ 的回路。

意义：
这一定理将图的路径问题转化为矩阵运算，是图论与代数结合的经典范例，也是 Warshall 算法求传递闭包的理论基础。

2.4 可达矩阵

定义（可达矩阵）：
设 $G$ 是一个 $n$ 阶图，$G$ 的可达矩阵 $P=(p_{ij}{)}_{n\times n}$ 定义为：
$$p_{ij}=\{\begin{array}{ll}1,& \text{若 }{v}_i\text{ 可达 }{v}_j\text{（即存在从 }{v}_i\text{ 到 }{v}_j\text{ 的通路）}\\ 0,& \text{否则}\end{array}$$

计算方法：
$$P=I\vee A\vee A^2\vee \cdots \vee A^{n-1}$$
其中 $\vee$ 为逻辑或运算（将非零元素视为 1），$I$ 为单位矩阵。

解读：

• 可达矩阵的元素只取 0 或 1，不关心通路的具体条数；
• $P$ 是全 1 矩阵（除对角线外）当且仅当图是强连通的；
• 计算可达矩阵的过程本质上是在求图的传递闭包（可以用之前关系章节的warshell算法求解）。

---

3. 连通性

连通性是图论中最核心的概念之一。一个图是否"连在一起"，直接决定了其是否具有路径、是否可以遍历、是否含有圈等基本性质。本章从无向图和有向图两个角度讨论连通性，并引入距离、极大路径法、连通度等重要工具。

3.1 无向图的连通性

定义（连通图）：
在无向图 $G$ 中，若任意两个顶点之间都存在通路（walk）（见后续），则称 $G$ 为连通图。

定义（连通分支）：
无向图 $G$ 的连通分支（或连通分量）是 $G$ 的极大连通子图。即一个子图本身是连通的，且不能再添加 $G$ 中的其他顶点而保持连通。

• 连通图恰好有 1 个连通分支（即它自身）；
• 不连通图有 2 个或更多的连通分支。

定义（连通分支数）：
图 $G$ 中连通分支的个数记为 $p(G)$。

3.2 有向图的连通性

有向图的连通性比无向图更复杂，需要区分三种不同层次的连通性。

定义（强连通）：
有向图 $D$ 中，若任意两个顶点 $u,v$ 都互相可达（即存在从 $u$ 到 $v$ 的有向通路，也存在从 $v$ 到 $u$ 的有向通路），则称 $D$ 为强连通图。

定义（单向连通）：
有向图 $D$ 中，若任意两个顶点 $u,v$，$u$ 可达 $v$ 或 $v$ 可达 $u$（至少一个方向可达），则称 $D$ 为单向连通图。

定义（弱连通）：
若有向图 $D$ 的基图（忽略方向后的无向图）是连通的，则称 $D$ 为弱连通图。

关系：
$$\text{强连通}\Rightarrow \text{单向连通}\Rightarrow \text{弱连通}$$

定理（有向图连通性判定）：

• 强连通判定：有向图 $D$ 是强连通的，当且仅当 $D$ 中存在一条经过所有顶点的回路（closed walk）；
• 单向连通判定：有向图 $D$ 是单向连通的，当且仅当 $D$ 中存在一条经过所有顶点的通路（walk）。

3.3 距离与短程线

定义（距离）：
设 $u,v$ 是图 $G$ 的两个顶点，$u$ 到 $v$ 的距离 $d(u,v)$ 定义为从 $u$ 到 $v$ 的最短通路的长度。若 $u$ 与 $v$ 之间不存在通路，则 $d(u,v)=\infty$。

定义（短程线）：
连接 $u$ 与 $v$ 的长度最短的通路称为 $u$ 到 $v$ 的短程线。

定义（图的直径）：
图 $G$ 的直径定义为
$$\text{diam}(G)=\underset{u,v\in V}{\max }d(u,v)$$
即所有顶点对之间距离的最大值。

3.4 极大路径法

定义（极大路径）：
在有限图中，一条极大路径是不能再向两端延伸的路径。即若 $P=v_1\to v_2\to \cdots \to v_k$ 是极大路径，则 $v_1$ 的所有邻接顶点都在 $P$ 中（否则可以在 $v_1$ 端延长），$v_k$ 的所有邻接顶点也都在 $P$ 中。

核心思想：
有限图中顶点数有限，必然存在至少一条极大路径。设 $P=v_1,v_2,\dots ,v_k$ 是极大路径，则 $v_1$ 的所有邻接点必在 $P$ 中（否则可将该邻接点接在 $v_1$ 前面，延长路径，与"极大"矛盾）。

应用：极大路径法是图论证明中极其常用的技巧，常用于证明图中圈的存在性、估算圈的长度，以及研究图的连通性质。（后续会给出一个应用）

3.5 点连通度与边连通度

连通性可以"量化"——我们不仅关心图是否连通，还关心"有多连通"，连通性之间进行比较。

定义（点连通度）：
图 $G$ 的点连通度记为 $\kappa (G)$，是为了使图 $G$ 变为不连通图或平凡图所需移除的最少顶点数目。

定义（边连通度）：
图 $G$ 的边连通度记为 $\lambda (G)$，是为了使图 $G$ 变为不连通图所需移除的最少边数目。

• 对于完全图 $K_n$，$\kappa (K_n)=n-1$；
• 对于不连通图，$\kappa (G)=\lambda (G)=0$。
• 定义破坏连通性，即删掉点或边后，连通分支增加。

3.6 Whitney 定理（惠特尼定理）

定理（Whitney’s Theorem）：
对于任何图 $G$，有
$$\kappa (G)\le \lambda (G)\le \delta (G)$$

即：点连通度 $\le$ 边连通度 $\le$ 最小度。

证明思路：
（不妨设我们研究的图是三阶以上连通非完全简单图，否则结论易得）

• $\lambda (G)\le \delta (G)$：移除与最小度顶点关联的所有 $\delta (G)$ 条边，该顶点即成为孤立点，图不连通。故只需移除至多 $\delta (G)$ 条边即可使图不连通。
• $\kappa (G)\le \lambda (G)$：设 $E^{\prime }$ 是使 $G$ 不连通的最少边集（$|E^{\prime }|=\lambda (G)$）。移除 $E^{\prime }$ 后图分裂为两个连通分支 $G_1$ 和 $G_2$。$E^{\prime }$ 中的每条边都有一个端点在 $G_1$ 中、一个端点在 $G_2$ 中。选择 $G_1$ 中与 $E^{\prime }$ 关联的顶点集 $S$，则 $|S|\le |E^{\prime }|$（因为每条边至少贡献一个端点），移除 $S$ 即可使图不连通。故 $\kappa (G)\le |S|\le \lambda (G)$。

解读：

• 移除一个顶点可能"切断"多条关联边，所以点连通度通常不超过边连通度；

---

4. 路径与圈的基本概念

在图 $G=(V,E)$ 中，路径与圈的研究是图论最基础也最重要的内容之一。本节从最基本的 “walk” 开始，逐步通过施加约束条件，引出 trail、path 和 cycle 的层级结构。

4.1 Walk（道路）

定义（Walk / 道路）：
给定图 $G=(V,E)$，图 $G$ 中的一条有限 walk 是形如
$$v_0,e_1,v_1,e_2,v_2,\dots ,e_m,v_m$$
的顶点与边的交替序列，其中每条边 $e_i=(v_{i-1},v_i)\in E$。等价地，可表示为顶点的交替序列：
$$v_0\to v_1\to v_2\to \cdots \to v_m$$
称这条 walk 是从初始顶点 $v_0$ 到终止顶点 $v_m$ 的 walk。整数 $m$ 称为该 walk 的长度（length，即经过的边数）。

解读：

• Walk 是图中最"宽松"的行进方式——允许重复经过顶点和边；
• Walk 的长度是指边的重复计数，而非不同边的数目；
• 单个顶点 $v$ 本身可视为长度为 0 的平凡 walk。

例子：在下图中

    D --- E --- B --- C
          |
          F

序列 $D\to E\to B\to C\to B\to E\to F$ 是一条从 $D$ 到 $F$ 的 walk，长度为 6。注意顶点 $B$ 和 $E$ 均被重复访问，边 {B,E}\{B,E\}{B,E} 也被重复使用——这是 walk 允许的行为。

---

4.2 Trail（迹）

定义（Trail / 迹）：
一条 trail 是所有边互不相同的 walk。

解读：

• Trail 在 walk 的基础上增加了约束：不允许重复经过同一条边；
• 但 trail 允许重复经过顶点（只要不是通过同一条边到达）；
• "迹"这个中文译名形象地表达了"留下痕迹而不重复"的含义。

例子：延续上图：

• $D\to E\to B\to C$ 是一条 trail（边 {D,E},{E,B},{B,C}\{D,E\}, \{E,B\}, \{B,C\}{D,E},{E,B},{B,C} 互不相同）；
• $D\to E\to F$ 也是一条 trail；
• 但 $D\to E\to B\to C\to B\to E\to F$ 不是 trail，因为边 {B,C}\{B,C\}{B,C} 和 {B,E}\{B,E\}{B,E} 均被重复使用。

---

4.3 Path（路径）

定义（Path / 路径）：
一条 path 是所有顶点互不相同的 trail。

解读：

• Path 在 trail 的基础上进一步约束：不允许重复经过任何顶点（因此自然也不会重复经过任何边）；
• 顶点互不相同 $\Rightarrow$ 边互不相同，所以 path $\subseteq$ trail $\subseteq$ walk；
• Path 是图论中最重要的概念之一，很多图论问题最终都归结为寻找满足某种性质的 path。

例子：$D\to E\to B\to C$ 是一条 path（顶点 $D,E,B,C$ 互不相同）。而 $D\to E\to B\to C\to B$ 不是 path，因为顶点 $B$ 重复出现。

---

4.4 层级关系总结

三种概念形成严格的包含关系：

$$\boxed{\text{Path (顶点互异)}⊊\text{Trail (边互异)}⊊\text{Walk (无约束)}}$$

概念	中文	边可重复？	顶点可重复？	严格程度
Walk	道路 / 行走	是	是	最宽松
Trail	迹	否	是	中等
Path	路径	否	否	最严格

---

4.5 闭 Walk / Trail / Path 与 Cycle（圈）

定义（闭 Walk）：
一条 walk（或 trail，或 path）称为闭的（closed），如果其初始顶点与终止顶点相同，即 $v_0=v_m$。

定义（Cycle / 圈）：
一个 cycle 是至少含有一条边的闭 path。即满足 $v_0=v_m$ 且 $v_0,v_1,\dots ,v_{m-1}$ 互不相同的 path。

解读：

• Cycle 要求：除起点=终点外，其余顶点互不相同；
• "至少含有一条边"排除了单个顶点构成的平凡情形；
• 长度为 $k$ 的 cycle 称为 $k$-cycle，记为 $C_k$；
• 三角形（triangle）即 $C_3$，是最小的 cycle。

---

4.6 简单回路与圈的辨析

对"回路"做进一步细分：

中文术语	英文对应	核心约束	例子
通路	walk	无约束	$v_1\to v_2\to v_1\to v_3$
简单通路	trail	边不重复	$v_1\to v_2\to v_3\to v_1\to v_4$
初级通路 / 路径	path	顶点不重复	$v_1\to v_2\to v_3\to v_4$
回路	closed walk	起点 = 终点	$v_1\to v_2\to v_3\to v_1\to v_2\to v_1$
简单回路	closed trail	边不重复，起点 = 终点	$v_1\to v_2\to v_3\to v_4\to v_2\to v_1$
初级回路 / 圈	cycle	顶点不重复（除起点 = 终点外）	$v_1\to v_2\to v_3\to v_1$

---

4.7 通路长度定理

定理（通路长度定理）：

1. 在 $n$ 阶图 $G$ 中，若从顶点 $v_i$ 到 $v_j$（$v_i\ne v_j$）存在通路，则 $v_i$ 到 $v_j$ 一定存在长度小于或等于 $n-1$ 的初级通路（路径）；
2. 在 $n$ 阶图 $G$ 中，若存在 $v_i$ 到自身的回路，则一定存在 $v_i$ 到自身长度小于或等于 $n$ 的回路。

证明思路：
若通路中存在重复顶点 $v_k$，即 $v_i\to \cdots \to v_k\to \cdots \to v_k\to \cdots \to v_j$，则删除从 $v_k$ 到 $v_k$ 之间的那段回路，得到一条更短的通路。反复删除重复顶点，最终可得所有顶点互不相同的路径。由于最多有 $n$ 个顶点，非回路路径长度 $\le n-1$；回路最多经过 $n$ 个不同顶点后回到起点，长度 $\le n$。

推论：
在 $n$ 阶图 $G$ 中，若存在 $v_i$ 到自身的简单回路，则一定存在 $v_i$ 到自身长度小于或等于 $n$ 的初级回路（圈）。

---

4.8 $\delta \ge 2$ 则含圈（极大路径法应用）

在第 3.4 节中我们已经介绍了极大路径法，这里给出一个经典应用。

引理：
设 $G$ 为 $n$（$n\ge 3$）阶无向简单图，若 $\delta (G)\ge 2$（每个顶点度至少为 2），则 $G$ 中一定含有圈。

证明（极大路径法）：

1. 取 $G$ 中的一条极大路径 $P=v_1\to v_2\to \cdots \to v_k$；
2. 由于 $P$ 是极大路径，$v_1$ 的所有邻接点都在 $P$ 中（否则 $P$ 可延长，矛盾）；
3. 由 $\delta (G)\ge 2$，$v_1$ 至少有两个邻接点；
4. 设 $v_i$ 是 $v_1$ 在 $P$ 上最远的邻接点（$i\ge 3$，因 $v_2$ 是 $P$ 上 $v_1$ 的邻接点之一，而 $v_1$ 至少有两个邻接点），则 $v_1\to v_2\to \cdots \to v_i\to v_1$ 构成一个长度至少为 3 的圈。

推广：若 $\delta (G)\ge 3$，则可进一步证明 $G$ 中存在长度大于或等于 4 的圈（证明思路类似：$v_1$ 至少有 3 个邻接点在 $P$ 上，取最远的两个邻接点 $v_a,v_b$，则 $v_1\to v_2\to \cdots \to v_b\to v_1$ 的长度至少为 4）。

---

5. Euler 路径与 Euler 回路

Euler 问题起源于七桥问题，本节给出完整的判定定理。

5.1 Euler Trail 与 Euler Tour 的定义

定义（Euler Trail / 欧拉迹）：
经过图中每条边恰好一次的 trail 称为 Euler trail（欧拉迹 / Euler 路径）。

定义（Euler Tour / 欧拉回路）：
经过图中每条边恰好一次的闭 trail 称为 Euler tour（欧拉回路）或 Euler circuit。含有 Euler tour 的图称为 Eulerian graph（欧拉图）。

直观区别：

• Euler trail：可以有不同的起点和终点，走遍所有边恰好一次；
• Euler tour：起点=终点，走遍所有边恰好一次后回到出发点（即闭合的 Euler trail）。

---

5.2 必要条件

引理（Euler Trail 的必要条件）：
若图 $G$ 存在 Euler trail，则 $G$ 中度为奇数的顶点个数为 0 或 2。

证明思路：
考虑一条 Euler trail $v_0\to v_1\to \cdots \to v_m$。对于 trail 的中间顶点 $v_i$（$0<i<m$），每次进入 $v_i$ 必然随后离开，因此每次经过 $v_i$ 贡献度 2。故中间顶点的度必为偶数。

对于端点 $v_0$ 和 $v_m$：

• 若 $v_0=v_m$（Euler tour），则两端点贡献也是偶数，所有顶点度为偶数（0 个奇度顶点）；
• 若 $v_0\ne v_m$（Euler trail 非闭），则 $v_0$ 和 $v_m$ 各多贡献 1，恰有 2 个奇度顶点。

推论：柯尼斯堡七桥问题对应的图有 4 个奇度顶点，因此不存在 Euler trail。

---

5.3 Euler 定理（充分性）

定理（Euler’s Theorem/ Hierholz）：
一个连通图 $G$ 存在 Euler trail 当且仅当 $G$ 中度为奇数的顶点个数为 0 或 2。

• 若奇度顶点个数为 0，则存在 Euler tour（欧拉回路）；
• 若奇度顶点个数为 2，则存在 Euler trail（非闭），且这两个奇度顶点恰为 trail 的端点。

历史回顾：

• Euler 于 1736 年证明了必要性（"仅当"方向），但没有证明充分性（"当"方向）；
• Carl Hierholzer（1840–1871）于 1873 年给出了第一个完整的充分性证明；
• Pierre-Henry Fleury 于 1883 年给出了另一个著名的证明

证明思路（Hierholzer 法，归纳法）：

对边数 $m$ 进行归纳。

基例：$m=0$（单点图），显然成立。

归纳步骤：设每个顶点度均为偶数（0 个奇度顶点情形）。

1. 找圈：由第 4.8 节引理（$\delta \ge 2$ 则含圈），可从任意顶点出发沿未访问的边行走，由于每个顶点度为偶数（$\ge 2$），最终必回到起点，形成一个 cycle $C$；
2. 删除圈：令 $G^{\prime }=G-C$（删除 $C$ 中的所有边），$G^{\prime }$ 的每个连通分支仍满足偶度条件；
3. 归纳假设：由归纳假设，$G^{\prime }$ 的每个连通分支都有 Euler tour；
4. 拼接：将 $C$ 与各连通分支的 Euler tour 在公共顶点处拼接，得到 $G$ 的 Euler tour。
   

TONCAS 性质：Euler 定理是图论中最经典的 TONCAS（“The Obvious Necessary Conditions are Also Sufficient”——显然的必要条件也是充分的）范例之一。

---

5.4 Euler 图的圈分解

定理（Euler 图的圈分解）：
每个 Euler 图（连通且所有顶点度为偶数）都可以分解为若干边不相交的 cycle 的并。

解读：

• "分解"意味着图的边集可以被划分为若干个 cycle 的边集之并；
• 这是 Hierholzer 证明的自然推论——每次找到的 cycle $C$ 与剩余部分的分解拼接起来；
• 直观理解：欧拉图可以看作若干个 cycle "叠加"而成。
  

---

5.5 找 Euler Tour 的算法

5.5.1 Hierholzer 算法

基本思想：从起点出发，沿未访问的边随便走，直到形成一个回路；然后在该回路上寻找还有未访问边的顶点，从该顶点出发继续构造新回路，将新回路拼入旧回路。

步骤：

1. 从任意顶点 $v$ 开始，沿未访问的边随意行走，直到回到 $v$，得到 cycle $C$；
2. 若 $C$ 包含所有边，结束；
3. 否则，在 $C$ 上找到一个还有未访问关联边的顶点 $u$；
4. 从 $u$ 出发继续步骤 1，得到新 cycle $C^{\prime }$；
5. 将 $C^{\prime }$ 拼接到 $C$ 中（在 $u$ 处"插入"），更新 $C$；
6. 重复步骤 2–5。

时间复杂度：$O(m)$，每条边仅被访问一次。

5.5.2 Fleury 算法

基本思想：除非别无选择，否则不走"桥"（删除会使图不连通的边）。

步骤：

1. 选择正确的起始顶点（奇度顶点之一，或任意顶点若全为偶度）；
2. 在当前顶点处，优先选择非桥边（即删除该边后图仍保持连通的边）；
3. 若所有关联边都是桥，则选择其中一条；
4. 走过该边后删除之，移动到邻接顶点；
5. 重复直到所有边被遍历。

时间复杂度：$O(m\cdot (n+m))$（需用 DFS 判断桥），较 Hierholzer 慢，但直观易懂。

---

6. Hamilton 路径与 Hamilton 圈

与 Euler 问题的"遍历每条边"不同，Hamilton 问题关注的是"遍历每个顶点恰好一次"。

6.1 历史背景

1859 年，爱尔兰数学家 William Rowan Hamilton发明了一种名为"Icosian 游戏"的智力玩具，基于正十二面体（Dodecahedron）的图结构：

• 正十二面体有 20 个顶点、30 条边、12 个面；
• 游戏的问题是：是否存在一条路径，经过每个顶点恰好一次并回到起点？

这引出了 Hamilton 路径与 Hamilton 圈的概念。

---

6.2 基本定义

定义（Hamiltonian Path / Hamilton 路径）：
经过图中每个顶点恰好一次的 path 称为 Hamiltonian path。

定义（Hamiltonian Cycle / Hamilton 圈）：
经过图中每个顶点恰好一次的 cycle 称为 Hamiltonian cycle。等价地说，是一个 Hamiltonian path 再加上连接其两端点的那条边，从而形成一个 cycle。

定义（Hamiltonian Graph / Hamilton 图）：
含有 Hamiltonian cycle 的图称为 Hamiltonian graph。

定义（Semi-Hamiltonian Graph / 半 Hamilton 图）：
不含有 Hamiltonian cycle，但含有 Hamiltonian path 的图称为 semi-Hamiltonian graph。

对比总结：

	Euler 问题	Hamilton 问题
遍历对象	每条边恰好一次	每个顶点恰好一次
判定复杂度	线性时间 $O(n+m)$	NP-完全
充要条件	有（Euler 定理）	无已知简洁充要条件
充分条件	也必要	有多种（Ore, Dirac 等）
必要条件	也充分	不充分

---

6.3 NP-完全性

定理：
Hamiltonian Path 问题和 Hamiltonian Cycle 问题都是 NP-完全的。

• 这意味着（在 $\text{P}\ne \text{NP}$ 的假设下）不存在多项式时间的判定算法；
• 与 Euler 问题形成鲜明对比——Euler 问题有线性时间算法，可以通过比较检查比较简单的性质就判定。
• “是否存在判定 Hamiltonian cycle 的简洁定理？”——目前没有人知道，很可能永远不会知道（若 $\text{P}\ne \text{NP}$）。

由于 NP-完全性，图论研究 Hamilton 问题时采取以下策略：

1. 充分条件：证明"若图满足某性质，则图是 Hamiltonian 的"；
2. 必要条件：证明"若图是 Hamiltonian 的，则图必满足某性质"；
3. 特殊图类：对某些特殊图类（如完全图、二部图等）给出判定方法。

---

6.4 典型例子介绍

6.4.1 Hamiltonian 图的正例

图类	Hamiltonian 性	说明
完全图 $K_n$ ($n\ge 3$)	是	任意排列顶点即得 Hamiltonian cycle
圈图 $C_n$ ($n\ge 3$)	是	自身就是 Hamiltonian cycle
所有正多面体图	是	Tetrahedron、Cube、Octahedron、Dodecahedron、Icosahedron
完全二部图 $K_{m,n}$	当且仅当 $m=n\ge 2$	见第 8.3 节

6.4.2 非 Hamiltonian 图的经典反例

Petersen 图：

• 10 个顶点、15 条边；
• 3-正则图（每个顶点度均为 3）；
• 围长（girth，最短 cycle 长度）为 5；
• 不是 Hamiltonian 图（有路径没有圈）。
  

证明思路（反证法）：
假设 Petersen 图有 Hamiltonian cycle $C$。考虑顶点 $v_0$，其在 Petersen 图中有 3 个邻接顶点。由于皮特森图中不存在长度小于五的圈（穷举可知），$v_0$ 在 $C$ 上的两个邻接顶点不能相隔太近。通过分析 $v_0$ 的邻接顶点在 $C$ 上的各种配置情况（case analysis），可以导出矛盾——要么产生长度为 4 的 cycle（与围长为 5 矛盾），要么归结为已排除的情形。

---

7. Hamilton 图的充分条件

本节介绍两个最著名的充分条件：Ore 定理和Dirac 定理。

7.1 Ore 定理（1960）

定理（Ore’s Theorem）：
设 $G=(V,E)$ 是 $n\ge 3$ 个顶点的简单图。如果对每一对不相邻的顶点 $u,v\in V$，都有

$$\mathrm{deg}(u)+\mathrm{deg}(v)\ge n$$

则 $G$ 是 Hamiltonian 图。

条件解读：

• 条件只要求对不相邻的顶点对验证；
• 直观含义：“如果图有足够多的边（用度和来衡量），则图是 Hamiltonian 的”；
• 这是一个充分但非必要条件。

证明思路（反证法 + 极值性论证）：

1. 反设：假设 $G$ 满足 Ore 条件但不是 Hamiltonian 图；
2. 加边保持条件：向 $G$ 中添加边不会破坏 Ore 条件（因为加边只会增加度，使不等式更容易满足）；
3. 极值图：不断加边直到得到一个极大非 Hamiltonian 图 $G^{\prime }$（再加任意一条边就变成 Hamiltonian 图）；
4. 半 Hamilton 性：由极大性，$G^{\prime }$ 必含有一条 Hamiltonian path $v_1\to v_2\to \cdots \to v_n$（因为加任意一条边就会产生 Hamiltonian cycle）；
5. 非邻接端点：$v_1$ 与 $v_n$ 不相邻（否则已有 Hamiltonian cycle）；
6. Ore 条件应用：$\mathrm{deg}(v_1)+\mathrm{deg}(v_n)\ge n$；
7. 构造矛盾：考察 $v_1$ 的邻接顶点集 $S$ 与 $v_n$ 的"前驱邻接集" $T$。由鸽巢原理，存在某个 $v_i$ 使得 $v_i$ 邻接于 $v_1$ 且 $v_{i-1}$ 邻接于 $v_n$。于是可以构造 Hamiltonian cycle：$v_1\to v_i\to v_{i+1}\to \cdots \to v_n\to v_{i-1}\to v_{i-2}\to \cdots \to v_1$，矛盾。
   

---

7.2 Dirac 定理

定理（Dirac’s Theorem，1952）：
设 $G=(V,E)$ 是 $n\ge 3$ 个顶点的简单图。如果

$$\delta (G)\ge \frac{n}{2}$$

（即每个顶点的度至少为 $n/2$），则 $G$ 是 Hamiltonian 图。

与 Ore 定理的关系：

• Dirac 定理是 Ore 定理的直接推论；
• 若 $\delta (G)\ge n/2$，则对任意不相邻顶点 $u,v$：$\mathrm{deg}(u)+\mathrm{deg}(v)\ge n/2+n/2=n$，满足 Ore 条件；
• Dirac 条件更强（要求更严格），因此适用范围更窄，但验证更简单。

紧性说明：

• Dirac 定理中的 $n/2$ 是最优的（不能降低）；
• 反例：取 $K_{\lfloor (n+1)/2\rfloor }$ 和 $K_{\lceil (n+1)/2\rceil }$ 共享一个顶点。此图的 $\delta (G)=\lfloor (n-1)/2\rfloor$，但不是 Hamiltonian 图。

---

7.3 闭包与 Bondy-Chvátal 定理（拓展）

定义（闭包）：
图 $G$ 的闭包 $C(G)$ 是通过反复执行以下操作得到的图：若存在不相邻顶点 $u,v$ 满足 $\mathrm{deg}(u)+\mathrm{deg}(v)\ge n$，则添加边 {u,v}\{u, v\}{u,v}，直到不存在这样的顶点对为止。

定理（Bondy-Chvátal，1972）：
图 $G$ 是 Hamiltonian 图当且仅当其闭包 $C(G)$ 是 Hamiltonian 图。

意义：

• 这是 Ore 定理的推广；
• 提供了一种系统性地"加边"来判定 Hamiltonian 性的方法；
• 若闭包最终变成完全图 $K_n$，则原图必为 Hamiltonian 图。

---

8. Hamilton 图的必要条件

本节介绍若干 Hamilton 图的必要条件。需注意：这些条件都不充分。

8.1 连通度条件

定理（Chvátal-Erdős 型必要条件）：
若 $G=(V,E)$ 是 Hamiltonian 图，则对任意非空真子集 $S\subset V$，有

$$c(G-S)\le |S|$$

其中 $G-S$ 表示从 $G$ 中删除 $S$ 中的所有顶点及其关联边后得到的图，$c(G-S)$ 表示 $G-S$ 的连通分支数。

直观理解：
想象 Hamiltonian cycle $C$ 是一条穿过所有顶点的"环状项链"。当删除集合 $S$ 中的顶点后，项链在每个被删除的顶点处断裂。断裂后的每一段（连通分支）必须"挂在" $S$ 的不同顶点上——因此连通分支数不可能超过 $|S|$。

证明思路：
Hamiltonian cycle 删除 $S$ 后最多变成 $|S|$ 条 path（每个被删顶点最多"切断" cycle 一次），故 $c(G-S)\le c(C-S)\le |S|$。

注意：该条件是必要但不充分的。例如 Petersen 图满足此条件但不是 Hamiltonian 图。

---

8.2 Whitney 定理与 Hamilton 图的关系

在第 3.6 节我们已经介绍了 Whitney 定理 $\kappa (G)\le \lambda (G)\le \delta (G)$。这里讨论它与 Hamilton 图的关系。

推论：
Hamilton 图必是 2-连通图（$\kappa (G)\ge 2$）。

证明：
Hamiltonian cycle 本身就是一个 2-连通结构：删除任意一个顶点后，cycle 变成一条 path，图仍然连通。因此非 2-连通的图一定不是 Hamiltonian 图。

注意：2-连通是不充分的——Petersen 图是 3-连通的（$\kappa =3$），但仍非 Hamiltonian。

---

8.3 度为 2 的顶点约束

必要条件：
若 $G$ 是 Hamiltonian 图，则所有与度为 2 的顶点关联的边必须都在 Hamiltonian cycle 上。

解读：

• 度为 2 的顶点只有两条关联边；
• Hamiltonian cycle 经过该顶点时恰好使用两条边；
• 因此这两条边"别无选择"，必须全部使用。

---

8.4 二部图的特殊必要条件

定理：
完全二部图 $K_{m,n}$ 是 Hamiltonian 图 当且仅当 $m=n\ge 2$。

证明：

• 充分性（$m=n\ge 2$）：在 $V_1$ 和 $V_2$ 之间交替访问即可构造 Hamiltonian cycle。
• 必要性：设 $K_{m,n}$ 有 Hamiltonian cycle。在 cycle 上，顶点必须在 $V_1$ 和 $V_2$ 之间严格交替（因为是二部图，无内部边），所以 $|V_1|=|V_2|$。又 $K_{1,1}$ 只有一条边，不构成 cycle，故需 $m=n\ge 2$。

推论（非 Hamiltonian 二部图例子）：
$K_{12,13}$（$|V_1|=12,|V_2|=13$）不是 Hamiltonian 图。

---

8.5 Petersen 图非 Hamilton 性再述

Petersen 图满足上述所有必要条件（连通度条件 $c(G-S)\le |S|$、度约束、2-连通等），但仍不是 Hamiltonian 图——这说明必要条件真的只是"必要"而非"充分"。

关键性质：

• 10 个顶点，15 条边，3-正则；
• 围长为 5（无 3-cycle 或 4-cycle）；
• 自同构群高度对称；
• 是亚哈密顿图（hypohamiltonian：本身非 Hamiltonian，但删除任意一个顶点后变成 Hamiltonian）。

---

9. 应用与拓展

9.1 马踏棋盘问题（Knight’s Tour）

问题描述：
在国际象棋棋盘上，骑士（也即马）按照"日"字形移动（横向走 2 格纵向走 1 格，或横向走 1 格纵向走 2 格）。问：

骑士能否恰好访问棋盘的每个方格一次，并最终回到出发点？

图论建模：

• 将棋盘的每个方格看作一个顶点；
• 若骑士可以一步从一个方格移动到另一个方格，则在对应顶点间连一条边；
• 问题转化为：在这个"骑士图"中寻找 Hamiltonian cycle。

二部图分析：
棋盘天然构成二部图——将棋盘按黑白染色，骑士每步必从黑格跳到白格（或反之）。因此骑士图是二部图。

定理：

• $5\times 5$ 棋盘：$|U|=12,|V|=13$（黑白格数不等），骑士图同构于 $K_{12,13}$ 的子图，故不存在 Hamiltonian cycle；
• $4\times 4$ 棋盘：删除中间的 4 个方格后，剩余图有 6 个连通分支。由必要条件 $c(G-S)\le |S|$（取 $|S|=4$），$6>4$，故不存在 Hamiltonian cycle；
• $4\times n$ 棋盘（$n\ge 4$）：类似分析，删除中间两行的棕色方格后产生 $\ge n+1$ 个连通分支，而 $|S|=n$，故不存在 Hamiltonian cycle。

---

9.2 旅行商问题（Travelling Salesman Problem, TSP）

问题描述：
给定一组城市和每对城市之间的距离，求一条最短的路线，使得：

• 从某城市出发；
• 恰好访问每个城市一次；
• 最终回到出发城市。

图论建模：

• 将城市看作顶点；
• 将城市间的道路看作边，距离作为边的权重；
• 问题转化为：在带权完全图中寻找权重最小的 Hamiltonian cycle。

与 Hamilton 问题的关系：

• TSP 是 Hamiltonian cycle 问题的加权优化版本；
• 决策版本（“是否存在长度 $\le L$ 的 tour？”）是 NP-完全的；
• 是组合优化中最著名、研究最深入的 NP-难问题之一；
• 实际应用中常用近似算法、启发式算法（如模拟退火、遗传算法、蚁群算法等）求解。

---

9.3 中国邮路问题（Chinese Postman Problem）

问题描述：
邮递员从邮局出发，要经过每条街道至少一次，最后回到邮局。求最短的投递路线。

与 Euler 问题的关系：

• 若街道图是 Eulerian 图，则 Euler tour 即最优解（每条街恰好走一次）；
• 若不是 Eulerian 图，则需要重复走某些街道（相当于在图中添加重复的边使其 Eulerian），使得重复的边总长度最小。

解决方法：

• 找出图中所有奇度顶点（必为偶数个）；
• 将这些奇度顶点两两配对；
• 在每对之间找最短路径，沿该路径复制边；
• 使所有顶点度变为偶数，然后找 Euler tour。
• 最优配对可用blossom 算法在多项式时间内求解。

---

9.4 邻接矩阵幂与路径计数的再讨论

在第 2.3 节我们已经介绍了邻接矩阵的幂与路径计数的基本定理。这里从路径与圈的角度进一步讨论其意义。

回顾定理：
设 $A$ 是图 $G$ 的邻接矩阵，则 $(A^k{)}_{ij}$ 等于从 $v_i$ 到 $v_j$ 的长度为 $k$ 的通路（walk）数目。

应用：

• 判断连通性：若 $P=I\vee A\vee A^2\vee \cdots \vee A^{n-1}$ 是全 1 矩阵，则图是连通的；
• 计数路径：无需枚举，直接用矩阵乘法即可统计固定长度的通路数目；
• 判断 cycle 存在性：$\text{tr}(A^k)={\sum }_{i=1}^n(A^k{)}_{ii}$ 表示图中长度为 $k$ 的闭 walk 数目（含重复计数）。

---

10. 总结

10.1 核心概念层级图

图论基础概念层级

图 G = (V, E)
├── 有向图 / 无向图
├── 简单图 / 多重图（平行边、环）
├── 度：d(v), δ(G), Δ(G)
├── 握手定理：Σd(v) = 2|E|
├── 特殊图类：K_n, C_n, W_n, K_{m,n}, 正则图, 竞赛图
├── 运算：删除点/边、加边、收缩
├── 子图、生成子图、导出子图、补图
├── 同构 ≅
├── 矩阵表示：A(邻接), M(关联), P(可达)
└── 连通性
    ├── 无向图：连通 / 不连通（连通分支）
    ├── 有向图：强连通 → 单向连通 → 弱连通
    ├── 距离 d(u,v) 与短程线
    ├── 极大路径法
    └── 连通度：κ(G) ≤ λ(G) ≤ δ(G)  (Whitney)

路径与圈概念层级

                    Walk (道路)
                   /    |    \
                  /     |     \
            (边互异)   (闭)   (顶点互异)
                /       |       \
           Trail    Closed    Path
          (迹)      Walk     (路径)
              \       |       /
               \      |      /
                \     |     /
              Closed Trail
                     |
                     |  (顶点互异)
                     |
                  Cycle (圈)

包含关系：

$$\text{Cycle}⊊\text{Closed Path}⊊\text{Closed Trail}⊊\text{Closed Walk}$$
$$\text{Path}⊊\text{Trail}⊊\text{Walk}$$

---

10.2 Euler 问题 vs Hamilton 问题

对比维度	Euler Trail / Tour	Hamilton Path / Cycle
遍历目标	每条边恰好一次	每个顶点恰好一次
判定难度	线性时间 $O(n+m)$	NP-完全
充要条件	有（奇度顶点数为 0 或 2）	无已知简洁条件
充分条件	也是必要条件	Ore、Dirac 等
必要条件	也是充分条件	连通度条件等（不充分）
算法	Hierholzer $O(m)$、Fleury	无多项式算法（一般情形）
应用	中国邮路问题	TSP、骑士巡游
典型正例	所有偶度连通图	完全图 $K_n(n\ge 3)$
典型反例	柯尼斯堡七桥图	Petersen 图

---

10.3 充分条件对比（Hamilton 图）

定理	年份	条件	强度
Dirac	1952	$\delta (G)\ge n/2$	强（易验证）
Ore	1960	$\forall$ 非邻接 $u,v$: $\mathrm{deg}(u)+\mathrm{deg}(v)\ge n$	中等
Bondy-Chvátal	1972	闭包 $C(G)$ 是完全图	最弱（最精确）

关系：$\text{Dirac}\Rightarrow \text{Ore}\Rightarrow \text{Bondy-Chvaˊtal（逆不成立）}$

---

10.4 注意事项

1. Walk $\ne$ Trail $\ne$ Path：这三者的区分是图论容易混淆的地方。核心区别在于：walk 无任何限制；trail 要求边不重复；path 要求顶点不重复。许多定理只对 path 成立，不能随意推广到 walk 或 trail。

2. 简单回路 $\ne$ 圈：简单回路只要求边不重复，允许顶点重复；圈要求除起点=终点外所有顶点互不相同。"8"字形的回路是简单回路但不是圈。

3. Euler 与 Hamilton 的本质区别：前者遍历边，后者遍历顶点。一个是"线性可解"，一个是"NP-完全"。不要混淆二者的条件和结论。

4. 闭 path 与 cycle 的区别：闭 path 只要求 $v_0=v_m$，中间顶点可能重复；cycle 要求 $v_0,v_1,\dots ,v_{m-1}$ 全不相同。因此闭 path $⊋$ cycle。

5. "至少有一条边"的约束：cycle 定义中要求至少一条边，这排除了单个顶点（长度为 0 的"自环"情况）。$C_3$（三角形）是最小的 cycle。

6. Ore 条件的验证范围：Ore 定理只要求对不相邻的顶点对验证度和条件。若两个顶点已经相邻，则无需检验。

7. Hamilton 必要条件的局限：连通度条件 $c(G-S)\le |S|$、度为 2 顶点约束等都是"必要不充分"的。Petersen 图满足所有常见必要条件但仍非 Hamiltonian。

8. 二部图 Hamiltonian 性的特殊处理：二部图的 Hamiltonian cycle 必须在两个部分集之间严格交替，因此 $|U|=|V|$ 是必要条件。对于完全二部图 $K_{m,n}$，这个条件也是充分的（当 $m=n\ge 2$ 时）。

9. 握手定理的适用范围：握手定理适用于所有图（包括有环、有平行边的图），只需注意环对度的贡献为 2。

10. TONCAS 原则：Euler 定理是图论中 TONCAS（“The Obvious Necessary Conditions are Also Sufficient”）原则的经典体现。Hamilton 问题则是反例——必要条件并不充分。

---