Python3 趣味系列题10 ------七桥

image

一、问题描述

在哥尼斯堡的一个公园里，七座桥将普雷格尔河中的两个岛之间以及河岸连接起来。问是否能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起始的陆地？将上面的图形抽象为下面的图：

image

也就是从上图中的任何一个顶点出发，遍历所有的边，并且每条边只能经过一次，最后再回到开始的点。

二、解题思路

欧拉通过研究这类型问题，于1736年得出下面的结论：

• 所有节点的度均是偶数。此时为欧拉回路，也称为欧拉闭迹。这种情况下存在从任意一个节点出发，遍历所有的边，并且每条边只经过一次，再回到出发点的路径。

• 节点的度是奇数的节点有且仅有2个。此时为欧拉通路，也称为欧拉开迹。这种情况下存在从任意一个度为奇数的节点出发，遍历所有的边，并且每条边只经过一次，最终到达另一个度为奇数的节点的路径。

• 其他情况不存在从一个节点出发，遍历所有的边，并且每条边只经过一次，再回到任意节点的路径。也就是不能够一笔画出这个图形。

节点的度就是与这个节点连接的边的个数。例如上图中节点岛D的度为3，因为有3条边与其连接；同理节点岛C的度为5，河岸A、B的度均为3。因此对于七桥问题，度为奇数的点的个数为4，因此不存在这样的路径。

三、Python3实现

Fleury(弗洛莱)算法的步骤：

• 首先判断是否存在路径。存在的话，判断是欧拉回路还是欧拉通路。欧拉回路的起始点可以是任意一个。欧拉通路的起点必须是度为奇数的2个节点中的其中一个。

• 选择起始点作为当前的点(CP)，当还有没走过的边时进行下面的循环：

1. 得到与当前的节点(CP)相邻的节点的集合，也就是集合中的点与当前的节点组成的边没有走过。

2. 遍历集合中的点，如果这个点与当前的节点组成的边，并且这条边不是桥，并且这个点不是终点，则作为下一个要去的节点。

3. 如果没有满足上面条件的点，则在是桥的节点中选择一个不是终点的节点，作为下一个要去的节点；

4. 如果还未找到，则把终点作为下一个要去的节点。

5. 把要去的节点和当前的节点组成的边记录为走过。将刚才找到的要去的节点作为当前的节点；

• 下一个要去的节点构成的集合，就是最终的路径。

如果将某条边去掉，剩下的图不是连通的，也就是被隔裂为2部分，则这条边就是桥。

四、结果图示

为了谜题的输入简单，用户需要在绘图网站上，绘制出谜题，然后导出作图过程的html格式的文件，程序会读取这个文件，然后自动生成谜题和计算路径。绘图网站GeoGebra。

• 1.欧拉回路

1.1 网站绘制的图

image

• 1.2求解过程中的图

image

• 2. 欧拉通路

• 2.1 网站绘制的图

image

• 2.2 求解的图

image

点击获得更多趣味谜题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image image