一、Euler轨迹（欧拉路径）

定义

Euler轨迹是图中经过每条边恰好一次的轨迹（允许重复经过顶点，但不重复经过边）。

存在条件

• 无向图：当且仅当图是连通的，且恰好有两个奇度数顶点（其余顶点度数均为偶数）。
• 有向图：当且仅当图是强连通的，且恰有一个顶点入度=出度+1（起点），一个顶点入度=出度-1（终点），其余顶点入度=出度。

二、Euler回路（欧拉回路）

定义

Euler回路是图中经过每条边恰好一次且起点与终点重合的闭合轨迹。

存在条件

• 无向图：当且仅当图是连通的，且所有顶点度数均为偶数。
• 有向图：当且仅当图是强连通的，且每个顶点的入度=出度。

三、Euler图

定义

• Euler图：包含至少一条Euler回路的图。
• 半Euler图：无Euler回路但存在Euler轨迹的图。

类型对比

类型	无向图条件	有向图条件
Euler图	连通，全偶数度	强连通，入度=出度
半Euler图	连通，恰好2个奇度顶点	强连通，1顶点入度=出度+1，1顶点入度=出度-1

四、Euler定理（Hierholzer定理）

内容

若图是Euler图，则可以通过以下步骤构造Euler回路：

1. 选择起点：任选一个顶点作为起点（若为半Euler图，则选奇度顶点）。
2. 遍历边：沿未访问的边走，直到无法继续（回到起点）。
3. 回溯补环：若存在未访问边，从路径中某个顶点出发构造子环，合并到主路径。

五、例题

例题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个）。

版权所有

版权归属：NateHHX

许可证：署名 4.0 国际 (CC-BY-4.0)