探寻无向图欧拉回路：发现图论封闭路径的奥秘

# 1. 无向图欧拉回路的定义和性质

**1.1 定义**

欧拉回路是指无向图中一条遍历所有顶点且仅遍历一次的路径。

**1.2 性质**

* **存在性：**欧拉回路存在当且仅当图是连通的且每个顶点的度数均为偶数。
* **唯一性：**欧拉回路不存在唯一性，即同一张图可能存在多条欧拉回路。
* **长度：**欧拉回路的长度等于图中顶点的个数。

# 2. 无向图欧拉回路的判定方法

### 2.1 欧拉定理

**定理陈述：**

一个无向连通图存在欧拉回路当且仅当它满足以下条件：

- 图中所有顶点的度数均为偶数。

**证明：**

* **必要性：**

如果图中存在欧拉回路，则每个顶点都必须被访问偶数次，因为欧拉回路是一条不重复经过任何边或顶点的闭合路径。因此，每个顶点的度数必须为偶数。

* **充分性：**

如果图中所有顶点的度数均为偶数，则可以构造一个欧拉回路。从任意一个顶点出发，沿着任意一条边前进，然后沿着与当前顶点相连的另一条边返回。继续重复此过程，直到访问所有边。由于所有顶点的度数均为偶数，因此可以保证在访问完所有边后回到出发点，形成一个欧拉回路。

### 2.2 弗莱里定理

**定理陈述：**

一个无向连通图存在欧拉回路当且仅当它满足以下条件：

- 图中存在一个奇数度顶点，其他所有顶点的度数均为偶数。

**证明：**

* **必要性：**

如果图中存在欧拉回路，则必须存在一个奇数度顶点，因为欧拉回路是一条不重复经过任何边或顶点的闭合路径。

* **充分性：**

如果图中存在一个奇数度顶点，其他所有顶点的度数均为偶数，则可以构造一个欧拉回路。从奇数度顶点出发，沿着任意一条边前进，然后沿着与当前顶点相连的另一条边返回。继续重复此过程，直到访问所有边。由于所有偶数度顶点都可以被偶数次访问，因此可以保证在访问完所有边后回到奇数度顶点，形成一个欧拉回路。

### 2.3 赫罗图定理

**定理陈述：**

一个无向连通图存在欧拉回路当且仅当它满足以下条件：

- 图中不存在奇数度顶点。

**证明：**

* **必要性：**

如果图中存在欧拉回路，则每个顶点都必须被访问偶数次，因为欧拉回路是一条不重复经过任何边或顶点的闭合路径。因此，图中不能存在奇数度顶点。

* **充分性：**

如果图中不存在奇数度顶点，则可以构造一个欧拉回路。从任意一个顶点出发，沿着任意一条边前进，然后沿着与当前顶点相连的另一条边返回。继续重复此过程，直到访问所有边。由于所有顶点的度数均为偶数，因此可以保证在访问完所有边后回到出发点，形成一个欧拉回路。

**代码示例：**

def is_eulerian(graph):
  """判断一个无向连通图是否存在欧拉回路。

  参数：
    graph: 一个无向连通图，用邻接表表示。

  返回：
    True 如果图存在欧拉回路，否则返回 False。
  """

  # 检查图是否连通
  if not is_connected(graph):
    return False

  # 计算每个顶点的度数
  degrees = [0] * len(graph)
  for vertex in graph:
    for neighbor in graph[vertex]:
      degrees[vertex] += 1

  # 检查欧拉回路存在的条件
  if all(degree % 2 == 0 for degree in degrees):
    return True
  elif degrees.count(1) == 2:
    return True
  else:
    return False

**代码逻辑分析：**

* `is_connected`函数检查图是否连通，如果图不连通，则不可能存在欧拉回路。
* `degrees`列表存储每个顶点的度数。
* 循环遍历图中的所有顶点，并计算每个顶点的度数。
* 检查欧拉回路存在的条件：
* 如果所有顶点的度数均为偶数，则存在欧拉回路。
* 如果存在两个奇数度顶点，则存在欧拉回路。
* 否则，不存在欧拉回路。

# 3.1 弗莱里算法

弗莱里算法是一种贪心算法，用于构造无向图的欧拉回路。该算法从图中的任意一个顶点出发，依次选择可以到达的边，直到遍历完所有边。

#### 算法步骤

1. 选择图中的任意一个顶点作为起点。
2. 从起点出发，选择一条未被遍历过的边，并沿着该边移动到另一个顶点。
3. 重复步骤 2，直到遍历完所有边。
4. 如果当前顶点与起点相同，则算法结束，否则返回步骤 2。

#### 代码实现

def fleury(graph):
  """
  弗莱里算法构造无向图的欧拉回路。

  参数：
    graph: 无向图，用邻接表表示。

  返回：
    欧拉回路，如果存在，否则返回 None。
  """

  # 初始化欧拉回路
  euler_path = []

  # 栈，用于存储当前路径
  stack = [graph[0]]

  # 遍历所有边
  while stack:
    # 获取栈顶元素
    current_vertex = stack[-1]