正文之前
关于欧拉回路，在图论中有一个著名的问题，叫做柯尼斯堡七桥问题(Königsberg Bridge Problem)
本文根据此问题来介绍:
- 欧拉回路(Euler Cycle)
- 欧拉路径(Euler Path)
正文
问题简介：
这个问题是基于一个现实生活中的事例：当时东普鲁士科尼斯堡（今日俄罗斯加里宁格勒）市区跨普列戈利亚河两岸，河中心有两个小岛。小岛与河的两岸有七条桥连接。在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？ ——WikipediaWikipedia
简化问题
我们先将上图中的七桥简化为如下所示：
第一眼看见，比划一下，就知道，在所有桥都只能走一遍的前提下，不能把这个地方所有的桥都走遍。
也就是说，如果遍历这个图，必须要重复经过某些边。
开始证明
欧拉在1735年提出，并没有方法能圆满解决这个问题，他更在第二年发表在论文《柯尼斯堡的七桥》中，证明符合条件的走法并不存在，也顺带提出和解决了一笔画问题。 ——Wikipedia
为了纪念欧拉，在一个图G中包含G的所有结点和边的回路称为欧拉回路,包含G的所有结点和边的路径称为欧拉路径
也就是说，如果欧拉路径闭合，就成了欧拉回路
注意回路的概念：从vi到vi的、长度非0的、不存在重复边的路径
所以上文所说的科尼斯堡七桥并不是欧拉回路。
存在欧拉回路（无向图）
前提条件
在图G中存在欧拉回路的前提条件为：
- 连通图
概念声明
关于一个图中是否存在欧拉回路，需要先说明两个概念：
- 奇结点（奇顶点）：连接该结点的边的数量为奇数
- 偶结点（偶顶点）：连接该结点的边的数量为偶数
证明（欧拉回路）
由于欧拉回路的性质：只能经过每条边一次，所以，对于每一个结点，至少需要有 2n 条边连接该结点（n = 0,1,2,...n），n = 0时，G中只含有一个结点v，则称路径(v)是G的欧拉回路。
也就是说，图G中存在欧拉回路的充要条件是G中每个结点都是偶结点。
设图G存在欧拉回路，则回路的起点和终点是同一结点，含有一条出边和一条入边，所以该结点为偶结点，以此类推，每个结点都连接有2n(n = 0,1,2,...n)
条边。
证明（欧拉路径）
图G中存在欧拉路径的充要条件和G中存在欧拉回路的充要条件有些相似：
- 图G中奇结点的个数为0或2
若奇结点的个数为0，则图G中存在欧拉回路，欧拉回路也是欧拉路径的一种。
若奇结点的个数为2，如上图中的欧拉路径，就存在两个奇结点，为欧拉路径，接下来证明这一点：
将两个奇结点相连，可知这是欧拉回路 (v1,v2,v3,v4,v5,v6,v3,v1)
将新增的边删去后，可知这是欧拉路径
欧拉路径(v1,v2,v3,v4,v5,v6,v3),起点和终点分别是两个奇结点
关于欧拉回路和欧拉路径的介绍就到此了，谢谢大家！
