企业官网建设流程全解析

无向图的欧拉回路

如果读者在动手过程中产生了上述思路，并得出了上述结论，那么恭喜您，您完成了欧拉在 300 年前做出的发现。

欧拉对哥尼斯堡七桥问题的分析更加抽象化。首先，欧拉将每片地区抽象为一个点，并将每座桥抽象为连接两点的一条线，得到如下抽象图形。

了解图论的读者一定会觉得非常熟悉，因为这一抽象正是图的表示。事实上，欧拉对哥尼斯堡七桥问题的研究正是图论的开端[^2]。

将问题抽象为图后，我们可以用图论的语言描述该问题：

给定一张无向图，问是否存在一条从某个节点出发，并最终回到该节点的路径，使得该路径恰好经过每条边一次。

为了纪念欧拉的发现，符合要求的路径被称为“欧拉回路”。

与上一节中的分析类似，对于任意一个与起点不同的节点，进入该节点需要“消耗”一条边，而离开该节点需要“消耗”另一条边。

因此，该节点的度数（连接该节点的边的数量，若一条边的两端是同一个节点则需计算两次）必须为偶数，才能保证我们不被“困在”该节点中。

同样地，对于起点而言，离开起点需要“消耗”一条边，而回到起点需要“消耗”另一条边。因此，起点的度数也必须为偶数，才能保证我们最终能回到起点。

我们依此得到无向图中存在欧拉回路的判定条件：

一张无向图中存在欧拉回路，当且仅当所有非零度节点（有边连接的节点）是连通的，且每个节点的度数均为偶数。