Lecture 9: Graphs（图论基础）

目录 · ← l9 · l11 →

Lecture 9: Graphs（图论基础）

概述

本讲引入整门课最重要的一种离散建模语言：图 (graph)。互联网的页面链接、大脑的神经元连接、城市的道路网、社交网络里”谁认识谁”——这些表面上毫不相干的系统，抽掉细节之后都是同一批数学对象：一组顶点加一组边。本讲分两步走。第一步给出图的正式定义（无向图、有向图、简单图、多重图）以及一整套基础术语（邻接、度、路径、环、连通性、连通分量、距离、二分图、完全图、补图），并用握手引理 $\sum_{v\in V}\deg(v)=2\vert E\vert $ 展示”双计数 (double counting)”这一证明技巧的威力。第二步回到图论的历史起点——柯尼斯堡七桥问题，给出并完整证明欧拉定理：一个连通无向图存在欧拉回路，当且仅当每个顶点的度都是偶数。这个定理是”充要条件”证明的典范：必要性用”进出配对”的巧思，充分性用构造性算法加归纳法，两种风格截然不同的论证在同一个命题上汇合。

核心概念的直观解释

无向图（undirected graph）

• 定义：一个无向图是序对 $G=(V,E)$，其中 $V$ 是顶点集 (vertex set)，$E$ 是边集 (edge set)。$E$ 中每个元素都是 $V$ 的一个二元子集 $\{u,v\}$（$u\neq v$），表示 $u$ 与 $v$ 之间有一条边。
• 直观解释（”它是什么意思？”）：顶点是”东西”，边是”关系”。关系的本质特征是对称：如果”你在我的通讯录里”和”我在你的通讯录里”是同一件事，那就该用无向图。现实类比：双向街道、握手、婚姻关系、”两人互相认识”。
• 具体示例：住户路网图 $G_3=(\{1,2,3,4\},\{\{1,2\},\{2,3\},\{1,4\},\{4,3\}\})$：顶点是房子，边是直接相连的道路。

图论最初的抽象：从柯尼斯堡到 $K_4$ 形状

• 定义：1736 年欧拉 (Leonhard Euler) 处理柯尼斯堡 (Königsberg，今俄罗斯加里宁格勒) 七桥问题时，做的正是”抽象”这一步：把每块陆地（两岸 $A,D$、两岛 $B,C$）换成一个小圆圈，把每座桥换成一条线段，于是问题从”城市地图”变成”能否一笔画完所有线段并回到起点”。
• 直观解释（”它是什么意思？”）：这是计算机科学中抽象 (abstraction) 这一核心思想的最早范例——丢掉长度、位置、形状，只保留”谁和谁相连”。抽掉之后剩下的正是图。
• 具体示例：柯尼斯堡的抽象图有顶点集 $V=\{A,B,C,D\}$，边集（多重集）为 $\{\{A,B\},\{A,B\},\{A,C\},\{B,C\},\{B,D\},\{B,D\},\{C,D\}\}$，共 7 条边。

有向图（directed graph）

• 定义：有向图 $G=(V,E)$ 中，边集 $E\subseteq V\times V$ 是有序对的集合（笛卡尔积 $U\times V=\{(u,v):u\in U,\ v\in V\}$）。边 $(u,v)$ 带箭头，从 $u$ 指向 $v$。
• 直观解释（”它是什么意思？”）：有向边是单向街道：$u\to v$ 存在并不意味着 $v\to u$ 存在。现实类比：”Alex 认识 Bridget 但 Bridget 不认识 Alex”（单向的”认识”）、网页 A 链接到网页 B、任务 A 必须在任务 B 之前完成。
• 具体示例：$V=\{1,2,3,4\}$、$E=\{(1,2),(1,3),(1,4)\}$ 是一个有向图：$(1,2)\in E$ 但 $(2,1)\notin E$。
• 与无向图的关系：若无向图的边 $\{u,v\}$ 理解为”两个方向都有”，则无向图恰是满足”$(u,v)\in E \iff (v,u)\in E$”的有向图；书写时对无向图去掉箭头，并把有序对写成集合 $\{u,v\}$。

相邻、邻居、度（adjacency, neighborhood, degree）

• 定义：若 $\{u,v\}\in E$，则称 $u$ 与 $v$ 相邻 (adjacent)，互为邻居 (neighbor)，也说边 $e=\{u,v\}$ 关联 (incident) 于 $u$ 和 $v$。顶点 $u$ 的度 (degree) 定义为 \(\deg(u) = \big\vert \{v\in V : \{u,v\}\in E\}\big\vert ,\) 即与 $u$ 相连的边的条数（在简单图中也就是邻居的个数）。度为 $0$ 的顶点叫孤立顶点 (isolated vertex)。
• 直观解释（”它是什么意思？”）：度就是”一个人认识多少个人”。孤立顶点是”谁都不认识的隐士”。在通信网络里，度就是”这台路由器有几根线”。
• 具体示例：路网图 $G_3$ 中 $\deg(1)=2$（连到 2 和 4），$\deg(2)=2$，$\deg(3)=2$，$\deg(4)=2$。若再加一个不与任何人相连的房子 5，则 $\deg(5)=0$，5 是孤立顶点，且 $G_3$ 变成不连通。
• 有向图的两种度：入度 (in-degree) 是”从别人指向 $u$ 的边数”，出度 (out-degree) 是”从 $u$ 指向别人的边数”。在”$u$ 认识 $v$”的社会网络里，入度 = 有多少人认识你（知名度），出度 = 你认识多少人（交际广度）。

自环（self-loop）、简单图（simple graph）、多重图（multigraph）

• 定义：边 $\{u,u\}$（或 $(u,u)$）叫自环。”一对顶点之间最多一条边”且”没有自环”的图叫简单图。允许一对顶点之间有多条边（重边 / 平行边, parallel edges）的图叫多重图 (multigraph)。
• 直观解释（”它是什么意思？”）：自环是”自己认识自己”，在大多数建模场景中没有信息量。重边是”两地之间有不止一条路/桥”——柯尼斯堡恰好是这种情况（$A$ 与 $B$ 之间有两座桥，$B$ 与 $D$ 之间也有两座）。
• 具体示例：本课程（以及 Berkeley 官方 Note）默认不考虑自环，也默认两条顶点之间至多一条边；遇到真有多重边的情形（如七桥问题），就把重边塌缩 (collapse) 成一条边。这个约定非常重要：它让”$\deg(u)=\vert \{v:\{u,v\}\in E\}\vert $”这个定义在简单图中自洽（既等于邻居数，也等于关联边数）。

路径、游走、环、回路（path, walk, cycle, tour）

• 定义：设 $G=(V,E)$ 无向。一条游走 (walk) 是顶点序列 $v_1,v_2,\dots,v_k$ 使得每对相邻的 $v_i,v_{i+1}$ 之间有边（顶点可以重复）。若 $v_1,\dots,v_k$ 互不相同，则称为路径 (path)（很多教材也写作 “simple path”，与允许重复的 walk 相对）。一条环 (cycle / circuit) 是 $v_1,\dots,v_n$ 互不相同且 $\{v_n,v_1\}\in E$ 的序列。起点与终点相同的游走叫巡游 (tour)。
• 直观解释（”它是什么意思？”）：walk 是”随便溜达”（可以来回踱步），path 是”不重复经过同一栋房子的行进路线”，cycle 是”绕一圈回到出发点且中途不重复”。
• 具体示例：在路网 $G_3$ 中，$1\to 2\to 1\to 4\to 3$ 是 walk（顶点 1 出现了两次）；$1\to 2\to 3$ 是 path；$1\to 2\to 3\to 4\to 1$ 是 cycle（长度 4）。注意 $1\to 4\to 3\to 2\to 1$ 是同一个环的另一种走法。

连通性与连通分量（connectivity, connected component）

• 定义：无向图 $G$ 称为连通的 (connected)，如果任意两个不同顶点之间都存在一条 path。不是连通的图称为不连通的。任何图都能唯一分解为若干连通分量 (connected component)：把顶点集划分成若干块 $V_1,\dots,V_k$，每块内部的顶点互相连通，块与块之间没有边。
• 直观解释（”它是什么意思？”）：连通 = “从任何一个房子都能开车到任何别的房子”。连通分量 = “一个个互相隔绝的孤岛”。在设计路网时你绝不希望出现孤立顶点或隔绝的小区，因为那样有的人永远到不了别处。
• 具体示例：$G_3$ 是连通的（从 1 可以到 2、3、4）。若在原图上加顶点 5 且不与任何顶点相连，则图不连通，连通分量是 $V_1=\{1,2,3,4\}$ 与 $V_2=\{5\}$。官方 Note 给出的例子则分成三块：$V_1=\{1,2,3\}$、$V_2=\{4\}$、$V_3=\{5,6,7\}$。

距离（distance）

• 定义：两顶点 $u,v$ 之间的距离 (distance) 是从 $u$ 到 $v$ 的最短 path 的边数。若不连通，则距离定义为 $\infty$。
• 直观解释（”它是什么意思？”）：距离就是”最少走几条路”。在互联网中它对应”最少经过几跳 (hop)”，这正是路由协议最关心的量。
• 具体示例：在 $G_3=\{1\!-\!2,2\!-\!3,1\!-\!4,4\!-\!3\}$ 中，从 1 出发的距离分别是 $d(1,1)=0$、$d(1,2)=1$、$d(1,4)=1$、$d(1,3)=2$（$1\to 4\to 3$ 或 $1\to 2\to 3$，都是 2 条边）。

二分图（bipartite graph）

• 定义：图 $G=(V,E)$ 是二分图，若顶点集可以划分为两个部分 $V=L\cup R$（$L\cap R=\varnothing$），且每条边都从 $L$ 跨到 $R$，即 $E\subseteq L\times R$（等价地，$L$ 内部与 $R$ 内部都没有边）。
• 直观解释（”它是什么意思？”）：二分图是”两个阵营”的结构：同一阵营的人互不相识，只跟对面阵营有往来。现实类比：求职者与岗位、学生与课程、男与女（在纯异性社交模型中）、以及电路中的”开关”与”被控制的线”。
• 具体示例：$K_{3,3}$（张三户人家与三口井，每家都要连到每口井，但人家之间、井之间不连边）是二分图：$L=\{$三户人家$\}$，$R=\{$三口井$\}$，$\vert E\vert =9$。另一个例子是偶数长度的环 $C_6$，而奇数长度的环 $C_5$（五边形）不是二分图（脚本用贪心二染色验证：$C_6$ 可二染色，$C_5$ 不可）。
• 一个重要等价刻画（L10 会正式证明）：一个图是二分图，当且仅当它不含奇数长度的环。直观理由：沿着环交替染色，若要回到起点时颜色一致，环长必须是偶数。

完全图（complete graph）

• 定义：无向完全图 $K_n=(V,E)$ 满足 $\vert V\vert =n$ 且 $E=\{\{v_i,v_j\} : v_i\neq v_j,\ v_i,v_j\in V\}$——任意两个不同顶点之间都恰好有一条边。有向完全图则要求对每对 $u\neq v$ 同时有 $(u,v)\in E$ 与 $(v,u)\in E$。
• 直观解释（”它是什么意思？”）：完全图是”关系最密集”的图：没有任何两个人是陌生人。它是”最大连通性”的极端，但代价是边数爆炸。
• 具体示例：$K_2$ 有 1 条边、$K_3$ 有 3 条边（三角形）、$K_4$ 有 6 条边、$K_5$ 有 10 条边。一般地 $\vert E(K_n)\vert =\binom{n}{2}=\frac{n(n-1)}{2}$（证明见定理 9.2）。每个顶点的度都是 $n-1$。$K_5$ 有 5 个顶点 10 条边——这个数字在 L10 证明”$K_5$ 不可平面”时会再次出现。

补图（complement）

• 定义：简单图 $G=(V,E)$ 的补图 $\overline{G}=(V,\overline{E})$ 与原图共享顶点集，边集为 $\overline{E} = \{\{u,v\}: u\neq v,\ \{u,v\}\notin E\}$，即”原本不相邻的点对在新图中相邻”。
• 直观解释（”它是什么意思？”）：补图把”陌生人网络”变成”熟人网络”，反之亦然。它在”顶点覆盖 / 独立集 / 团”这组概念之间搭起一对一的翻译（$G$ 中的独立集恰好是 $\overline{G}$ 中的团）。
• 具体示例：$K_4$ 的补图没有边（$\overline{K_4}$ 是 4 个孤立顶点）。路 $P_4=\{1\!-\!2,2\!-\!3,3\!-\!4\}$ 的补图边集为 $\{\{1,3\},\{1,4\},\{2,4\}\}$，度数分别是 $2,1,1,2$（脚本验证）。$C_5$ 的补图仍是 $C_5$（自补）。

树（tree，预告）

• 定义：一个图是树 (tree)，若它连通且无环 (connected and acyclic)。官方 Note 还给出了三个等价刻画：连通且有 $n-1$ 条边（$n=\vert V\vert $）；连通但删去任意一条边就变得不连通；无环但添加任意一条新边就会产生环。根树 (rooted tree) 还指定一个特别的顶点叫根 (root)，最底层没有子节点的顶点叫叶 (leaf)，中间的叫内部节点 (internal node)，从根到叶的最长路径长度叫树的深度 (depth)。树的第 $k$ 层 (level) 是与根相距恰好 $k$ 条边的顶点集合。
• 直观解释（”它是什么意思？”）：树是”刚好够用“的连通图——不连通的图不能用，而比树多一条边就一定有多余的环（冗余）。现实类比：公司组织架构图、家谱、细菌分裂的世代图（根是一个细菌，每一层是一次分裂）、二叉搜索树。在通信网络设计中，树是”用最少线路把所有城市连起来”的方案（最小生成树）。
• 具体示例：$V=\{1,2,3\}$、$E=\{\{1,2\},\{2,3\},\{1,3\}\}$（三角形）不是树（有环）；去掉任意一条边，例如得 $E=\{\{1,2\},\{2,3\}\}$，这就是一棵树：连通、无环、有 $3-1=2$ 条边。官方 Note 中的 15 节点完全二叉树深度为 3，根在第 0 层，第 3 层是全部 8 个叶节点。L10 会给出树的等价刻画的完整证明（对顶点数用强归纳，并需要处理”删掉一个顶点后图分裂成多个连通分量”的情形——这正是强归纳而非弱归纳的原因）。

同构（isomorphism，一句话说明）

• 定义：两个图 $G=(V,E)$ 与 $G^{\prime}=(V^{\prime},E^{\prime})$ 同构，若存在一个双射 $f:V\to V^{\prime}$，使得 $\{u,v\}\in E \iff \{f(u),f(v)\}\in E^{\prime}$。同构的图”结构完全相同”，只是顶点被重新命名、画法不同而已。
• 直观解释（”它是什么意思？”）：同构是”换名字不换结构”。官方 Note 说”前两个图画法不同但其实是同一个图”，说的正是同构。注意：平面上画图时线条的交叉只是画法，不代表结构差异。
• 具体示例：$1\!-\!2\!-\!3$ 与 $a\!-\!b\!-\!c$ 同构（$f(1)=a,f(2)=b,f(3)=c$）。而 $1\!-\!2\!-\!3$（3 个顶点的路）与三角形 $1\!-\!2,2\!-\!3,3\!-\!1$ 不通过同构——前者边数 2、后者边数 3，边的数量是同构不变量。

完整证明与推导（核心）

定理 9.1（握手引理 Handshake Lemma）：对任意无向图 $G=(V,E)$（允许自环与重边时需按惯例计度，简单图情形结论相同）， \(\sum_{v\in V}\deg(v) = 2\,\vert E\vert .\)

证明策略：双计数 (double counting)——用两种不同的方式数同一个量，从而得到等式。这里的”同一个量”是关联关系的个数，即”顶点—边”的关联对 $(v,e)$（其中 $e$ 关联于 $v$）的总数。为什么选这个策略？因为左边”按顶点分组数”、右边”按边分组数”，两种分组方式数的是同一批对象，等式自动成立。

逐步推导：

1. 定义关联对集合 $S = \{(v,e) : v\in V,\ e\in E,\ v \text{ 是 } e \text{ 的一个端点}\}$。依据：定义（构造一个用于双计数的对象）。
2. 按顶点数：对每个固定的 $v\in V$，与 $v$ 关联的边恰好有 $\deg(v)$ 条，所以 $v$ 贡献 $\deg(v)$ 个关联对。对所有 $v$ 求和得 \(\vert S\vert = \sum_{v\in V}\deg(v).\) 依据：度的定义（度为关联于该顶点的边的条数）。
3. 按边数：对每条固定的边 $e=\{u,v\}$（$u\neq v$，简单图情形），它恰好有两个端点，所以 $e$ 贡献 2 个关联对——$(u,e)$ 与 $(v,e)$。对所有边求和得 \(\vert S\vert = \sum_{e\in E} 2 = 2\,\vert E\vert .\) 依据：边的定义（每条边恰有 2 个端点）。
4. 第 2 步与第 3 步数的是同一个集合 $S$，故两边相等：$\sum_{v\in V}\deg(v) = 2\vert E\vert $。依据：第 2、3 步 + 等式的传递性。

【证明机制解说】：双计数的全部力量来自一个朴素想法——同一个东西数两遍不会数出两个不同的答案。这里的”巧思”是选对了计数对象：不是直接数度数，而是把”顶点与边的关联”作为砖块。每一块砖在”按顶点分组”时被算一次，在”按边分组”时被算一次，2 与 $\deg(v)$ 就是这样自然浮现的。若试图用归纳法逐个加边，也能证明，但会繁琐得多——这正是”选对策略”的价值。

反例（外观上的”违反者”）与自环的说明：若图中有自环 $e=\{u,u\}$，它在”按边数”时仍被算作 2 个关联对（约定自环对一个顶点的度贡献 2）。例如 $V=\{1\}$，$E=\{\{1,1\}\}$：$\deg(1)=2$，$\sum\deg=2=2\cdot 1=2\vert E\vert $ ✓。若错误地把自环只算 1 度，引理就会被”违反”——这提醒我们：引理的正确性依赖于度的定义与计数约定的一致。本课程默认无自环，所以不会有这个麻烦。

推论 9.1.1（奇度顶点个数为偶数）：任意无向图中，度数为奇数的顶点个数是偶数。

证明策略：直接证明 + 模 2 分析（奇偶性论证）。

逐步推导：

1. 由定理 9.1，$\sum_{v\in V}\deg(v)=2\vert E\vert $，右边是偶数。依据：握手引理。
2. 把 $V$ 分成 $V_{\text{odd}}$（奇度顶点）与 $V_{\text{even}}$（偶度顶点）。依据：分类。
3. $\sum_{v\in V}\deg(v) = \sum_{v\in V_{\text{odd}}}\deg(v) + \sum_{v\in V_{\text{even}}}\deg(v)$，其中第二个和是偶数（偶数之和为偶数）。依据：奇偶性。
4. 由第 1、3 步，$\sum_{v\in V_{\text{odd}}}\deg(v)$ 必为偶数（偶数减去偶数为偶数）。依据：整数奇偶性。
5. 一个整数之和为偶数，当且仅当其中的奇数项个数为偶数（每一对奇数相加为偶数）。故 $\vert V_{\text{odd}}\vert $ 是偶数。依据：第 4 步 + 奇偶性论证。

【证明机制解说】：这个推论是”奇偶性是全局约束“的漂亮示范：单个顶点的度可以随便是奇是偶，但全图的奇度顶点个数被锁成偶数。”存在性”式的应用极为有用：要证明某个度序列不可能实现，只要看奇度顶点个数是否为奇。

反例（推论的应用）：5 个人的握手次数能否恰好是 $0,1,2,3,4$？不能。理由有两个层次：

• 直接理由：$0+1+2+3+4=10$ 是偶数，奇偶性检查通过了——所以这一条单独不够，必须再挖一层。
• 真正的理由：设握手次数为 0 的人是 $A$，握手次数为 4 的人是 $B$。$B$ 与其余 4 人全都握过手，特别是 $B$ 与 $A$ 握过手，于是 $\deg(A)\ge 1$，与 $\deg(A)=0$ 矛盾。（脚本穷举了 5 个顶点、10 条可能边的全部 $2^{10}=1024$ 种图，度序列为 $(0,1,2,3,4)$ 的图一个都没有。）这个反例同时提醒我们：奇偶性只是必要条件，不是充分条件——判定度序列是否可实现需要更强的工具（如 Erdős–Gallai 定理）。

定理 9.2（完全图的边数）：$\vert E(K_n)\vert = \dfrac{n(n-1)}{2}$，且 $K_n$ 中每个顶点的度为 $n-1$。

证明策略：双计数（两条路径都可以，此处用边的双计数）+ 与握手引理交叉验证。

逐步推导：

1. 在 $K_n$ 中，每个顶点 $v$ 与其他 $n-1$ 个顶点都相邻，故 $\deg(v)=n-1$。依据：完全图的定义。
2. 由握手引理，$\sum_{v}\deg(v)=2\vert E\vert $。依据：定理 9.1。
3. 左边 $=\sum_{v\in V}(n-1)=n(n-1)$。依据：第 1 步 + 有 $n$ 个顶点。
4. 因此 $2\vert E\vert =n(n-1)$，即 $\vert E\vert =\frac{n(n-1)}{2}=\binom{n}{2}$。依据：第 2、3 步。
5. 验证：$n=2,3,4,5,10$ 时分别得 $1,3,6,10,45$（脚本验算通过），与前面手数 $K_3$、$K_4$、$K_5$ 的结果一致。依据：代入。

【证明机制解说】：这里用握手引理”反解”边数是图论中极常用的套路：当每个顶点的度都容易知道时，边数可以由度和除以 2 得到。（L10 证明超立方体有 $n2^{n-1}$ 条边时用的正是同一招：$2^n$ 个顶点、每个度 $n$，故 $\vert E\vert =n2^n/2=n2^{n-1}$。）换个角度看，$\binom{n}{2}$ 也可以用”从 $n$ 个顶点中选 2 个组成一条边”的组合计数直接得到——两条路径的一致性本身就是定理 9.1 的一个侧面。

定理 9.3（欧拉定理 Euler’s Theorem, 1736）：一个无向图 $G=(V,E)$ 存在欧拉回路 (Eulerian tour)——即经过每条边恰好一次并回到出发点的闭游走——当且仅当 $G$ 是偶度图 (even degree graph)（每个顶点的度都是偶数）且连通（允许孤立顶点例外）。

证明策略：这是一个”当且仅当”命题，两个方向必须用完全不同的策略：

• 必要性（$\Rightarrow$）用直接证明 + 配对论证：$G$ 有欧拉回路 $\Rightarrow$ 偶度 $+$ 连通。理由：回路这一”行走过程”本身就是一本证据簿，只要把每个顶点处被走过的边两两配对即可。
• 充分性（$\Leftarrow$）用构造性算法 + 归纳法：偶度 $+$ 连通 $\Rightarrow$ 有欧拉回路。理由：光说”存在”不够有说服力，我们要给出一个能真正跑出来的算法（Hierholzer 思路的 $\text{FIND TOUR}$ + $\text{SPLICE}$），再对边数做归纳证明它的正确性。

逐步推导（必要性，第一部分：连通性）：

1. 设 $G$ 有欧拉回路 $T$，即 $T$ 是一条经过 $E$ 中每条边恰好一次的闭游走。依据：假设。
2. 每个非孤立顶点 $v$（即 $\deg(v)\ge 1$）至少关联一条边，而这条边必在 $E$ 中，故必被 $T$ 走过，所以 $v$ 出现在 $T$ 的顶点序列中。依据：欧拉回路经过所有边。
3. 于是任意两个非孤立顶点 $u,v$ 都出现在同一条游走 $T$ 上，沿着 $T$ 从 $u$ 走到 $v$ 的那一段就是一条连接它们的 path（去掉可能的绕行后即是）。故 $G$ 在非孤立顶点之间连通。依据：第 2 步 + 连通性定义。
4. 孤立顶点（$\deg=0$）不关联任何边，自然不与任何顶点连通，故”允许孤立顶点例外”这一措辞是必需的。依据：孤立顶点定义。

逐步推导（必要性，第二部分：偶度）：

1. 固定任意顶点 $v$。$T$ 作为闭游走，每一次经过 $v$ 都是”进来一条边、出去一条边”（包括起点的首次离开与终点的最后一次进入，它们配对）：把游走按时间顺序写出来，每当 $T$ 沿一条边进入 $v$，紧接着就必须沿另一条边离开 $v$。依据：游走的定义（相邻顶点间有边）+ 闭游走性质。
2. 把每一次这样的”进入边 + 离开边”配成一对。因为 $T$ 每条边只走一次，每对中的两条边互不相同；而 $T$ 经过所有边，所以 $v$ 关联的每条边都被配进某一对，一不多一不少。依据：欧拉回路的定义。
3. 起点 $s$ 处的配对要小心处理：首次离开 $s$ 的那条边在它之前没有”进入边”。但闭游走必然回到 $s$，于是把”首次离开 $s$ 的边”与”最后一次进入 $s$ 的边”配成一对（若 $\vert E\vert =0$ 则 $s$ 是孤立顶点，$\deg(s)=0$ 是偶数，无需配对）。依据：闭游走的定义。
4. 于是 $v$ 关联的全部边被分成若干两两不相交的二元组，故关联边数是偶数。在简单图中关联边数等于 $\deg(v)$，于是 $\deg(v)$ 为偶数。依据：第 1–3 步。
5. $v$ 是任意的，所以 $G$ 中每个顶点的度都是偶数，$G$ 是偶度图。依据：第 4 步。
6. （柯尼斯堡的应用） 七桥图的度数为 $\deg(A)=3,\deg(B)=5,\deg(C)=3,\deg(D)=3$（脚本数出度为 $3,5,3,3$，度和 $14=2\times 7$ ✓），四个顶点全是奇度。由必要性方向，不存在欧拉回路，所以”走遍七座桥恰好一次并回到起点”不可能。这就回答了 1736 年的问题。依据：第 5 步。

逐步推导（充分性：构造性算法 + 归纳）：

1. 子程序 $\text{FIND TOUR}(G,s)$：从顶点 $s$ 出发，每一步任选一条尚未走过的、与当前顶点关联的边，沿它走到下一个顶点；重复直到当前顶点没有未走过的关联边（”卡住”）为止。依据：算法定义（贪心游走）。
2. 断言（$\text{FIND TOUR}$ 一定在 $s$ 处卡住）：设游走在顶点 $v$ 处卡住。对任意 $v\neq s$，游走的每一次”进入 $v$”都消耗一条关联边，而游走的每一步”离开 $v$”也消耗一条；由第 1 步的走法，游走是”进去一次、出来一次”地交替经过 $v$，所以游走结束时，$v$ 处被走过的关联边数是奇数（最后停在 $v$ 时只进未出）。但 $G$ 是偶度图，$\deg(v)$ 是偶数，偶数减奇数 $=$ 奇数 $>0$，故 $v$ 处至少还有一条未走过的边，与”卡住”矛盾。因此 $v\neq s$ 不可能，游走只能在 $s$ 处卡住。依据：偶度假设 + 奇偶性论证。
3. $\text{FIND TOUR}$ 的产物：它返回一条从 $s$ 出发、以 $s$ 结束的闭游走（即 $G$ 的一个 tour），但未必是欧拉回路——因为可能还剩没走过的边。依据：第 2 步。
4. 拼接子程序 $\text{SPLICE}(T,T_1,\dots,T_k)$：输入若干条边不相交的 tour，其中 $T$ 与每一条 $T_i$ 都共享至少一个顶点。输出一条单一 tour $T^{\prime}$，走遍 $T,T_1,\dots,T_k$ 的全部边：做法是沿 $T$ 走，每当走到一个与某条 $T_i$ 相交的顶点 $s_i$ 时，就先绕道把 $T_i$ 从 $s_i$ 完整走一圈回到 $s_i$，然后继续沿 $T$ 前进。依据：算法定义。
5. 递归算法 $\text{EULER}(G,s)$：先算 $T=\text{FIND TOUR}(G,s)$；再把 $T$ 的边从 $G$ 中删去，得到若干连通分量 $G_1,\dots,G_k$；对每个 $G_i$ 取”$T$ 上第一个与 $G_i$ 相交的顶点”为 $s_i$；递归调用 $\text{EULER}(G_i,s_i)$；最后输出 $\text{SPLICE}\big(T,\text{EULER}(G_1,s_1),\dots,\text{EULER}(G_k,s_k)\big)$。依据：算法定义。
6. 递归的合法性：删去 $T$ 的边后，每个顶点损失的度恰好是它在 $T$ 上被走过的关联边数，而由第 2 步的论证那是偶数；偶度减偶度仍是偶度。故每个 $G_i$ 都是偶度图。又 $G_i$ 由连通分量定义本身是连通的。所以归纳假设可以应用。此外每删去 $T$ 至少一条边，故 $G_i$ 的边数严格小于 $G$ 的边数。依据：第 2 步 + 连通分量定义。
7. $T$ 与每个 $G_i$ 确实相交：$G$ 连通，$G_i$ 中的顶点 $w$ 与 $s$ 之间有一条 path，这条 path 必在某处离开”完全由 $T$ 上顶点构成的部分”而进入 $G_i$，其跨越边必是 $T$ 的边（因为 $G_i$ 之外的边都被 $T$ 吸收了），故交点存在。于是 $s_i$ 有定义，$\text{SPLICE}$ 的前提满足。依据：连通性 + 第 5 步。
8. 归纳基础：$m=0$（没有边）时无 tour 可找，命题空洞成立。依据：基础情形的平凡性。
9. 归纳假设：对边数 $\le m$ 的所有偶度连通（允许孤立顶点）图，$\text{EULER}$ 输出欧拉回路。依据：强归纳假设。
10. 归纳步骤：设 $G$ 有 $m+1$ 条边。由第 5 步，$G_i$ 的边数都 $\le m$，故由归纳假设 $\text{EULER}(G_i,s_i)$ 输出 $G_i$ 的欧拉回路。由第 4 步，$\text{SPLICE}$ 把这些 tour 与 $T$ 拼成一条走遍”$T$ 的边 $\cup$ 所有 $G_i$ 的边 $=$ $G$ 的全部边”的单一 tour，且每条边恰好走一次，起点终点都是 $s$。这就是 $G$ 的欧拉回路。依据：第 4、5、9 步。
11. 由归纳原理，对任意边数的偶度连通图，$\text{EULER}(G,s)$ 都输出欧拉回路。充分性得证。依据：第 8–10 步。
12. 必要性（第 1–6 步与连通性部分）与充分性（第 1–11 步）合起来给出”当且仅当”。依据：双向。

【证明机制解说】：这个定理的两个方向展现了两种截然不同的数学风格。必要性是”记账”：欧拉回路是一份审计日志，凡是进入的必被离开，账目必然平衡，所以度数为偶——完全不需要构造任何东西。充分性是”搭积木”：先找一条小回路（$\text{FIND TOUR}$），再看剩下什么（偶度图的剩余部分仍偶度），然后把小回路拼进大回路（$\text{SPLICE}$），对规模归纳。$\text{FIND TOUR}$ 一定回到起点这一断言（第 2 步）是全证明的枢纽：它把”偶度”这一全局条件翻译成”游走无法停在中途”这一局部事实——因为停在中途要求该顶点有奇数条已走过的边，而它的总度数是偶数，于是必然还剩未走过的边可走。$\text{SPLICE}$ 的机制则是一个”绕道“：走到交叉点 $s_i$，先把支路 $T_i$ 绕完回到 $s_i$，再接着走主干，就像旅游时在某地插入一段一日游。

图 9.1（拼接机制的 ASCII 示意）：

图 9.1  欧拉定理充分性的"拼接"机制（SPLICE）
=========================================================
 原图 G（偶度图，每个顶点度数为偶数）：
          2
         / \
        1---3      <- 三角形 T1 = 1->2->3->1
         \ /
          4---5    <- 三角形 T2 = 1->4->5->1
         /
        1

 步骤 1: FIND TOUR(G, 1) 随便走，假设先走三角形 T1
          得到 T = 1 -> 2 -> 3 -> 1          （仍未覆盖 T2）

 步骤 2: 从 G 中删去 T 的边，剩下的图是 T2（连通分量 G1），
         T 与 G1 的交点是 1（即 s1 = 1）

 步骤 3: SPLICE(T, T1) —— 沿 T 走，走到交点上"绕道"
         1 -> 2 -> 3 -> 1      （走完 T）
                     |
                     +--> 在此绕道走 T2:  1 -> 4 -> 5 -> 1
                     |
         得到 T' = 1 -> 2 -> 3 -> 1 -> 4 -> 5 -> 1
         每条边恰好一次，起点终点都是 1  ==>  欧拉回路！

 若是另一种走法（FIND TOUR 先走 T2），结果对称：
         T'' = 1 -> 4 -> 5 -> 1 -> 2 -> 3 -> 1
         同样是一条合法欧拉回路（脚本已验证两者都合法）
=========================================================

定理 9.4（欧拉路径 Eulerian path 的判定）：无向图 $G$ 存在欧拉路径——经过每条边恰好一次、但不要求回到起点的游走——当且仅当 $G$ 的奇度顶点个数恰好是 $0$ 或 $2$；且所有边都位于同一个连通分量内。

证明策略：把”路径”情形归约到”回路”情形（添加一条虚拟边），再用定理 9.3。这是数学中极其常用的”把新问题变形成已解决问题”的思路。

逐步推导：

1. （$\Leftarrow$，$0$ 个奇度顶点）此时 $G$ 是偶度图，由定理 9.3 存在欧拉回路，而欧拉回路当然是欧拉路径（闭的路径也是路径）。依据：定理 9.3。
2. （$\Leftarrow$，恰好 2 个奇度顶点）设奇度顶点为 $u\neq v$。若 $u$ 与 $v$ 之间已有一条边，则不能直接添边；正确做法是把问题建立在”添加一条新边 $\{u,v\}$（可以是重边）得到 $G^{\prime}$“上。依据：构造。
3. $G^{\prime}$ 中 $u,v$ 的度各加 1 变成偶数，其余顶点度数不变（仍为偶数），故 $G^{\prime}$ 是偶度图。又 $G^{\prime}$ 连通（由”所有边在同一连通分量”的假设加上新边），由定理 9.3 存在欧拉回路 $T^{\prime}$。依据：定理 9.3。
4. 把 $T^{\prime}$ 中的虚拟边 $\{u,v\}$ 删掉：$T^{\prime}$ 是一条闭游走，删去其中那一步就得到一条从 $v$ 到 $u$（或反向）的游走 $T$，它经过 $G^{\prime}$ 中除虚拟边外的每条边恰好一次（$G$ 中的每条边都被 $T^{\prime}$ 走过一次，且虚拟边不在 $G$ 中），即 $G$ 的欧拉路径。依据：第 3 步。
5. （$\Rightarrow$）反过来，设 $G$ 有欧拉路径 $T$，从 $a$ 走到 $b$（$a\neq b$ 时不闭，$a=b$ 时即欧拉回路）。对任意 $v\notin\{a,b\}$：$T$ 每次进入 $v$ 必离开 $v$，配对论证给出 $\deg(v)$ 为偶数。对 $a$：$T$ 有一次”只出不进”（起点），其余进出配对，所以 $\deg(a)$ 为奇；同理 $\deg(b)$ 为奇。若 $a=b$（闭游走），配对论证给出所有度数为偶，即 0 个奇度顶点。依据：定理 9.3 必要性的配对论证。
6. 故奇度顶点个数恰为 2（当 $a\neq b$）或 0（当 $a=b$），只能是这两种情形。依据：第 5 步。
7. 连通性要求同定理 9.3：欧拉路径经过所有边，故所有非孤立顶点都在同一个连通分量里。依据：定理 9.3 必要性第一部分。
8. 第 1–4 步与第 5–7 步合起来给出”当且仅当”。依据：双向。

【证明机制解说】：这个归约的”灵光一现”是虚拟边：不要求回到起点，等价于”要求回到起点但允许走一条实际上不存在的边”。奇度顶点恰好是 $a$ 与 $b$——游走的两个”半截端点”，因此把 $a,b$ 用手搭起来（虚拟边）就补成回路。这也解释了推论 9.1.1（奇度顶点个数为偶）在欧拉语境下的意义：奇度顶点必定”成对出现”，因为一条不闭的游走恰好有两个端点。

反例（条件不可省）：

• 有 2 个奇度顶点：有欧拉路径，无欧拉回路。 取”房子图” $H$：$V=\{1,2,3,4,5\}$，$E=\{\{1,2\},\{2,3\},\{3,4\},\{4,1\},\{2,5\},\{4,5\}\}$（四边形顶上加个尖顶，尖顶连到 2 和 4）。度数为 $\deg(1)=2,\deg(2)=3,\deg(3)=2,\deg(4)=3,\deg(5)=2$——恰有 2 个奇度顶点（2 和 4）。故无欧拉回路（不是偶度图），但有欧拉路径。一条合法的走法是 \(2\to 3\to 4\to 1\to 2\to 5\to 4\) （脚本逐边校验：6 条边全部用到、每条恰好一次、起点 2 终点 4 不闭合 ✓）。另一条对称的走法是 $2\to 5\to 4\to 3\to 2\to 1\to 4$，也合法。
• 不连通但偶度：仍无欧拉回路。 取两个不相交的三角形 $\{1,2,3\}$ 与 $\{4,5,6\}$，两个图都是偶度（每个顶点度 2）但整个图不连通，无论从哪出发都无法一次走完两组边。这说明定理 9.3 中”连通”这一条件不可省。
• 连通但奇度：无欧拉回路。 七桥图连通、有 7 条边，但四个顶点全为奇度（$3,5,3,3$），故无欧拉回路；也无欧拉路径（奇度顶点 4 个，不是 0 或 2）——所以”走遍七桥恰好一次（不要求回到起点）”同样做不到。脚本用 Hierholzer 算法与穷举逻辑双重确认：柯尼斯堡图既无欧拉回路也无欧拉路径。

与经典问题的联系

问题一：柯尼斯堡七桥问题（图论的诞生）

• 实际背景：普鲁士柯尼斯堡城中有普列戈利亚河 (Pregel)，把城市分成两岸 $A$、$D$ 与两座岛 $B$、$C$；七座桥连接这些陆地。市民晚饭后散步时热衷于挑战：”能不能走一条路线，把七座桥每座恰好走一次，并回到出发点？”
• 数学建模：把每块陆地抽象成一个顶点，每座桥抽象成一条边，得到多重图 $V=\{A,B,C,D\}$，$E$ 为 7 条边的多重集。
• 求解：由定理 9.3 的必要性方向，欧拉回路存在要求所有度为偶。实际度数为 $\deg(A)=3$、$\deg(B)=5$、$\deg(C)=3$、$\deg(D)=3$，全为奇数。故不存在这样的路线。1736 年欧拉给出的正是这个不可能性证明，他也因此被认为是图论的创始人。
• 意义：这是”用不变量回答可行性问题“的最早范例：不去尝试所有路线（$7!=5040$ 种走法可以硬试），而是找到一个与走法无关的不变量（度的奇偶性），一击判定。这种思路在后来的算法理论中反复出现。

问题二：一笔画谜题与投递路线（中国邮递员问题）

• 一笔画 (one-stroke drawing)：给定一个图形，能否不抬笔、不重复地画完所有线条？这正是”是否存在欧拉路径”的问题，答案由定理 9.4 给出：奇度顶点数必须是 0 或 2。这是小学奥数题背后真正的数学。
• 中国邮递员问题 (Chinese Postman Problem)：邮递员要走过他负责的每条街道至少一次并回到邮局，如何走最短？若街区的图是偶度图，答案就是欧拉回路（每条街恰好走一次，没有浪费）。若有 $2k$ 个奇度顶点，则必须重复走一些街道；最优解等价于在奇度顶点之间找一组最短的配对路径（最小权匹配），把图”补”成偶度图。这是欧拉定理在运筹学中的直接延伸。
• 扫地机器人 / 除雪车路线规划：同一类问题的工业版本：希望每条通道都被覆盖至少一次且总路程最小。

问题三：网络与互联网中的图论语言

• 路由：互联网可以建模成图，节点是路由器，边是链路。”从源到目标能不能送达”就是连通性问题；”最少经过几跳”就是距离问题（本讲定义）；路由协议（如 OSPF）计算的就是加权图上的最短路径。
• 最小生成树与网络设计：要让 $n$ 个城市都能互相通信且总造价最低，需要一棵生成树，其边数是 $n-1$——正是 $K_n$ 的边数 $\binom{n}{2}$ 中的一小部分。L10 会给出树的四种等价刻画并证明”连通 + 无环 $\iff$ 连通 + $n-1$ 条边”。
• 社交网络分析：顶点是人、边是”互相认识”。度分布刻画影响力，连通分量刻画社群，二分图刻画”两类主体之间的关系”（如用户—商品二部图，是推荐系统的标准模型）。
• de Bruijn 图与序列生成（官方 Note 的练习题，属于 L10 前的预告）：$2^n$ 位循环序列使每个长度 $n$ 的 0/1 串恰好作为连续子串出现一次，这样的序列可由 de Bruijn 图中的欧拉回路生成——因为 de Bruijn 图是有向图，定理 9.3 需修改为”每个顶点的入度 $=$ 出度”（官方 Note 明确指出了这一修改）。这是欧拉定理从无向图推广到有向图的标准做法。

问题四：作为”组合码”的图论（与 Lecture 8 的呼应） L08 指出纠错码有两大流派：基于有限域多项式的代数码（Reed–Solomon）与基于图论的组合码。图论在这里的角色是：把”码字”看成图的子集，用图的连通性、围长、度分布等结构性质来保证码的最小距离。低密度奇偶校验码 (LDPC) 与图码 (graph code) 都是这一流派的现代产物。L08 与 L09 因此是一对”同一目标、两种语言”的姊妹讲。

与其他讲次的关联

• 讲次 0（直接证明 / 集合与记号）：本讲的图定义完全建立在集合语言上：$V$ 是集合，$E$ 是 $V$ 的二元子集构成的集合，有向图的 $E\subseteq V\times V$ 用的是笛卡尔积。集合的并与、交、差、子集关系是后续所有图论表述的基础。
• 讲次 2（证明技巧 II：反证法、分情形、极端原理）：握手引理的推论（奇度顶点个数为偶）的反例分析用了”抓极端值”（取度最大的 4 与度最小的 0）的极端原理；定理 9.3 必要性中对”起点特殊”的分情形处理，也是 L02 技巧的直接应用。
• 讲次 3（归纳法与强归纳）：定理 9.3 充分性的 $\text{EULER}$ 算法是强归纳的典型范例——删去一条回路后可能得到多个连通分量，必须分别对每一个更小的图使用归纳假设，弱归纳在这里不够用。L10 将继续用归纳证明”树 = 连通无环 = 连通且有 $n-1$ 条边”与欧拉公式 $v+f=e+2$。
• 讲次 7、8（多项式与编码）：L07 的系数表示/值表示对偶与 L08 的 Reed–Solomon 码是”代数码”路线；本讲的图是 L08 提到的”组合码”路线的语言。两条路线在官方 Note 的同一段话里被并列提出，本讲正是那条岔路的入口。
• 讲次 10（Graphs II）：直接延续本讲。L10 将讨论平面图与欧拉公式 $v+f=e+2$、树（连通无环，含 $n-1$ 条边）、超立方体（$2^n$ 个顶点、每个度 $n$、$n2^{n-1}$ 条边，其边数证明正是握手法则的又一次应用）、以及五色定理与 Kuratowski 定理。本讲的”完全图 $K_n$”与”二分图”在 L10 立刻派上用场：$K_5$ 与 $K_{3,3}$ 正是两个最小的非平面图。
• 讲次 11（Stable Matching）：Gale–Shapley 算法处理的是二分图上的匹配问题——一边是求职者、一边是岗位，边表示”可接受”。本讲的二分图定义与度数概念（”每个求职者的偏好表长度就是他在图中的度”）是 L11 建模的直接前提。
• 讲次 12、13（可数性与可计算性）：本讲的图是有限图；L12 将讨论无限集合的大小。图上的算法（如”是否存在欧拉回路”）是多项式时间可判定的，而 L13 将给出不可判定的问题（停机问题）；L10 提到的”判定图是否同构”则至今没有已知多项式算法。这三讲共同刻画出”可判定 / 难判定 / 不可判定”的谱系。
• 讲次 14、16（计数与组合证明）：$\binom{n}{2}$ 条边、连通图的生成树计数（Cayley 公式 $n^{n-2}$）都是双计数与双射证明的经典素材；本讲定理 9.1 与 9.2 已经是”双计数”的最简演练。

关键要点

1. 图 = 顶点集 + 边集。无向边是二元子集 $\{u,v\}$，有向边是有序对 $(u,v)$；本课程默认简单图（无自环、无重边），遇到七桥这类多重边情形就把重边塌缩掉（但柯尼斯堡的度数必须按 7 条桥来数）。
2. 握手引理 $\sum_{v\in V}\deg(v)=2\vert E\vert $ 是双计数的第一课：数”顶点—边关联对”这个集合，按顶点数得到 $\sum\deg$，按边数得到 $2\vert E\vert $。推论：奇度顶点个数必为偶数。
3. 欧拉定理（有回路）：连通（孤立顶点可例外）$+$ 所有度为偶 $\iff$ 存在经过每条边恰好一次的闭游走。
   • 必要性：回路中”每次进入必离开”，把边配对，故度为偶。
   • 充分性：$\text{FIND TOUR}$（必回到起点）$+$ $\text{SPLICE}$（在交点绕道）$+$ 对边数强归纳。
4. 欧拉路径（不必回到起点）：奇度顶点个数恰为 $0$ 或 $2$。证明靠”添加一条虚拟边把两个奇度端点接上”归约到回路情形。
5. 术语要精确区分：walk（可重复顶点）$\supsetneq$ path（顶点互不相同）；tour（首尾相同）$\supsetneq$ cycle（首尾相同且中途不重复）；连通 $\ne$ 完全图（连通只要求”能走到”，完全图要求”直接相连”）。

常见误区与注意事项

1. 把”度”与”邻居数”在多重图中混为一谈。在简单图中二者相等，所以定义可以写成 $\deg(u)=\vert \{v:\{u,v\}\in E\}\vert $；但在多重图（如柯尼斯堡）中，度是关联边的条数（$B$ 的度是 5，而 $B$ 只有 3 个邻居 $A,C,D$）。若用邻居数当度，七桥问题的整个论证就错了。
2. 忘记欧拉定理里的”连通”条件。所有顶点度数为偶不足以保证欧拉回路：两个不相交的三角形都是偶度图，却没有一条游走能覆盖两者的所有边。正确的陈述是”连通且偶度”（孤立顶点若不关联任何边可以忽略，因为它本来就在所有边之外）。
3. 把必要性和充分性搞反。”度为偶”是欧拉回路的充要条件；”奇度顶点 ≤ 2”是欧拉路径的充要条件。常见错误是把”存在欧拉路径”误当成”存在欧拉回路”，于是把房子图（2 个奇度顶点）误判为有欧拉回路。判定的标准流程是：先数奇度顶点个数——0 个 $\to$ 回路（也顺带有路径），2 个 $\to$ 只有路径，$\ge 4$ 个 $\to$ 两者都没有（如柯尼斯堡）。
4. 把”一笔画”误解为”每条边恰好一次”以外的含义。一笔画允许顶点重复经过，只禁止边重复。若误以为顶点也不能重复，问题就变成了”是否存在哈密顿路径”，那是完全不同的（且困难得多、L10 之后才涉及）问题。欧拉（边）与哈密顿（顶点）是图论中一对著名的”看起来一样、难度天差地别”的问题。
5. 在 $\text{FIND TOUR}$ 的论证里忘记”起点特殊”这一分情形。对 $v\neq s$，游走停在 $v$ 意味着已走过奇数条关联边（进多出少一次）；但对起点 $s$，游走”从 $s$ 出发”也算作一次”只出不进”，必须把首次离开与最后一次进入配成一对才能让论证成立。漏掉这个细节是最常见的证明漏洞。
6. 混淆”环 cycle”与”回路 tour”的用词。本讲中 cycle 指顶点互不相同的闭合结构（简单环）；tour 是允许顶点重复的闭游走。欧拉回路是 tour 而不是 cycle——它必然重复经过顶点（例如 G3 上的 $1\to 4\to 3\to 2\to 1$ 经过 4 个顶点各一次，看似像 cycle，但在”8 字形”图上 $1\to 2\to 3\to 1\to 4\to 5\to 1$ 把顶点 1 走了三次，这就绝不是一个 cycle）。“顶点可以重复”正是欧拉回路能走遍所有边的代价：如果额外要求顶点也不能重复，问题就变成了哈密顿回路（见误区 4），难度完全不同。
7. 把 $K_n$ 的边数记成 $n(n-1)$。那是有向完全图的边数（每条无向边对应两条有向边）。无向完全图的边数是 $n(n-1)/2$，也就是握手引理给的结果；每个顶点的度是 $n-1$ 而不是 $n$。
8. 图示中的交叉不代表不连通或错误。在平面上画图时，两条边在纸上”交叉”只是画法问题，不代表图中有交点这个顶点——这与 L10 的”平面图”概念直接相关：$K_4$ 可以画成有交叉的样子，但它其实是平面图（能换一种画法消除交叉）。

思考题（带答案）

Q1.（纯计算） 某小镇的街区图 $G$ 有顶点 $V=\{a,b,c,d,e,f\}$，边集为 \(E=\{\{a,b\},\{a,c\},\{b,c\},\{b,d\},\{c,d\},\{d,e\},\{d,f\},\{e,f\}\}.\) (a) 写出每个顶点的度数，并验证握手引理。 (b) 判断 $G$ 是否有欧拉回路；若没有，是否有欧拉路径？ (c) 给出 $G$ 中一条从 $a$ 到 $e$ 的最短路径及其长度，并给出一个包含 $d$ 的环。

Q2.（概念/证明） (a) 证明：任意无向图中，度数为奇数的顶点个数是偶数。(b) 用这一结论说明”不可能存在一个 7 个顶点的无向简单图，其中 6 个顶点的度分别是 $1,2,3,4,5,6$，而第 7 个顶点的度是 $10$”。

Q3.（概念 + 反例构造） 下面三个图都被宣称”有欧拉回路”，请逐个判断真伪并说明理由；对为假的，指出是哪个条件失效，并判断它是否有欧拉路径。 (i) 单个顶点 $V=\{1\}$，$E=\varnothing$。 (ii) $V=\{1,2,3,4,5,6\}$，$E=\{\{1,2\},\{2,3\},\{3,1\},\{4,5\},\{5,6\},\{6,4\}\}$。 (iii) $V=\{1,2,3,4\}$，$E=\{\{1,2\},\{2,3\},\{1,4\},\{4,3\}\}$（即路网图 $G_3$）。

图 9.2  柯尼斯堡七桥图：ASCII 重绘 + 各顶点度数标注
=========================================================
 实际地理（左）                抽象成图（右）

    A 岸                         A
   ——+——                        ||  \        A-B 之间有 2 座桥
     |  |                        ||   \
   [B 岛]—[C 岛]                 B----C       A-C 之间有 1 座桥
     |  |                        ||   |       B-C 之间有 1 座桥
   ——+——                        ||   |       B-D 之间有 2 座桥
    D 岸                         D----+       C-D 之间有 1 座桥

 顶点与度数：
   deg(A) = 3   (两条到 B，一条到 C)
   deg(B) = 5   (两条到 A，一条到 C，两条到 D)
   deg(C) = 3   (一条到 A，一条到 B，一条到 D)
   deg(D) = 3   (两条到 B，一条到 C)
   ------------------------------------------------
   度和 = 3 + 5 + 3 + 3 = 14 = 2 x 7 = 2|E|   (握手引理 OK)
   奇度顶点个数 = 4   (A, B, C, D 全是奇度)
   ------------------------------------------------
 由欧拉定理必要性：欧拉回路要求所有度为偶  ==>  没有欧拉回路
 由欧拉路径判定：奇度顶点个数需为 0 或 2，实际是 4
                 ==>  连"不要求回到起点"的一笔画也没有
 结论：1736 年欧拉证明的"不可能"成立。
=========================================================

图 9.3  欧拉回路 / 欧拉路径 / 两者皆无：三类小图对照
=========================================================
【第一类】全偶度 + 连通  ==>  有欧拉回路  (定理 9.3)
   G3 = 四边形                      "8 字形"（两个三角形共顶点）
       1 ----- 2                             2
       |       |                            / \
       |       |                           1---3
       4 ----- 3                            \ /
                                            4---5
   度数: 1:2 2:2 3:2 4:2                 度数: 1:4 2:2 3:2 4:2 5:2
   欧拉回路举例:                         欧拉回路举例:
     1->4->3->2->1                          1->2->3->1->4->5->1
   (4 条边各一次, 闭合)                    (6 条边各一次, 闭合)
   <-- 注意这是 SPLICE 的实战: 先把三角形 1-2-3-1 走成主干,
       到达交点 1 后绕道走三角形 1-4-5-1

【第二类】恰 2 个奇度顶点 + 连通  ==>  只有欧拉路径  (定理 9.4)
   房子图 H：边集 = {1-2, 2-3, 3-4, 4-1, 2-5, 4-5}
   即四边形 1-2-3-4 加上"尖顶"5，5 连到 2 和 4。
   （注意 2 与 4 不相邻、1 与 3 不相邻——它们是四边形的对角）

            5
           / \
          /   \
         2     4
         | \ / |
         |  X  |
         | / \ |
         1     3
   真正的边: 1-2, 2-3, 3-4, 4-1 (四边形), 2-5, 4-5 (尖顶)
   度数: 1:2 2:3 3:2 4:3 5:2   <-- 奇度顶点是 2 和 4
   欧拉路径举例: 2->3->4->1->2->5->4     (6 条边各一次, 不闭合)
   没有欧拉回路 (2 个奇度顶点)!

【第三类】>= 4 个奇度顶点  ==>  两者皆无
   柯尼斯堡七桥图 (见 图 9.2): 4 个奇度顶点
=========================================================

图 9.4  FIND TOUR 为什么一定回到起点（偶度图，起点 s=1）
=========================================================
  步骤追迹（三角形 1-2-3-1，每个顶点度都是 2）

  时刻   当前顶点   已走过的关联边数        能否卡住？
  ---------------------------------------------------------
   t=0      1        1 (只出不进: 边1-2)      不能 (还有边 1-3 没走)
   t=1      2        2 (进 1-2, 出 2-3)      不能
   t=2      3        2 (进 2-3, 出 3-1)      不能
   t=3      1        2 (进 3-1, 回到起点)     无未走边 -> 停在 s=1 ✓

  对 v != s 的一般论证：
     游走每"进入 v"就消耗 1 条边，每"离开 v"又消耗 1 条；
     若停在 v != s，则进入次数 = 离开次数 + 1，
     故已走过的关联边数 = 2k+1 (奇数)，
     而 deg(v) 是偶数 => 剩余未走的边数 = 偶数 - 奇数 = 奇数 > 0
     => 不可能卡住 => 只能停在起点 s。
  这就是"偶度"这一全局条件如何变成"回得来"这一局部事实。
=========================================================

附加算例（度数与握手引理的三次演练）

1. $K_5$：$n=5$ 个顶点，每个度 $5-1=4$（偶），度和 $=5\times 4=20$，故 $\vert E\vert =20/2=10=\binom{5}{2}$ ✓（脚本验证）。注意 $K_5$ 是偶度图（$n=5$ 为奇数时 $K_n$ 的度 $n-1$ 为偶），而且显然连通，所以 $K_5$ 有欧拉回路——事实上 $K_5$ 的 10 条边可以一笔画完。这也说明”有欧拉回路”与”是平面图”是两件毫不相干的事（$K_5$ 在 L10 中将被证明不可平面）。
2. $K_4$：$n=4$，每个度 $3$（奇），4 个奇度顶点，度和 $=4\times 3=12$，$\vert E\vert =6$ ✓。奇度顶点 4 个 $\ge 4$，故 $K_4$ 既无欧拉回路也无欧拉路径（脚本用 Hierholzer 逻辑确认）。
3. $K_{3,3}$：二分图，$\vert V\vert =6$、$\vert E\vert =9$，每个顶点度都是 3（奇），度和 $=6\times 3=18=2\times 9$ ✓。6 个奇度顶点，无欧拉路径。
4. $C_6$（六边形环）：$\vert V\vert =6$、$\vert E\vert =6$，每个度 2，度和 $=12=2\times 6$ ✓，无奇度顶点，有欧拉回路（就是沿着环走一圈）。而 $C_5$（五边形）：每个度 2，$\vert V\vert =5$、$\vert E\vert =5$，度和 $10=2\times 5$ ✓，也有欧拉回路。注意 $C_6$ 是二分图而 $C_5$ 不是（脚本用贪心二染色验证），但两者都有欧拉回路——再次说明”二分”与”欧拉”是彼此独立的性质。

附加算例（反例：奇偶性检查通过、但图仍不存在） Q2 的反例提醒我们奇偶性只是必要条件。更经典的例子是度序列 $(3,3,3,1)$（4 个顶点）：奇度顶点有 4 个（偶数，奇偶性检查通过），$3+3+3+1=10$ 是偶数，看似可行。但最大度是 3，说明某个顶点与所有其他 3 个顶点都相连——于是其余 3 个顶点各自至少有 1 度来自它，其中度数为 1 的那个顶点度数记为 1 恰好用掉，而另外两个度数为 3 的顶点除了连到最大度顶点之外，还各需 2 度，它们之间最多只有 1 条边（简单图），共可获得 1 度，达不到 2 度——矛盾。故该度序列不可实现（脚本穷举 4 个顶点、6 条可能边的全部 $2^6=64$ 种图，实现数为 0）。结论：判定度序列可实现性需要 Erdős–Gallai 或 Havel–Hakimi 之类的算法，握手引理提供的只是第一个筛子。

附加算例（同构不变量：一个小实验） 上面提到”同构的图必有相同的边数与度序列”。反过来不成立：取 $V=\{1,2,3,4,5,6\}$， \(G_a:\;\{1\!-\!2,\ 2\!-\!3,\ 3\!-\!1,\ 3\!-\!4,\ 4\!-\!5,\ 5\!-\!6,\ 6\!-\!4\}\quad(\text{两个三角形用边 }3\!-\!4\text{ 相连}),\) \(G_b:\;\{1\!-\!2,\ 2\!-\!3,\ 3\!-\!4,\ 4\!-\!1,\ 1\!-\!5,\ 5\!-\!6,\ 6\!-\!2\}\quad(\text{四边形 }1\!-\!2\!-\!3\!-\!4\text{ 加路径 }1\!-\!5\!-\!6\!-\!2).\) 两者都有 6 个顶点、7 条边，度和都是 14 ✓，但环结构完全不同：脚本枚举出 $G_a$ 只有长度 3 的环（两个三角形，三角形之间那条边 $3\!-\!4$ 是桥 (bridge)——删掉它图就分裂成两块），而 $G_b$ 没有任何三角形，只有两个长度 4 的环与一个长度 6 的环。由于”存在长度为 3 的环”在同构下必须保持，$G_a$ 与 $G_b$ 不同构。这说明边数与度序列不是完整的同构不变量，判断同构需要更精细的工具（这也引出了”图同构问题”这一著名的算法难题，与 L13 的可计算性讨论呼应）。

附加算例（欧拉定理在四类小图上的判定汇总）

（表中所有”$\lvert E\rvert$、度和、奇度个数、是否有回路/路径”均由脚本逐项验算：每一行的度和都等于 $2\lvert E\rvert$ ✓，回路/路径判定与欧拉定理和定理 9.4 完全一致。注意”两个分离三角形”这一行是度全偶但不连通的关键反例；”柯尼斯堡”这一行是连通但 4 个奇度的关键反例。）

附加算例（柯尼斯堡的”放松版”：如果拆掉一座桥会怎样？） 设从柯尼斯堡图中删去 $A$ 到 $B$ 之间的一座桥。则度变为 $\deg(A)=2$、$\deg(B)=4$、$\deg(C)=3$、$\deg(D)=3$，度和 $=12=2\times 6$ ✓（现在有 6 条边）。奇度顶点是 $C$ 与 $D$，恰好 2 个，故按定理 9.4，此时存在欧拉路径（从 $C$ 到 $D$ 或反向）但仍无欧拉回路。若再拆掉 $C$ 到 $D$ 的那座桥，则度数变为 $(2,4,2,2)$，全偶且连通，于是存在欧拉回路了——七桥问题会变成”可以办到”。这组小实验直观展示了欧拉定理的判定边界：问题的答案完全由一个不变量（度的奇偶性）决定，与具体的桥长、地形、走法都无关。