欧拉迹是有限图中恰好经过每条边一次的遍历。顶点可以重复经过,但边不能重复经过。如果遍历最终回到起始顶点,就称为欧拉回路。这些概念以莱昂哈德·欧拉的名字命名,是图论中的基本概念,并应用于路线规划、网络巡检和序列组装等领域。欧拉迹是否存在,可以根据连通性和顶点的度数来判定;若存在,则可在线性时间内构造出来。
定义与术语
设 是一个有限图。迹是一个顶点与边交替出现的序列:
其中,每条边 都连接序列中紧邻它前后的两个顶点,且任何边都不重复出现。如果这条迹包含 中的所有边,即 ,就称其为欧拉迹。
在有向图中,每条边都必须沿指定方向经过。这一定义也适用于多重图,其中同一对顶点之间可以有多条边。这些边彼此不同,必须各经过一次。图中也允许有环,即连接某个顶点与其自身的边。
欧拉迹分为:
- 闭欧拉迹:,此时也称为欧拉回路。
- 开欧拉迹:。
“欧拉路径”(Eulerian path)这一说法很常见,但使用“迹”(trail)更准确:在标准图论术语中,路径不允许重复经过顶点,而欧拉遍历可以重复经过顶点。同样,有时也会用“欧拉圈”(Eulerian cycle)来指欧拉回路,尽管严格意义上的圈除了起点和终点重合外,不允许重复经过顶点。
具有欧拉回路的图通常称为欧拉图。具有开欧拉迹但没有欧拉回路的图,有时称为半欧拉图。不同文献的术语用法并不完全一致,因此应明确说明所讨论的遍历是否必须闭合。
无向图中的存在条件
顶点 的度(图论)记为 ,是与该顶点关联的边端点数。每个环对该顶点的度贡献为二。
对于至少有一条边的有限无向图,存在欧拉迹当且仅当:
- 所有度非零的顶点都属于同一个连通分支。
- 度为奇数的顶点恰有零个或两个。
这些条件也决定了可能的端点:
| 奇度顶点数 | 结论 |
|---|---|
| 零个 | 存在欧拉回路,可以从任意度非零的顶点出发。 |
| 恰好两个 | 存在开欧拉迹,其两个端点恰好就是这两个奇度顶点。 |
| 多于两个 | 不存在欧拉迹。 |
孤立顶点不影响能否用一条迹遍历所有边。因此,连通性条件针对的是由度非零的顶点构成的子图,而不一定是整个图。
对于没有边的图,需要采用关于空遍历的约定。通常允许在某个顶点处取长度为零的迹,并将其视为闭迹;对于没有顶点的图,则需要另作约定。
为什么奇度顶点决定端点
当一条迹在途中经过某个顶点时,进入该顶点的边与离开该顶点的边总是配对出现。因此,闭遍历在每个顶点处使用的关联边端点数都是偶数。
在开遍历中,起始顶点有一次离开没有与之配对的进入,终止顶点则有一次进入没有与之配对的离开。因此,这两个顶点的度为奇数,其余所有顶点的度均为偶数。
这就证明了条件的必要性。充分性可以通过构造闭迹并将它们拼接起来证明,希尔霍尔策算法采用的就是这种方法。如果有两个奇度顶点,可以临时在它们之间添加一条边,使所有顶点的度都变为偶数。随后构造欧拉回路,再从中删去添加的边,就得到所需的开欧拉迹。
握手定理
还表明,奇度顶点的个数总是偶数。
示例
考虑一个顶点为 的三角形,再添加一条从 连接到第四个顶点 的边。各顶点的度为:
其中一条欧拉迹是:
它从 出发,在 结束,这两个顶点正是图中的两个奇度顶点。重复经过 是允许的。
有向图中的存在条件
对于有向图,用 表示出度,用 表示入度。每个有向环对入度和出度各贡献一。
至少有一条边的有限有向图存在欧拉回路,当且仅当:
忽略边的方向后,所有与边关联的顶点彼此连通。
每个顶点的入度与出度相等:
在入度与出度相等的条件下,上述弱连通条件还意味着所有与边关联的顶点彼此强连通:从其中任意一个顶点出发,都可以沿有向路径到达其他任意一个顶点。
对于 ,从 到 的开欧拉迹存在,当且仅当忽略方向后的图满足同样的连通性条件,并且
而其他所有顶点的入度与出度均相等。
起始顶点多一次离开,终止顶点多一次进入。临时添加一条从 指向 的有向边,就可以将这种情况转化为欧拉回路的情况。
构造算法
希尔霍尔策算法
希尔霍尔策算法发表于1873年,通过拼接闭迹来构造欧拉回路:
- 从一个与边关联的顶点出发,沿尚未使用的边行进,直到回到起点。
- 如果仍有未使用的边,就在当前回路上选取一个与未使用边关联的顶点。
- 从该顶点出发,使用尚未使用的边构造另一条闭迹。
- 将新的闭迹插入现有回路。
- 重复以上步骤,直到所有边都已使用。
度数条件保证遍历不会在起点以外的顶点陷入无路可走的状态。连通性则保证,只要还有未使用的边,就能从某个已经到达的顶点继续访问这些边。
实际实现时可以使用栈和邻接表。算法沿未使用的边行进,并将经过的边移除;当当前顶点没有未使用的边时,将该顶点出栈并追加到输出列表中。将列表反转,即可得到遍历序列。
对于开欧拉迹,算法可以直接从所要求的端点出发。另一种方法是临时添加一条边,求出欧拉回路,再在这条边的位置将回路断开。
通过适当的边标识和邻接表管理方式,条件检查和遍历构造所需的时间均为
,这里使用的是大O记号。遍历序列中共出现 次顶点。
弗勒里算法
弗勒里算法采用另一条规则:除非别无选择,否则不要选择这样一条尚未使用的边——移除它会使剩余可用边之间不再连通。这样的边是相应剩余图中的桥。
这种方法直观易懂,但如果反复通过图搜索来判断桥,效率就会较低。忽略孤立顶点后,其直接实现的时间复杂度与边数的平方成正比。通常更倾向于使用希尔霍尔策算法,因为它不需要反复检测桥。
历史起源
欧拉遍历问题起源于柯尼斯堡七桥问题。这座城市的桥梁连接着四块陆地。问题是:能否找到一条步行路线,恰好经过每座桥一次?
欧拉于1736年发表的研究将地理细节抽象为一个网络:陆地变成顶点,桥梁变成边。四个顶点的度全都是奇数,因此既不存在开欧拉迹,也不存在欧拉回路。
这种抽象的重要意义在于,距离、角度以及各块陆地的具体形状都不决定答案,真正起作用的只有连接方式。这一问题被广泛视为图论的奠基性范例。
应用与相关问题
路线巡检
由街道、管道或其他连接构成的网络,可能需要对每条边进行检查或维护。如果网络满足欧拉条件,就可以不重复地遍历每条边。
如果不满足条件,就必须重复经过某些边。寻找一条覆盖所有边且总成本最低的闭游走,就是中国邮递员问题,也称路线巡检问题。在其标准无向形式中,通过复制选定路径上的边,使所有顶点的度都变成偶数,然后构造欧拉回路。
这与旅行商问题不同:后者关注的是访问指定地点,而不一定要覆盖每条边。
序列组装
在某些序列组装方法中,片段用德布鲁因图表示。顶点代表相互重叠的字符串,边则代表连接前缀与后缀的更长字符串。欧拉遍历可以为边所对应的片段确定顺序,使相邻片段的重叠部分保持一致。
这一原理用于某些脱氧核糖核酸序列组装方法。重复序列、观测缺失和测量误差可能引入歧义,也可能使观测所得的图无法满足理想的欧拉条件。因此,仅有欧拉遍历的存在,并不能确定唯一的生物学重建结果。
与哈密顿路径的比较
欧拉迹恰好经过每条边一次。哈密顿路径恰好经过每个顶点一次。这两个条件互不蕴含。
这一区别在计算上也很重要。欧拉迹的存在性可以在线性时间内判定,也可以在线性时间内完成构造。而判定任意图中是否存在哈密顿路径是一个NP完全问题。不能仅仅因为两类问题都可以被通俗地描述为“寻找一条穿过网络的路线”,就认为欧拉方法可以直接解决顶点访问问题。