柯尼斯堡七桥问题的核心所在——欧拉通路和欧拉回路的区别

每次讲解与图论或复杂网络相关的课程时，老师们不得不提到的一个著名例子就是“柯尼斯堡七桥问题”。 这个故事的主角是欧拉。 他开创性地将许多问题抽象为图的拓扑结构，并通过研究图的特性解决了许多问题，其中包括“一笔”问题，这是七桥问题的核心。 位置——即一个人怎样才能走过下图中的七座桥而不重复呢？

图1| 柯尼斯堡七桥问题[1]

为了解决这个问题，欧拉仔细观察发现一笔画问题的核心在于每个中间顶点都有其起点和终点（即指向该节点的边，和指向该节点的边）。 那么当出现奇异点时（某个点的链接数为奇数，称为奇异点），就需要仔细判断它在图中的位置。 如果它位于图表的中间，则必须反复重复。 笔画已完成。 欧拉用严格的数学证明给出了一笔画的充分必要条件：奇点的数量要么是0，要么是2。

2. 定义

为了纪念欧拉的发现，图论将连通图G中每一条边经过且仅一次的路径定义为欧拉路径。 而如果欧拉路径中存在一些环，则称为欧拉环。 具有欧拉回路的图被定义为欧拉图。 具有欧拉路径但没有欧拉回路的图称为半欧拉图[2]。

图2| 欧拉路径和欧拉电路之间的区别[来自]

图3 | 非欧拉图、半欧拉图和欧拉图的示意图【来自】

在比较复杂的图结构中，为了判断一个图是否是欧拉图，有以下定理：

定理1：无向图G是欧拉图当且仅当G是连通的并且没有奇异点。 无向图 G 是半欧拉图当且仅当 G 是连通的并且恰好有两个奇点。

在有向图中，也有类似的定理。 即，如果有向连通图G是欧拉图，当且仅当图中各顶点的入度和出度相等。

根据定理1，我们回顾柯尼斯堡七桥问题。 通过计算每个节点的度，我们发现它显然不满足欧拉图的判断条件。

三、总结

1.欧拉图的由来——柯尼斯堡七桥问题。

2.欧拉图和半欧拉图的定义。

3、欧拉图的判断条件。

4. 参考文献

[1] 维基百科-柯尼斯堡七桥问题

[2]

[3]

编辑：郑高兴