欧拉图：从七桥问题到图论基础

QY8765

67人浏览 · 2026-08-12 12:50:54

QY8765 · 2026-08-12 12:50:54 发布

1. 什么是欧拉图？

欧拉图（Eulerian Graph）是图论中的一个重要概念，它得名于瑞士数学家莱昂哈德·欧拉（Leonhard Euler）。1736年，欧拉在解决著名的“柯尼斯堡七桥问题”时，开创了图论这一数学分支，并提出了欧拉路径和欧拉回路的概念。

简单来说，欧拉图是指包含欧拉回路（Eulerian Circuit）的图。欧拉回路是一条经过图中每条边恰好一次，并且最终回到起点的路径。如果图中存在一条经过每条边恰好一次但不要求回到起点的路径，则称为欧拉路径（Eulerian Path）。

2. 欧拉图的基本概念

2.1 图的定义

在讨论欧拉图之前，我们先回顾图的基本定义：

图（Graph）：由顶点（Vertex）和边（Edge）组成的集合，记作 G = (V, E)。
无向图（Undirected Graph）：边没有方向，表示顶点间的双向关系。
有向图（Directed Graph）：边有方向，表示从一个顶点指向另一个顶点。
度（Degree）：在无向图中，一个顶点的度是与该顶点相连的边的数量。

2.2 欧拉路径与欧拉回路

让我们正式定义这两个核心概念：

欧拉路径（Eulerian Path）：经过图中每条边恰好一次的路径。
欧拉回路（Eulerian Circuit）：经过图中每条边恰好一次，并且起点和终点相同的路径。

包含欧拉回路的图称为欧拉图，而包含欧拉路径但不包含欧拉回路的图称为半欧拉图（Semi-Eulerian Graph）。

3. 欧拉图的判定条件

3.1 无向图的判定

对于无向连通图：

欧拉回路存在条件：当且仅当图中所有顶点的度都是偶数。
欧拉路径存在条件：当且仅当图中恰好有两个顶点的度是奇数（这两个顶点分别是路径的起点和终点），其余顶点的度都是偶数。

3.2 有向图的判定

对于有向连通图：

欧拉回路存在条件：当且仅当每个顶点的入度等于出度。
欧拉路径存在条件：当且仅当存在一个顶点出度比入度大1（起点），一个顶点入度比出度大1（终点），其余顶点的入度等于出度。

4. 经典问题：柯尼斯堡七桥问题

柯尼斯堡七桥问题是欧拉图理论的起源。问题描述如下：

柯尼斯堡（现俄罗斯加里宁格勒）的普雷格尔河上有两个岛，岛与河岸之间有七座桥连接。问题是：能否从某地出发，恰好经过每座桥一次，最后回到起点？

欧拉将这个问题抽象为图论模型：

将陆地（两个岛和两个河岸）抽象为4个顶点
将七座桥抽象为7条边

通过分析发现，每个顶点的度都是奇数（3, 3, 3, 5），不满足欧拉回路的存在条件，因此证明了这样的走法不存在。

5. 寻找欧拉路径的算法

5.1 弗勒里算法（Fleury's Algorithm）

弗勒里算法是寻找欧拉路径的经典算法，基本思想如下：

def fleury_algorithm(graph, start_vertex):
    """
    使用弗勒里算法寻找欧拉路径
    """
    # 复制图，避免修改原图
    temp_graph = copy.deepcopy(graph)
    path = []
    
    def dfs(v):
        for u in list(temp_graph[v]):
            # 检查边(v, u)是否是桥
            temp_graph[v].remove(u)
            temp_graph[u].remove(v)
            
            if is_connected(temp_graph):
                dfs(u)
            else:
                # 如果是桥，恢复边并尝试其他边
                temp_graph[v].add(u)
                temp_graph[u].add(v)
                continue
            
            path.append((v, u))
    
    dfs(start_vertex)
    return path[::-1]  # 反转得到正确顺序

5.2 希拉霍尔泽算法（Hierholzer's Algorithm）

希拉霍尔泽算法更高效，时间复杂度为O(E)：

def hierholzer_algorithm(graph):
    """
    使用希拉霍尔泽算法寻找欧拉回路
    """
    # 检查图是否满足欧拉回路条件
    if not has_eulerian_circuit(graph):
        return None
    
    circuit = []
    stack = [0]  # 从任意顶点开始
    
    while stack:
        v = stack[-1]
        if graph[v]:  # 如果还有未访问的边
            u = graph[v].pop()
            graph[u].remove(v)  # 对于无向图
            stack.append(u)
        else:
            circuit.append(stack.pop())
    
    return circuit[::-1]  # 反转得到正确顺序

6. 欧拉图的应用

6.1 电路板布线

在印刷电路板（PCB）设计中，需要确保所有连接都能被一次性绘制而不重复。这可以建模为欧拉路径问题，确保绘图笔能不重复地走过所有连线。

6.2 DNA测序

在生物信息学中，DNA片段组装可以转化为寻找欧拉路径的问题。每个k-mer（长度为k的DNA序列）作为边，重叠部分作为顶点，欧拉路径对应完整的DNA序列。

6.3 邮递员问题

中国邮递员问题要求邮递员走过所有街道至少一次并回到邮局，且总路程最短。当所有街道只需要走一次时，就是欧拉回路问题。

7. 欧拉图与哈密顿图的区别

特性	欧拉图	哈密顿图
关注对象	边	顶点
路径要求	经过每条边恰好一次	经过每个顶点恰好一次
判定难度	有多项式时间算法	NP完全问题
经典问题	七桥问题	旅行商问题