歌尼斯堡7桥问题

歌尼斯堡7桥问题
歌尼斯堡7桥问题

歌尼斯堡7桥问题
18世纪时,欧洲有一个风景秀丽的小城哥尼斯堡,那里有七座桥.如图1所示：河中的小岛A与河的左岸B、右岸C各有两座桥相连结,河中两支流间的陆地D与A、B、C各有一座桥相连结.当时哥尼斯堡的居民中流传着一道难题：一个人怎样才能一次走遍七座桥,每座桥只走过一次,最后回到出发点?大家都试图找出问题的答案,但是谁也解决不了这个问题…………
欧拉在1727年20岁的时候,被俄国请去在圣彼得堡（原列宁格勒）的科学院做研究.差不多在这个时候,他的德国朋友告诉他一个曾经令许多人困惑的问题.
,
这城现被苏联占领,就像老沙皇把从中国占领的土地改名一样,这城现被改称为卡里林格勒（Kaliningrad）.有一条河横贯市内,河中心有二个小岛.在当时有七座桥把这小岛和对岸联结起来.（见图四）
在周末当地的市民喜欢在城里溜达,有人曾想法子从家里出发,走过所有的桥回到家里,他们想是否能有座桥只走过一次.许多人试过都不成功.现在是否有一个方法能走过?
欧拉的朋友知道这个青年人很聪明,并且喜欢思考问题,就告诉他这个“哥尼斯堡七桥问题”,要他想法子解决.
读者最好先在图四上“纸上漫步”,看看能不能走出一个法子来.如果行不通,那么就继续下去.
欧拉并没有跑到哥尼斯堡去走走.他把这个问题化成了这样的问题来看：把二岸和小岛缩成一点,桥化为边,二个顶点有边联结,当且仅当（if and only if）这点代表的地区有桥联结起来.这样欧拉就得到了一个图了.
欧拉如何解决“七桥问题”
欧拉现在考虑这个图是否能一笔画成,如果能够的话,对应的“七桥问题”也就解决了.
他先研究一般能一笔画成的图应该具有什么性质?他发现它们大体上有二类,不是全都是偶点就是有二个奇点.
这个情形是可以这样的看：如果一个图能一笔画成,那么一定有一个起点开始画,也有一个终点.其他图上的点是“过路点”——我们要经过它.
现在看“过路点”会有什么性质?它是“能上能下,有进有出”的点,有一条边进这点,那么就要有一条边出去,不可能是有进无出,它就会变成终点,也不可能有出无进,它就会变成起点.因此在“过路点”进出的边总数应该是偶数,即“过路点”是偶点.
如果起点和终点是同一点,那么它也是属于“有进有出”的类型,因此必须是偶点,这样图上全体的点是偶点.
如果起点和终点是不一样,那么它们必须是奇点了.因此这图最多只能有二个奇点.
现在对应七桥问题的图,所有的顶点都是奇点,共有四个,故这个图肯定不能一笔画成.
以上说明的方法不完全和欧拉把这个结果在1736年的圣彼得堡科学院学报上发表的一样.我是取其精神,自己改编成较通俗的讲法,希望读者能较容易的明白这个道理.欧拉很喜欢这个结果,他在以后的几个通俗数学演讲,时常以此为话题.
我们今天学习欧拉的成果不应是单纯把它当作数学游戏,重要的是应该知道他怎样把一个实际问题抽象化.研究数学问题不应该为“抽象而抽象”,抽象的目的是为了更有效的解决实际产生的问题,欧拉的大作就成为我们学习的一个样板.
事实上,中国民间很早就流传这种一笔画的游戏,从长期实践的经验,人们知道如果图的点全部是偶点,可以任意选取一点做起点,一笔画完.如果是有二个奇点,那么就选择一个奇点做起点以顺利的一笔画完.可惜的是古时的一些从事数学研究的儒生,受到“万般皆下品,唯有读书高”的思想毒害,对于民间的游戏当作“下里巴人的雕虫小技”不加以重视.如果那时中国的数学家把这一笔画书的经验总结,以及加以研究,可能“图论”的开山祖师将不是欧拉了.

哥尼斯堡七桥问题
18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如图1所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。
这个问题看起来似乎不难，但人们始终没有能找到答案，最后问题提到了大数学家欧拉那里。欧拉以深邃的洞察力很快证明了...

全部展开

哥尼斯堡七桥问题
18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如图1所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。
这个问题看起来似乎不难，但人们始终没有能找到答案，最后问题提到了大数学家欧拉那里。欧拉以深邃的洞察力很快证明了这样的走法不存在。欧拉是这样解决问题的：既然陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成A、B、C、D4个点，7座桥表示成7条连接这4个点的线，如图2所示。
于是“七桥问题”就等价于图3中所画图形的一笔画问题了。欧拉注意到，每个点如果有进去的边就必须有出来的边，从而每个点连接的边数必须有偶数
个才能完成一笔画。图3的每个点都连接着奇数条边，因此不可能一笔画出，这就说明不存在一次走遍7座桥，而每座桥只许通过一次的走法。
欧拉对“七桥问题”的研究是图论研究的开始，同时也为拓扑学的研究提供了一个初等的例子。
参考资料：http://www.cbe21.com/subject/maths/html/040303/2001_01/20010109_548.html

收起