浅谈：无向图的欧拉回路

无向图的欧拉回路如果读者在动手过程中产生了上述思路并得出了上述结论那么恭喜您您完成了欧拉在 300 年前做出的发现。欧拉对哥尼斯堡七桥问题的分析更加抽象化。首先欧拉将每片地区抽象为一个点并将每座桥抽象为连接两点的一条线得到如下抽象图形。了解图论的读者一定会觉得非常熟悉因为这一抽象正是图的表示。事实上欧拉对哥尼斯堡七桥问题的研究正是图论的开端[^2]。将问题抽象为图后我们可以用图论的语言描述该问题给定一张无向图问是否存在一条从某个节点出发并最终回到该节点的路径使得该路径恰好经过每条边一次。为了纪念欧拉的发现符合要求的路径被称为“欧拉回路”。与上一节中的分析类似对于任意一个与起点不同的节点进入该节点需要“消耗”一条边而离开该节点需要“消耗”另一条边。因此该节点的度数连接该节点的边的数量若一条边的两端是同一个节点则需计算两次必须为偶数才能保证我们不被“困在”该节点中。同样地对于起点而言离开起点需要“消耗”一条边而回到起点需要“消耗”另一条边。因此起点的度数也必须为偶数才能保证我们最终能回到起点。我们依此得到无向图中存在欧拉回路的判定条件一张无向图中存在欧拉回路当且仅当所有非零度节点有边连接的节点是连通的且每个节点的度数均为偶数。