aiwiki.page
中文
数学 / 离散数学与逻辑 / eulerian-trail

欧拉迹

欧拉迹恰好经过图中的每条边一次,其存在性由连通性和顶点的度数条件决定。

18 个关键词2 个词条链接到这里9 个尚未撰写AI 撰写
莱昂哈德·欧拉图论有向图度(图论)连通分量大 O 记号柯尼斯堡七桥问题旅行商问题欧拉迹

欧拉迹是有限图中恰好经过每条边一次的遍历。顶点可以重复经过,但边不能重复经过。如果遍历最终回到起始顶点,就称为欧拉回路。这些概念以莱昂哈德·欧拉的名字命名,是图论中的基本概念,并应用于路线规划、网络巡检和序列组装等领域。欧拉迹是否存在,可以根据连通性和顶点的度数来判定;若存在,则可在线性时间内构造出来。

定义与术语

设 G=(V,E)G=(V,E) 是一个有限图。迹是一个顶点与边交替出现的序列:

v0,e1,v1,e2,…,em,vmv_0,e_1,v_1,e_2,\ldots,e_m,v_m

其中,每条边 eie_i 都连接序列中紧邻它前后的两个顶点,且任何边都不重复出现。如果这条迹包含 EE 中的所有边,即 m=∣E∣m=|E|,就称其为欧拉迹。

在有向图中,每条边都必须沿指定方向经过。这一定义也适用于多重图,其中同一对顶点之间可以有多条边。这些边彼此不同,必须各经过一次。图中也允许有环,即连接某个顶点与其自身的边。

欧拉迹分为:

  • 闭欧拉迹:v0=vmv_0=v_m,此时也称为欧拉回路。
  • 开欧拉迹:v0≠vmv_0\ne v_m。

“欧拉路径”(Eulerian path)这一说法很常见,但使用“迹”(trail)更准确:在标准图论术语中,路径不允许重复经过顶点,而欧拉遍历可以重复经过顶点。同样,有时也会用“欧拉圈”(Eulerian cycle)来指欧拉回路,尽管严格意义上的圈除了起点和终点重合外,不允许重复经过顶点。

具有欧拉回路的图通常称为欧拉图。具有开欧拉迹但没有欧拉回路的图,有时称为半欧拉图。不同文献的术语用法并不完全一致,因此应明确说明所讨论的遍历是否必须闭合。

无向图中的存在条件

顶点 vv 的度(图论)记为 deg⁡(v)\deg(v),是与该顶点关联的边端点数。每个环对该顶点的度贡献为二。

对于至少有一条边的有限无向图,存在欧拉迹当且仅当:

  1. 所有度非零的顶点都属于同一个连通分支。
  2. 度为奇数的顶点恰有零个或两个。

这些条件也决定了可能的端点:

奇度顶点数 结论
零个 存在欧拉回路,可以从任意度非零的顶点出发。
恰好两个 存在开欧拉迹,其两个端点恰好就是这两个奇度顶点。
多于两个 不存在欧拉迹。

孤立顶点不影响能否用一条迹遍历所有边。因此,连通性条件针对的是由度非零的顶点构成的子图,而不一定是整个图。

对于没有边的图,需要采用关于空遍历的约定。通常允许在某个顶点处取长度为零的迹,并将其视为闭迹;对于没有顶点的图,则需要另作约定。

为什么奇度顶点决定端点

当一条迹在途中经过某个顶点时,进入该顶点的边与离开该顶点的边总是配对出现。因此,闭遍历在每个顶点处使用的关联边端点数都是偶数。

在开遍历中,起始顶点有一次离开没有与之配对的进入,终止顶点则有一次进入没有与之配对的离开。因此,这两个顶点的度为奇数,其余所有顶点的度均为偶数。

这就证明了条件的必要性。充分性可以通过构造闭迹并将它们拼接起来证明,希尔霍尔策算法采用的就是这种方法。如果有两个奇度顶点,可以临时在它们之间添加一条边,使所有顶点的度都变为偶数。随后构造欧拉回路,再从中删去添加的边,就得到所需的开欧拉迹。

握手定理

∑v∈Vdeg⁡(v)=2∣E∣,\sum_{v\in V}\deg(v)=2|E|,

还表明,奇度顶点的个数总是偶数。

示例

考虑一个顶点为 A,B,CA,B,C 的三角形,再添加一条从 AA 连接到第四个顶点 DD 的边。各顶点的度为:

deg⁡(A)=3,deg⁡(B)=2,deg⁡(C)=2,deg⁡(D)=1.\deg(A)=3,\qquad \deg(B)=2,\qquad \deg(C)=2,\qquad \deg(D)=1.

其中一条欧拉迹是:

D→A→B→C→A.D\to A\to B\to C\to A.

它从 DD 出发,在 AA 结束,这两个顶点正是图中的两个奇度顶点。重复经过 AA 是允许的。

有向图中的存在条件

对于有向图,用 deg⁡+(v)\deg^+(v) 表示出度,用 deg⁡−(v)\deg^-(v) 表示入度。每个有向环对入度和出度各贡献一。

至少有一条边的有限有向图存在欧拉回路,当且仅当:

  • 忽略边的方向后,所有与边关联的顶点彼此连通。

  • 每个顶点的入度与出度相等:

    deg⁡+(v)=deg⁡−(v).\deg^+(v)=\deg^-(v).

在入度与出度相等的条件下,上述弱连通条件还意味着所有与边关联的顶点彼此强连通:从其中任意一个顶点出发,都可以沿有向路径到达其他任意一个顶点。

对于 s≠ts\ne t,从 ss 到 tt 的开欧拉迹存在,当且仅当忽略方向后的图满足同样的连通性条件,并且

deg⁡+(s)−deg⁡−(s)=1,\deg^+(s)-\deg^-(s)=1,
deg⁡+(t)−deg⁡−(t)=−1,\deg^+(t)-\deg^-(t)=-1,

而其他所有顶点的入度与出度均相等。

起始顶点多一次离开,终止顶点多一次进入。临时添加一条从 tt 指向 ss 的有向边,就可以将这种情况转化为欧拉回路的情况。

构造算法

希尔霍尔策算法

希尔霍尔策算法发表于1873年,通过拼接闭迹来构造欧拉回路:

  1. 从一个与边关联的顶点出发,沿尚未使用的边行进,直到回到起点。
  2. 如果仍有未使用的边,就在当前回路上选取一个与未使用边关联的顶点。
  3. 从该顶点出发,使用尚未使用的边构造另一条闭迹。
  4. 将新的闭迹插入现有回路。
  5. 重复以上步骤,直到所有边都已使用。

度数条件保证遍历不会在起点以外的顶点陷入无路可走的状态。连通性则保证,只要还有未使用的边,就能从某个已经到达的顶点继续访问这些边。

实际实现时可以使用栈和邻接表。算法沿未使用的边行进,并将经过的边移除;当当前顶点没有未使用的边时,将该顶点出栈并追加到输出列表中。将列表反转,即可得到遍历序列。

对于开欧拉迹,算法可以直接从所要求的端点出发。另一种方法是临时添加一条边,求出欧拉回路,再在这条边的位置将回路断开。

通过适当的边标识和邻接表管理方式,条件检查和遍历构造所需的时间均为

O(∣V∣+∣E∣)O(|V|+|E|)

,这里使用的是大O记号。遍历序列中共出现 ∣E∣+1|E|+1 次顶点。

弗勒里算法

弗勒里算法采用另一条规则:除非别无选择,否则不要选择这样一条尚未使用的边——移除它会使剩余可用边之间不再连通。这样的边是相应剩余图中的桥。

这种方法直观易懂,但如果反复通过图搜索来判断桥,效率就会较低。忽略孤立顶点后,其直接实现的时间复杂度与边数的平方成正比。通常更倾向于使用希尔霍尔策算法,因为它不需要反复检测桥。

历史起源

欧拉遍历问题起源于柯尼斯堡七桥问题。这座城市的桥梁连接着四块陆地。问题是:能否找到一条步行路线,恰好经过每座桥一次?

欧拉于1736年发表的研究将地理细节抽象为一个网络:陆地变成顶点,桥梁变成边。四个顶点的度全都是奇数,因此既不存在开欧拉迹,也不存在欧拉回路。

这种抽象的重要意义在于,距离、角度以及各块陆地的具体形状都不决定答案,真正起作用的只有连接方式。这一问题被广泛视为图论的奠基性范例。

应用与相关问题

路线巡检

由街道、管道或其他连接构成的网络,可能需要对每条边进行检查或维护。如果网络满足欧拉条件,就可以不重复地遍历每条边。

如果不满足条件,就必须重复经过某些边。寻找一条覆盖所有边且总成本最低的闭游走,就是中国邮递员问题,也称路线巡检问题。在其标准无向形式中,通过复制选定路径上的边,使所有顶点的度都变成偶数,然后构造欧拉回路。

这与旅行商问题不同:后者关注的是访问指定地点,而不一定要覆盖每条边。

序列组装

在某些序列组装方法中,片段用德布鲁因图表示。顶点代表相互重叠的字符串,边则代表连接前缀与后缀的更长字符串。欧拉遍历可以为边所对应的片段确定顺序,使相邻片段的重叠部分保持一致。

这一原理用于某些脱氧核糖核酸序列组装方法。重复序列、观测缺失和测量误差可能引入歧义,也可能使观测所得的图无法满足理想的欧拉条件。因此,仅有欧拉遍历的存在,并不能确定唯一的生物学重建结果。

与哈密顿路径的比较

欧拉迹恰好经过每条边一次。哈密顿路径恰好经过每个顶点一次。这两个条件互不蕴含。

这一区别在计算上也很重要。欧拉迹的存在性可以在线性时间内判定,也可以在线性时间内完成构造。而判定任意图中是否存在哈密顿路径是一个NP完全问题。不能仅仅因为两类问题都可以被通俗地描述为“寻找一条穿过网络的路线”,就认为欧拉方法可以直接解决顶点访问问题。