欧拉图判定
线性判断无向图或有向图是否存在欧拉回路或欧拉迹:无向图看奇度顶点与连通性,有向图看入度出度平衡与弱连通。时间 O(n + m),空间 O(n + m) · 标签 图论 / 欧拉图 / 欧拉回路 / 欧拉路径 / 判定
问题形式
给定无向图或有向图 ,判断是否存在欧拉回路或欧拉迹。这里只判定存在性,不要求输出具体路径;构造方法见 Hierholzer 算法。
无向图判定
设 的所有度非零顶点在同一个连通分量内。则:
- 有欧拉回路,当且仅当每个顶点的度都是偶数;
- 有欧拉迹,当且仅当恰有 个或 个奇度顶点。
奇度顶点数为 时,欧拉迹必须以这两个顶点为起点和终点;为 时,每条欧拉迹都是欧拉回路。孤立点不影响判定。
有向图判定
记 为出度, 为入度。若忽略方向后,所有 的顶点在同一个连通分量内,则:
- 有向欧拉回路存在,当且仅当每个顶点满足 ;
- 有向欧拉迹存在,当且仅当所有顶点满足 ,或者恰有一个顶点满足 、恰有一个顶点满足 ,其余顶点满足 。
后一种情形中,第一个顶点是起点,第二个是终点。
正确性
无向图的必要性:迹每经过一个顶点,就用掉两条与它关联的边;只有起点和终点可能被用掉奇数条,因此非端点的度为偶数,端点的度为奇数当且仅当起点与终点不同。
无向图的充分性:若所有度为偶数,取一条边不重复的极大迹。它的起点与终点必须相同,否则这两个端点的度为奇数,矛盾。若它尚未覆盖全部边,则剩余图中仍有非空边;由于原图连通,剩余边所在的非空分量与已有迹有公共顶点,从该顶点再取一条极大闭迹并拼接,重复直到覆盖全部边。若只有两个奇度顶点,先加一条连接它们的虚边化为欧拉回路,再删去虚边。
有向图的必要性:内部顶点每进入一次就要离开一次,因此入度等于出度;开放欧拉迹的起点多一条出边、终点多一条入边,其余顶点平衡。所有边都在同一条迹上,所以忽略方向后连通。
有向图的充分性:回路情形取一条有向极大迹。若它停在非起点顶点 ,则 的已用入边数比已用出边数多 ;但 已无未使用出边,且总入度等于总出度,矛盾,所以极大迹必回到起点。若未覆盖全部边,由弱连通性在相交顶点继续拼接闭迹。开放情形同样可以先加一条从终点到起点的虚边,化为有向欧拉回路后删去虚边。
判定流程
- 统计各顶点的度;有向图分别统计 和 ,并标记 的顶点。
- 从任意一个度非零顶点开始 BFS 或 DFS,检查是否到达所有度非零顶点。
- 无向图:若所有度为偶数,则有欧拉回路;若恰有两个奇度顶点,则有欧拉迹;否则没有。
- 有向图:若所有顶点满足 ,则有欧拉回路;若恰有一个顶点出度比入度大 、恰有一个顶点入度比出度大 ,且其余顶点平衡,则有欧拉迹;否则没有。
易错点
- 孤立点不参与连通性判断,但它的度仍要计入“所有度为偶数”的检查。
- 无向图有欧拉迹的条件是 个或 个奇度顶点;有 个及以上奇度顶点时不存在欧拉迹。
- 有向图只检查入度出度平衡还不够,忽略方向后还必须连通。
- 自环在无向图中贡献 度;在有向图中同时贡献 入度和 出度。
- 重边的每一条边都要单独计数,不能把同一对端点之间的多条边合并成一条。