通俗易懂的欧拉回路——哥尼斯堡七桥问题

时间:2024-05-21 11:00:10

作者:翁松秀


通俗易懂的欧拉回路——哥尼斯堡七桥问题

问题背景

通俗易懂的欧拉回路——哥尼斯堡七桥问题
“7桥问题” 就是如何能从任一处陆地出发,经过且经过每个桥一次后回到原出发点,这个问题可抽象为一个如图所示的数学意义上的图。问题转化为:“从图中的某个节点出发,经过每座桥恰好一次,又回到该节点。”
通俗易懂的欧拉回路——哥尼斯堡七桥问题

欧拉路径

如果图G中的一个路径包括每个边恰好一次,则该路径称为欧拉路径(Euler path)。

欧拉回路

如果一个回路是欧拉路径,则称为欧拉回路(Euler circuit)。

欧拉图

具有欧拉回路的图称为欧拉图(简称E图)。

问题抽象与转化

原始问题:“是否能从某块陆地出发,经过每座桥恰好一次,最后回到出发点?”
抽象成数据模型:“是否能从图中的某个图出发,经过每条边恰好一次,最后回到出发节点?”
欧拉转化:“该图是否存在欧拉回路?”

无向图存在欧拉回路的充要条件

一个无向图存在欧拉回路,当且仅当该图所有顶点度数都为偶数,且该图是连通图

有向图存在欧拉回路的充要条件

一个有向图存在欧拉回路,所有顶点的入度等于出度且该图是连通图

问题的解

将原始问题抽象成无向图,判断该无向图不存在欧拉回路,所以七桥问题无解。