外观
Euler图
约 637 字大约 2 分钟
一、Euler轨迹（欧拉路径）
定义
Euler轨迹是图中经过每条边恰好一次的轨迹（允许重复经过顶点，但不重复经过边）。
存在条件
- 无向图：当且仅当图是连通的，且恰好有两个奇度数顶点（其余顶点度数均为偶数）。
- 有向图：当且仅当图是强连通的，且恰有一个顶点入度=出度+1（起点），一个顶点入度=出度-1（终点），其余顶点入度=出度。
二、Euler回路（欧拉回路）
定义
Euler回路是图中经过每条边恰好一次且起点与终点重合的闭合轨迹。
存在条件
- 无向图：当且仅当图是连通的，且所有顶点度数均为偶数。
- 有向图：当且仅当图是强连通的，且每个顶点的入度=出度。
三、Euler图
定义
- Euler图：包含至少一条Euler回路的图。
- 半Euler图：无Euler回路但存在Euler轨迹的图。
类型对比
| 类型 | 无向图条件 | 有向图条件 |
|---|---|---|
| Euler图 | 连通，全偶数度 | 强连通，入度=出度 |
| 半Euler图 | 连通，恰好2个奇度顶点 | 强连通，1顶点入度=出度+1，1顶点入度=出度-1 |
四、Euler定理（Hierholzer定理）
内容
若图是Euler图，则可以通过以下步骤构造Euler回路：
- 选择起点：任选一个顶点作为起点（若为半Euler图，则选奇度顶点）。
- 遍历边：沿未访问的边走，直到无法继续（回到起点）。
- 回溯补环：若存在未访问边，从路径中某个顶点出发构造子环，合并到主路径。
五、例题
例题1：判断Euler图
题目：判断下图是否为Euler图或半Euler图，并说明理由。
A ——— B
| \ / |
| C |
| / \ |
D ——— E解：
- 顶点度数：A(3), B(3), C(4), D(3), E(3)
- 结论：非Euler图（存在4个奇度顶点），也非半Euler图（奇度顶点数不为2）。
例题2：构造Euler回路
题目：在以下图中构造Euler回路：
1 --> 2
↑ ↓
4 <-- 3解：
- 条件验证：每个顶点入度=出度=1，满足Euler图条件。
- 构造路径：1→2→3→4→1。
例题3：七桥问题
题目：哥尼斯堡七桥问题能否找到Euler轨迹？
解：
- 抽象模型：四个陆地顶点（度数分别为3, 3, 3, 3）；
- 结论：不存在Euler轨迹（奇度顶点数量为4，超过2个）。
更新日志
2025/3/16 17:14
查看所有更新日志
8739a-update于
版权所有
版权归属：NateHHX