《把定理跑出来》系列第 3 讲。这一讲有两个最最浪漫的问题哥尼斯堡七桥图论的出生地和最残酷的问题哈密顿圈NP 完全的入门体验。课本把它们排在一起讲但两者的难度差距是整个计算复杂性理论的差距欧拉回路有多项式时间的充要条件看一眼度数就行哈密顿圈是 NP 完全——没有已知的好判定三种经典算法在三堵不同高度的墙前排队倒下。本讲 8 张图全部由文末代码生成种子固定SEED2026可复现。摘要七桥问题实证哥尼斯堡七桥建模后度数 [5,3,3,3]4 个全奇点 → 欧拉回路与通路都不存在1736 年的论文30 行代码重做历史上真加过桥——加一座 B–C 桥后度数变 [5,4,4,3]恰 2 奇点Hierholzer 跑出通路0→1→0→2→0→3→1→2→38 条边恰用一次判定 × 构造对拍900 个随机图全偶度/恰 2 奇点/一般随机各 300——判定说是的图 Hierholzer全部跑出合法回路判定说否的图构造全部失败有向版 200 组同样零分歧Hierholzer 环合并8 字图两帧完成——第一帧走出三角形 0-1-2-0第二帧在顶点 0 处插入 0-3-4-5-0教科书插图级别的可视化Ore/Dirac 只是充分条件n12 随机图里满足最小度 ≥ n/2的 94 张回溯全部找到哈密顿圈94/94但反例同样现成——星图 K₁,₅ 最小度 1 无哈密顿圈圈图 C₆ 最小度 2 却有条件充分不必要三堵规模墙同一批有哈密顿圈的图n7…28暴力枚举 n11 已 621msn! 的墙状压 DP n20 才 29ms2ⁿ 的墙更高回溯在有解且结构好的图上 n28 仅 7ms——但下一张图会看到它的底牌NP 完全露脸G(24,p) 的哈密顿概率在理论阈值 (ln nln ln n)/n 0.181 附近从 0 爬到 1阈值附近回溯超时率冲到 22/25——最难判的样本恰好堆在阈值上这不是实现慢是问题难。关键词七桥问题欧拉回路欧拉通路Hierholzer有向欧拉哈密顿圈Ore 定理Dirac 定理NP 完全状压 DP回溯剪枝随机图阈值目录1. 七桥问题图论的出生30 行代码重做2. 欧拉判定定理 × Hierholzer900 组对拍2.1 环合并教科书插图的生成过程3. 有向图欧拉入度 出度4. 哈密顿圈为什么没有看一眼度数的判定5. 三堵规模墙暴力、状压、回溯6. NP 完全在这里露脸哈密顿相变7. 一张元图总结欧拉 vs 哈密顿8. 本讲检查清单9. 复现指南10. 下一讲预告1. 七桥问题图论的出生30 行代码重做1736 年欧拉解决了一个本地人吵了几十年的问题哥尼斯堡的 7 座桥能不能不重复地走完图 1左七桥建模为 4 顶点多重图度数 [5,3,3,3] 全是奇数。握手定理保证奇点个数为偶数第 1 讲刚跑过这里是 4 个——欧拉回路要求 0 个奇点通路要求恰 2 个都不满足无解。右加一座 B–C 桥历史上桥真的被拆改过度数变 [5,4,4,3]只剩 2 个奇点 → 欧拉通路存在Hierholzer 跑出的实际路径0→1→0→2→0→3→1→2→38 条边恰用一次。欧拉的判定规则用代码写就是三行defhas_euler_circuit(g):returng.connected_on_edges()andall(deg%20fordeging.degrees())defhas_euler_path(g):returng.connected_on_edges()andlen(g.euler_odd())in(0,2)注意度数条件只管奇偶连通是另一半前提——一个每个顶点度都是 2、但碎成两个圈的图照样没有欧拉回路。考试选择题最爱漏掉这个前提。2. 欧拉判定定理 × Hierholzer900 组对拍课本原话无向图有欧拉回路 ⟺ 连通且所有顶点度为偶数有欧拉通路非回路⟺ 连通且恰有两个奇度顶点。“充要条件四个字值得较真判定说是”能不能真构造出那条回路判定说否是不是真的构造不出来构造算法用 Hierholzer1733比欧拉还早defhierholzer(g,start0):it[deque(vs)forvsing.adj]# 每个顶点的剩余边指针used[False]*len(g.edges)stack[start];circuit[]whilestack:ustack[-1]whileit[u]andused[it[u][0][1]]:it[u].popleft()ifit[u]:# 还有未走的边压栈前进v,eidit[u].popleft()used[eid]True;stack.append(v)else:# 走投无路回溯并记录circuit.append(stack.pop())circuit.reverse()returncircuit图 2900 组对拍全部一致。三类图各 300 个全偶度图应判回路300/300 构造成功且每条边恰用一次圈上删一边恰 2 奇点应判通路300/300 通路从一奇点走到另一奇点一般随机图 300/300 判定与构造结论一致。判定构造这件事在欧拉图上是定理保证在实验里是 900 次兑现。充要条件不是背出来的是验出来的。2.1 环合并教科书插图的生成过程Hierholzer 的教科书叙述是找一个环在环上还有剩余边的点插入新环。这个环合并过程我们逐帧记录图 38 字图两环共点 0两帧完成。第 0 帧从 0 走出三角形 0-1-2-0蓝色下半环还是灰色第 1 帧发现 0 还有未用边从 0 走出 0-3-4-5-0红色插入——合并成完整欧拉回路。实现细节值得记第一版 walk一直走到无路可走结果一帧就合并完了8 字图恰好一步走全。改成**“回到出发点就停”**的教科书式 walk才产生真正的多帧环合并。可视化要忠实于算法叙述而不是忠实于能跑。3. 有向图欧拉入度 出度有向图的版本把度数为偶换成入度 出度有向图有欧拉回路 ⟺ 弱连通且每个顶点入度 出度。图 4左一个满足条件的 5 点有向图每点出入右200 组构造对拍全过。判定是的图Hierholzer 跑出的回路边数恰为 |E|1 且首尾闭合判定否的图如实拒绝。考试高频陷阱入度出度只是回路条件欧拉通路的有向版是恰一个顶点出−入1起点、恰一个入−出1终点、其余平衡。两套条件别混。4. 哈密顿圈为什么没有看一眼度数的判定换一个问题不重复地经过每个顶点再回到起点——这就是哈密顿圈。注意与欧拉的差别只有一字欧拉遍历边哈密顿遍历点。但这一字之差是 P 与 NP 的鸿沟。课本给的只有充分条件Dirac1952n≥3 且每个顶点度 ≥ n/2 → 有哈密顿圈Ore1960不相邻的任意两点度数和 ≥ n → 有哈密顿圈。图 5左星图 K₁,₅最小度 1——无哈密顿圈叶结点进出只能一次中圈图 C₆最小度 2 n/23——但哈密顿圈就是它自己右n12 随机图实测满足 Dirac 条件的 94 张全部找到圈94/94。两张反例图 94/94 的实测把充分不必要钉死条件满足必有条件不满足可能有也可能没有。那不满足但可能有的图怎么判只能搜——这就撞上了 NP 完全。5. 三堵规模墙暴力、状压、回溯同一批图先放一个哈密顿圈再随机加边保证有解三种经典算法看它们各自撞墙的位置图 6对数轴上的三堵墙。红暴力枚举 O(n!)——n11 已 621msn12 起分钟级蓝状压 DP O(2ⁿ·n²)——n20 才 29ms但内存吃 2ⁿ·n 个状态n25 起爆内存绿回溯剪枝——在有解且结构好的图上 n28 仅 7ms。回溯看起来最强别急——它快是因为有解且好找。图 7 会看到无解图面前回溯同样指数爆炸。三种算法的适用场景就是考试简答题的标准答案算法复杂度适用暴力排列O(n!·n)n≤10 的教学演示状压 DPO(2ⁿ·n²)n≤20 要精确解回溯剪枝最坏指数平均快判定型、有解图、竞赛常用6. NP 完全在这里露脸哈密顿相变第 1、2 讲我们看过连通性的相变c1 巨分量诞生。哈密顿性也有自己的阈值G(n,p) 几乎必然含哈密顿圈的临界概率是(ln n ln ln n)/n——比几乎必然连通的 ln n/n 略晚。图 7n24p 从 0.6× 到 1.4× 阈值0.181每档 25 个随机图。紫线含哈密顿圈的比例已判定样本0→1 干净切换灰柱回溯超时的样本数——阈值附近冲到 22/25。灰柱才是本讲最硬的信息最难判的样本恰好堆在阈值上。低于阈值的图大多一眼无解有孤立点、割点剪枝秒判高于阈值的图大多有解好找回溯秒出只有阈值附近有没有本身变成难题——回溯要搜到指数级才能确认无解于是超时。这就是 NP 完全的物理质感不是所有实例都难难的是临界带上的实例。密码学、求解器设计、竞赛题出题吃的都是这块地带。7. 一张元图总结欧拉 vs 哈密顿图 8同一类问题走遍所有…两种难度。欧拉遍历边度数局部条件 → 判定 Hierholzer 构造都是多项式哈密顿遍历点无漂亮充要条件 → 暴力/状压/回溯三堵墙 临界带超时。一句话带走遍历边是局部约束每个点进出配对遍历点是全局约束路径不能自交——局部性质可检验全局性质要搜索。这是图论算法难度分层的第一个原理。8. 本讲检查清单□ 七桥为什么无解4 个奇度顶点回路要 0 个、通路要恰 2 个 □ 欧拉判定的两个前提连通 度数条件只答度数丢分 □ 有向欧拉回路/通路条件回路入出通路起终点差 ±1其余平衡 □ Hierholzer 复杂度O(E)每条边进出栈各一次 □ Dirac/Ore 是什么条件的条件充分不必要C₆ 是最小反例 □ 三种哈密顿算法的墙各在哪n! 撞 n≈12、2ⁿ 撞 n≈25、回溯平均快但临界带超时 □ 随机图哈密顿阈值(ln n ln ln n)/n比连通阈值 ln n/n 略高9. 复现指南graph-course/ ├── course3.py # 七组实验七桥/对拍/分帧/有向/充分条件/规模墙/相变~420 行 ├── figs3.py # 8 张配图 ├── results/course3.json └── figures/python course3.py# → results/course3.json约 3 分钟含超时保护python figs3.py# → 8 张图正确性断言判定是 ⇔ 构造成功900200 组回路每条边恰用一次verify_circuit超时样本单列不混入无解——诚实对待算法判不动的样本是这一讲实验方法论的底线。10. 下一讲预告第 4 讲《最短路三件套》Dijkstra 为什么怕负权跑一个它悄悄出错的真实反例、Bellman-Ford 的 O(VE) 到底慢在哪、Floyd 的三重循环凭什么正确k 的含义用动态规划讲透外加三算法在同一批图上的规模横评。欧拉给了图论第一定理哈密顿给了图论第一个噩梦。认得清局部条件与全局搜索的边界图论就再没有神秘感。系列目录第 1 讲 基本概念与存储 · 第 2 讲 遍历与连通 · 第 3 讲 欧拉图与哈密顿图本篇· 第 4 讲 最短路三件套 · 第 5 讲 生成树与拓扑排序 · 第 6 讲 网络流与匹配