补充导读：图模型、遍历与路径问题

学习目标

• 能写出图的顶点、边、方向、平行边与自环合同，并把关系编码成邻接表或邻接矩阵
• 能用 BFS 的层次证据和 DFS 的回退证据解释遍历结果，验证距离、父节点和复杂度
• 能区分欧拉路径、哈密顿回路、TSP 与最小生成树，不把“过边”和“过点”混用
• 能把图的一步关系提升为矩阵复合或随机漫步，并用小规模代码与反例检查判断

先声明：这不是原书的“图论章”

先预测：《数学女孩》前四卷的权威目录中是否有一章标题为“图论”？没有。本页是独立重写的跨卷补充，不冒充原书章节；它把第 3 卷第 8 章的等价关系、格点与商集，连接到第 1 卷的树形计数和第 4 卷的比较树、矩阵与随机漫步。

本页的 officialUnitId: mg3-08 是一个明确的核心锚点：它只承接“关系如何压缩对象、如何得到等价类”的桥梁，不声称原书已经讲过 BFS、欧拉路径或 TSP。读者可以因此区分三类证据：原书目录范围、独立推导的图论知识、以及本页新增的可运行实验。

一、关系模型：把图写成合同

图模型

把一群对象压缩为 G=(V,E)：顶点 V 说明对象，边 E 说明关系。边可以是无序对，也可以是有序对；可以带权，也可以保留多重边。建图的第一问不是“画得好不好看”，而是“每一条边的业务或数学语义是什么”。

邻接表 适合边数远小于顶点平方的稀疏图。若题目中的两座陆地之间有两座独立的桥，邻接表必须保存两个边对象，不能用集合去重；若边有方向，还要区分出边与入边。

图、边与可达性

无向图中，边 {u,v} 表示互相连接；有向图中，边 (u,v) 只表示 u 能走向 v。路径是边和顶点交替组成的序列；连通分量是彼此可达的顶点集合。孤立顶点的度为 0，在“走遍所有已有边”的问题里可以暂时忽略，但在“访问所有顶点”的问题里不能删除。

一个可靠的模型合同至少列出五项：顶点含义、边含义、方向、权重、平行边与自环规则。合同不完整时，所谓“最短路径”“度数”或“是否存在回路”都没有唯一答案。

二、从重叠的对到等价关系：为什么它是图的桥

第 3 卷第 8 章的关系构造提供了一个很好的桥：先把对象表示成有顺序的对，再声明哪些对被视为同一类；图模型也在做同样的事，只是把“关系”保留成边，而不是马上压缩掉。

两份孤独所衍生的产物：重叠的对与泰朵拉的发现

“两份孤独所衍生的产物”可以读成两个坐标共同描述一个对象；“重叠的对”则提醒我们检查两个表示是否指向同一类。泰朵拉的发现不是凭图形直觉猜出来的，而是从正自然数对不含0开始，记录哪些坐标允许进入模型，再寻找保持不变的关系。

元发现：交叉和与差值

“元发现”是发现自己正在寻找条件。若两个正自然数对满足 a+d=b+c，就有“外项之和等于内项之和”；另一种同样稳定的写法是 a-b=c-d。这里的“我的发现”必须转成可检验命题，不能停留在“谁都没发现的事实”式的惊讶：给出定义、必要性和一个反例，才知道它是否真的成立。

从自己的数学到等价类

“毕业生就是定理”是一种学习隐喻：一个发现经受反例检查后，才可以离开“家中”的直觉场景，成为“自己的数学”。“表现的压缩”把同一差值的一堆对压成差值类对应整数；“加法运算的定义”必须独立于所选代表，亦即代表元无关。于是 [1,1] 可以作为零元，交换坐标为负元，教师的存在和毕业典礼只是叙事外壳，真正的结构是等价关系把许多表示压成一个对象。

对衍生的产物：从自然数到整数

从自然数到整数的构造不能预用减法，否则会把尚未建立的负数偷偷当成定义工具；必须先用有序对和等价关系造出商集，再定义加法。两首歌重混与“对衍生的产物”可以帮助记忆：新对象不是凭空出现，而是从旧对象的表示和一个可逆的同一性标准中产生。

图、格点斜线与向量加法射影

把每个正自然数对画成平面格点，就得到“图”这一几何影子；满足 a-b=c-d 的点落在同一条“格点斜线”上。沿着斜线移动，相当于把多个表示投影到同一个差值类；“向量加法射影”说明逐分量加法如何在投影后变成整数加法。这正是图论的桥：节点可以是表示，边可以是一步变换，商集则把等价的节点折叠成一个类。

等号一般化：自反律、对称律与传递律

一个关系要像等号那样用于压缩，至少要检查自反律、对称律和传递律。它们分别保证“自己和自己同类”“换一个表示仍同类”“两次同类可以串起来”。“等号一般化”就是把等价关系当作更广的同一性标准；缺少任何一条，商集里的“类”都可能互相重叠，图上的节点也无法稳定解释。

商集、代表元素与具体商

商集是用关系去除集合中的表示重复；整数商集把正自然数对按差值关系折叠，有理数商集把分子分母对按交叉乘积关系折叠。每一类可以挑一个代表元素，但代表元素只是记号，不是对象本身；例如 Z/3Z 把整数按模 3 同余分为三个类。“同年级商集”是同样结构的熟悉类比：只要关系满足三条律，类的运算就不依赖挑了哪一个同学。

餐厅、两个人的晚饭与 Pair No算术

“餐厅”“两个人的晚饭”“一对翅膀”和“无力考试”是场景提示，不是证明本身；它们可以分别提醒我们区分对象、组合两个分量、检查对称性和承认尚未掌握的定义。把这种场景抽象成 Pair No算术 时，必须重新写出运算、单位元和逆元。最后的 “Poincare” 提醒我们：几何直觉可以发现不变量，但仍要回到定义和可逆映射。

三、表示、度数与遍历证据

简单图、多重图与有向图

简单图默认无方向、无平行边、无自环；多重图把每条桥视为独立边；有向图把依赖、调用或状态转移写成箭头。若把多重图强行转为邻接集合，后面的欧拉判断会少算边；若把有向边当无向边，BFS 得到的可达性也会被扩大。

度与握手定理

无向多重图中，顶点 v 的度记为 deg(v)。每条非自环边给两个端点各贡献 1；自环在同一顶点贡献 2，所以

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

右边是偶数，因此奇度顶点的数量必为偶数。这个局部度数事实会成为欧拉路径的必要条件，但它本身不能替代连通性检查。

BFS：用层次回答无权最短路

BFS 从起点入队，顶点第一次被发现时的层数就是无权图中的最短边数。实现应同时输出 distance[v]、parent[v] 和访问状态；沿父节点回溯才能把距离证据还原成一条路径。

验收时检查每条树边都满足 distance[child]=distance[parent]+1，每条无向图边的两个端点层数相差至多 1。邻接表上每个顶点和每条边只处理常数次，复杂度为 $\Theta(|V|+|E|)$。

DFS：用深入与回退回答结构问题

DFS 沿一条分支深入，走到死路后回退；递归版本借助调用栈，显式栈版本更容易控制深度。DFS 适合寻找连通分量、检测环和建立拓扑结构，但它访问的第一条路径不一定是最短路。

树：连通、无环与唯一简单路径

有限无向简单图中，以下条件等价：连通且无环；任意两顶点间恰有一条简单路径；连通且边数为 n-1；无环且边数为 n-1。只有 n-1 条边不够，一个三角形加一个孤立点就能构成反例。比较排序的决策树和卡塔兰计数的二叉树共享无环分支结构，但节点语义不同。

四、路径问题：先区分过边、过点和连通

欧拉路径：过边问题

欧拉路径

有限无向多重图存在欧拉回路，当且仅当所有非零度顶点在同一连通分量且奇度顶点为 0；存在欧拉开路径，当且仅当同样的连通条件成立且奇度顶点恰为 2。哥尼斯堡七桥的度数为 3,3,3,5，有 4 个奇度顶点，因此不存在每桥恰走一次的路径。

哈密顿回路：过点问题

哈密顿回路 哈密顿回路关心顶点，不适用欧拉路径的奇偶度条件。给出候选回路后，可以在线性规模内验证顶点是否全部出现且相邻项有边；一般图中的寻找与判定是 NP 完全难题，所以“候选可验证”不等于“高效易寻找”。

TSP 与最小生成树不是同一个优化问题

旅行商问题（TSP）寻找最短哈密顿回路，一般情形是 NP 困难；Held–Karp 动态规划仍有指数级状态，最近邻和局部搜索虽常用，却没有相同的一般最坏保证。最小生成树不要求回路，只要求全点连通、无环且总权重最小；Kruskal 用并查集避免成环，Prim 从已连通集合跨割选边，正确性来自割性质。

五、邻接矩阵与随机漫步

顶点编号后，邻接矩阵 A 把一步关系写成代数。对适当的无向简单图，(A^k)_{ij} 统计从 i 到 j 的长度为 k 的游走；矩阵乘法把连续两步压成一步复合。若每一行按出度归一化得到转移矩阵 P，随机漫步的状态分布满足

$$\mathbf p_{t+1}=P\mathbf p_t.$$

这里必须先约定向量是行向量还是列向量，否则乘法方向会错。矩阵负责记录结构，概率负责记录权重；第 4 卷的随机漫步正好把路径、矩阵和状态变化接在一起。

分步实验：从关系到可计算的路径

⚡分步1 / 4

1. 1
2. 2
3. 3
4. 4

重置

1. 建模：切换图的合同

先预测同一组顶点在简单图、多重图和有向图中会怎样变化，再切换实验模式。检查平行边、边方向、度数和邻接记录，最后按“顶点、边、方向、权重、自环”五项合同复述。

简单图多重图有向图重置

上一步播放下一步

小结：先建对图，再选对问题

• 图模型必须声明顶点、边、方向、权重、平行边和自环；G=(V,E) 是合同，不是装饰。
• 等价关系的自反、对称、传递三条律说明如何把多个表示压成一个类，这也是本页映射 mg3-08 的核心桥梁。
• BFS 用层次和父节点支持无权最短路，DFS 用深入和回退支持结构搜索；二者都需要访问状态。
• 欧拉路径过边，哈密顿回路过点，TSP 做回路优化，MST 做无环连通优化。
• 邻接矩阵把一步关系变成可复合的代数，转移矩阵把路径计数提升为随机漫步的状态更新。

练习与答案

练习

1. 问题 1：修订一份建图合同

给出一个“城市与道路”的模型，分别说明简单图、多重图和有向图如何改变 V、E、度数与可达性；指出什么时候邻接表不能去重。

查看答案

城市是顶点，道路是边；若道路没有方向则用无向边，有单行规则则用有向边，同一城市间多条独立道路必须保留为多重边。合同还要写权重、自环规则和邻接表示，因此不能为了方便把独立道路放进一个只保留键的邻接集合。

2. 问题 2：验证 BFS 与 DFS

对一个含有环的无权图，分别写出 BFS 的 distance、parent 和 DFS 的回退记录；解释为什么“第一次到达”只有在 BFS 中能推出最短边数。

查看答案

BFS 按层入队，顶点第一次被发现时，队首顶点已经具有最小层数，因此 distance[child]=distance[parent]+1。DFS 可能先沿较长分支深入，第一次到达终点不保证最短；它应记录访问状态、栈或递归回退，用于连通分量和环检测。

3. 问题 3：选择路径判据

一个无向多重图的非零度顶点连通，奇度顶点有 4 个。它能否有欧拉路径？若题目改成“每个顶点一次”，还可以沿用这个结论吗？

查看答案

不能有欧拉路径，因为欧拉开路径要求恰有 0 或 2 个奇度顶点；4 个奇度顶点不满足必要条件。改成每个顶点一次后问题变成哈密顿回路，奇度条件不再是充分或必要的判据，需要检查候选覆盖与相邻关系，并区分一般判定的复杂度。

4. 问题 4：扩展矩阵实验

把图的邻接矩阵扩展成带权转移矩阵：显示 A^2 统计两步游走，显示 Pp_t 更新状态分布，并加入一个“方向约定错误”的测试。

查看答案

先固定顶点编号和向量约定，再用矩阵乘法计算 A^2；把每行按出度归一化得到 P，用 p_{t+1}=Pp_t 更新列向量分布。测试应验证每个概率非负且总和为 1，并故意交换行向量与列向量来确认界面能报告维度或方向错误；重置后恢复无错误的初始图。

名词解释

本章出现的专业名词，用大白话再讲一遍。

图模型

用顶点集合和边集合表达对象关系的模型，必须同时写明方向、权重与边的保留规则。

邻接表

为每个顶点保存相邻顶点或边的列表，适合稀疏图和线性规模遍历。

BFS

广度优先搜索，用队列按距离层次发现顶点并建立无权最短路径树。

DFS

深度优先搜索，沿分支深入并在死路处回退，适合连通、环和拓扑结构分析。

欧拉路径

恰好经过每条边一次的路径；无向图还要检查非零度顶点连通和奇度数条件。

哈密顿回路

恰好经过每个顶点一次并回到起点的回路，不能用欧拉路径的奇度判据替代。