释疑解惑 您当前所在位置:首页 > 释疑解惑
哥尼斯堡七桥问题
作者:马文驹     时间:2010-4-14     点击率:61548


哥尼斯堡七桥问题的答案:(问题的提出见本期力学园地“科普花园”)
  这是一个著名的图论问题,同时也是拓扑学研究的一个例子。实际上就是民间一笔画游戏。请看上面图1和图2。图1是可以一笔画出来的,图2就不能一笔画出来了。
  法则:把图看成是由点和线组成的一种集合。图里直线的交点叫做顶点,连结顶点的线叫做边。这个图是联通的,即任何二个顶点之间都有边。很显然,图中的顶点有两类:一类是有偶数条边连着它的,另一类是有奇数条边连着它的。一个顶点如果有偶数条边连着它,这点就称为偶点;如果有奇数条边连着它,就称它为奇点。能一笔画的图形只有两类:一类是所有的点都是偶点。另一类是只有二个奇点的图形。图1只有2个奇点,其余都是偶点,所以能一笔画出。图2有六个奇点,四个偶点,当然就不能一笔画出来了。
  那么,这又是为什么呢?当年年仅20岁的大数学家欧拉最早解决了这个问题。他想:既然陆地是桥梁的连接地点,不妨把图中被河隔开的陆地看成4个点,7座桥表示成7条连接这4个点的线,如图3所示。
  于是“七桥问题”就等价于图4中所画图形的一笔画问题了。欧拉注意到,如果一个图能一笔画成,那么一定有一个起点开始画,也有一个终点。图上其它的点是“过路点”——画的时候要经过它。
  现在看“过路点”具有什么性质。它应该是“有进有出”的点,有一条边进这点,那么就要有一条边出这点,不可能是有进无出,如果有进无出,它就是终点,也不可能有出无进,如果有出无进,它就是起点。因此,在“过路点”进出的边总数应该是偶数,即“过路点”是偶点。如果起点和终点是同一点,那么它也是属于“有进有出”的点,因此必须是偶点,这样图上全体点都是偶点。如果起点和终点不是同一点,那么它们必须是奇点,因此这个图最多只能有二个奇点。现在对照七桥问题的图,所有的顶点都是奇点,共有四个,所以这个图肯定不能一笔画成。
  由此,我们不难想到,如果再造上一座桥,如图5、图6所示,散步者就能一次走遍所有桥,而且每座桥只通过一次。对于图2的情况,我们只要加上二段线,就可以一笔画成了,见图7。