欧拉图
经过每条边恰好一次的图结构;无向图由奇度顶点个数判定,有向图还需入度与出度平衡且弱连通。标签 图论 / 欧拉图 / 欧拉回路 / 欧拉路径
定义
设 是 无向图。若一条迹经过 中每条边恰好一次,则称它为欧拉迹;起点与终点相同的欧拉迹称为欧拉回路。存在欧拉回路的图称为欧拉图。
迹指边不重复的连续边序列,顶点可以重复。重边和自环不影响定义;自环在度数中贡献 。
只有欧拉迹、没有欧拉回路的图有时称为半欧拉图。
基本性质
- 欧拉图的所有边都属于同一个连通分量;孤立点可以存在。
- 欧拉回路的边集可以分解为若干条边不交的简单环。
- 欧拉回路的起点可以是任意一个度非零顶点;从不同顶点出发得到不同的边序列。
- 欧拉回路不唯一;即使起点固定,也可能有多条。
与哈密顿路径的区别
欧拉迹要求每条边恰好一次,判定只依赖度数和连通性;哈密顿路径要求每个顶点恰好一次,一般图的判定是 NP 完全的。两者的约束对象不同,不能把“经过所有点”与“经过所有边”混用。
常见误解
- 认为图必须整体连通才有欧拉回路:孤立点可以存在,只需所有度非零顶点在同一连通分量内。
- 认为有欧拉迹就必须所有顶点度数为偶数:开放欧拉迹恰有两个奇度端点。
- 认为有向图入度等于出度就有欧拉回路:忽略方向后还必须连通。
- 认为欧拉图不能有割点:两个环共享一个顶点仍是欧拉图,该共享点是割点。
- 认为欧拉回路唯一:起点和走法都可能不同。