哥尼斯堡七桥问题

来自计算思维百科
跳转至: 导航搜索
哥尼斯堡(Konigsberg)地处东普鲁士,位于普雷格尔(Pregel)河的两岸及河中心的两个岛上,城市各部分由七座桥梁连接着,如图1所示。多年来,该城居民总有一个愿望:从家里出去散步,通过每座桥恰好一次再返回家中。但是任何人也没有找出这样一条理想的路径,问题最终被欧拉发表的论文中解决了,但结果却是令人遗憾的否定性答案。
8.4.1.png

图1 哥尼斯堡七桥示意图

欧拉解決问题的方法是:既然岛屿与河岸用桥相连,又仅仅是考虑过桥问题,那就可以把陆地区域抽象为一个点,用连接两个点的线段表示桥梁,这样在不改变问题实质的情况下,把过桥问题抽象成只有点和线的图,如图2所示:
8.4.2.png

图2 哥尼斯堡七桥模拟图