欧拉路径与欧拉回路：图论中的“一笔画”问题

欧拉路径与欧拉回路：图论中的“一笔画”问题

欧拉路径和欧拉回路是图论中的重要概念，它们描述了图中是否存在一条可以“一笔画”的路径。本文将详细介绍欧拉路径、欧拉回路、欧拉图和半欧拉图的概念及其相关定理，并讲解如何找到欧拉路径的算法。

一、欧拉路和欧拉回路

• 欧拉路径是指从图中一个点开始到图中一个点结束的路径，并且图中每条边通过的且只通过一次（顶点可以多次）。一个图可以有多条欧拉路径。

• 欧拉回路是欧拉回路是指起点和终点相同的欧拉路。

我们定义奇点是指跟这个点相连的边的数目有奇数个的点。对于一笔画的图，有以下两个定理：

定理1：存在欧拉路的条件：图是连通的，有且只有2个奇点；

定理2：存在欧拉回路的条件：图是连通的，有0个奇点。

二、欧拉图和半欧拉图

具有欧拉回路的图叫欧拉图，不具有欧拉回路的图叫半欧拉图。

这两个定理是显而易见的，既然每条边都要经过一次，那么对于欧拉路，除了起点和终点外，每个点如果要进入一次，显然一定要出去一次，显然是偶点。对于欧拉回路，每个点进入和出去的次数一定是相等的，显然没有奇点。

欧拉图：对于无向图来说，所有顶点的度都是偶数；对于有向图来说，所有顶点的入度和出度相等。

半欧拉图：对于无向图来说，有且仅有两个顶点的度为奇数；对于有向图来说，有且仅有一个顶点入度-出度=1，另有且仅有一个顶点出度-入度=1。

三、如何找到欧拉路

1、先判断是有向图还是无向图；

• 无向图：

• 欧拉图：所有顶点的度都是偶数

• 半欧拉图：有且仅有两个顶点的度为奇数

• 有向图

• 欧拉图：所有顶点的入度和出度相等

• 半欧拉图：有且仅有一个顶点入度-出度=1，另有且仅有一个顶点出度-入度=1

2、求欧拉路的算法使用深度优先遍历，每经过一条边，就把这条边设置visited。

• 如下图：首先是无向图，然后统计图的结点的度都是偶数，那么就是欧拉图；
• 找到一个奇数条边的点作为起点，如果没有找到就随便找一个点作为起点；
• 针对边进行DFS递归搜索，访问所有未访问过的边；

3、针对边的深度优先遍历过程如下：

• A点为起点，AB这条边入栈
  Stack-1
  ，也就是：A入栈、B入栈；（AB边被访问过visited）
• B点为起点，BC这条边入栈，也就是：C入栈；（BC边visited）
• C点为起点，CA这条边入栈，也就是：A入栈；（CA边visited）
• A点为起点，所有的边都被访问过，那么A点出栈，进入
  Stack-2
• 回溯到C点，CE这条边入栈，也就是：E入栈；（CE边visited）
• E点为起点，EB这条边入栈，也就是：B入栈；（EB边visited）
• B点为起点，BD这条边入栈，也就是：D入栈；（BD边visited）
• D点为起点，DE这条边入栈，也就是：E入栈；（DE边visited）
• E点为起点，EG这条边入栈，也就是：G入栈；（EG边visited）
• G点为起点，GF这条边入栈，也就是：F入栈；（GF边visited）
• F点为起点，FC这条边入栈，也就是：C入栈；（FC边visited）
• C点为起点，所以边都被访问过，那么C点出栈，进入
  Stack-2
• 依次是F、G、E、D、B、E、C、B、A出栈
  Stack-1
  ，入栈
  Stack-2
• Stack-2中的元素是（栈底到栈顶）：A、C、F、G、E、D、B、E、C、B、A
• Stack-2出栈：ABCEBDEGFCA
  ABCEBDEGFCA 就是欧拉回路，尝试一下，可以一笔画完。

四、练习题

欧拉图G是指可以构成一个闭回路的图，且图G的每一条边恰好在这个闭回路上出现一次(即一笔画)。以下各个描述中，不一定是欧拉图的是( )

A. 图G中没有度为奇数的顶点

B. 包括欧拉环游的图（欧拉环游图是指通过图中每边恰好一次的闭路径）

C. 包括欧拉闭迹的图（欧拉迹是指通过图中每边恰好一次的路径）

D. 存在一条回路，通过每个顶点恰好一次

参考答案 D

参考欧拉图的定义。