路径与回路
欧拉回路要求经过每条边一次（欧拉定理给出充要条件），哈密顿圈要求经过每个顶点一次（NPC 问题），旅行商问题是其带权版本。
所属主题：图论 ↗阅读路径
参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。
01定义
欧拉回路要求不重复地走完每条边（欧拉定理：恰当所有顶点度数为偶），哈密顿圈要求不重复地访问每个顶点（判定是 NP 完全问题）——一字之差，难度天壤之别。旅行商问题是其带权优化版。
02核心要点
01
欧拉定理
连通图存在欧拉回路当且仅当所有顶点度数为偶——柯尼斯堡七桥（4 个奇度顶点）因此无解；Fleury 与 Hierholzer 算法构造回路。
02
哈密顿圈
判定「是否每顶点恰访一次的圈」是 NP 完全问题，无已知简洁判据；狄拉克定理（ 则存在）给出充分条件。
03
旅行商问题
TSP：求访问所有城市并返回的最短回路。精确算法指数级，Christofides 1.5 倍近似与 LKH 启发式支撑着物流实践。
03关键公式
04历史沿革
欧拉 1736 年证明七桥问题无解，被公认为图论第一篇论文；哈密顿 1856 年发明「周游世界」棋推广哈密顿圈；TSP 自 1930 年代成为优化标杆。
05应用与延伸
快递路径规划、电路板布线、DNA 测序拼接（de Bruijn 图）、卫星对地观测排程——「遍历」问题的理论原点。
06交互演示
欧拉回路：七桥问题与一笔画无桥时 4 个奇度节点 → 不能一笔画；加桥后奇度变 2