欧拉图基础
一句话总结
「一笔画」游戏的本质是寻找欧拉路径/欧拉回路，可以通过节点的度数判断是否存在欧拉路径/欧拉回路。
核心内容
一笔画游戏与欧拉图
一笔画游戏规则：
- 一笔连接所有的点和边
- 点可以重复经过，但每条边必须恰好经过一次，不能重复
判断是否存在欧拉路径/回路的方法：
- 欧拉回路（回到起点）：所有节点的度数都是偶数 → 可以从任何节点开始，一定能完成并回到起点
- 欧拉路径（不回到起点）：只有两个节点的度数为奇数 → 必须从这两个奇数度节点中的任意一个开始
- 无法一笔画：不满足上述两种情况
七桥问题
欧拉图的概念源于 18 世纪著名的哥尼斯堡七桥问题：
- 哥尼斯堡（现加里宁格勒）被河流分为南北两岸，河中有东西两个小岛，共七座桥连接各区域
- 问题：能否从任意区域出发，经过每座桥恰好一次，最后回到起点？
图论抽象：
- 每个区域 → 一个节点
- 每座桥 → 一条边
- 问题转化为：是否存在一条路径，经过图中每条边恰好一次，且最终回到起点
结论：欧拉证明七桥问题无解。
术语定义
| 术语 | 定义 |
|---|---|
| 欧拉路径 | 经过图中每条边恰好一次的路径（起点和终点可以不同） |
| 欧拉回路 | 经过图中每条边恰好一次且回到起点的回路（起点=终点） |
| 欧拉图 | 包含欧拉回路的图 |
| 度数 | 与节点相连的边的数量 |
Hierholzer 算法
- 用于计算欧拉路径/欧拉回路的经典算法
- 是 DFS 算法的拓展
- 本文作为基础章节未详细讲解代码实现，具体实现将在数据结构章节的图论部分讲解
应用场景
欧拉图在现代计算机科学中的应用：
- 路径规划
- 电路设计
- 其他需要"一笔画"特性的场景