当前位置:人教学习网 > 学科世界 > 趣味数学

趣味数学

七桥问题与图论

2010-08-16 已有7492人阅读

    俄国的加里宁格勒,18世纪称为哥尼斯堡,风景秀丽,是一座历史名城。城中有一条河,两条支流环抱着的一座美丽的小岛,是城市的商业中心。河上共建有七座桥,方便了居民购物、散步,也吸引了众多的游客观光。一天,有人提出了一个问题:能不能一次不重复地走遍所有七座桥,最后仍回到出发点?

    这个既简单又有趣的问题吸引了很多人,他们尝试了各种各样的走法,但谁也不能一次不重复地走遍。有人计算过,如果对7座桥沿任何可能的路线都走一下的话,共有5040种走法,而这么多的走法中是否存在一条不重复走遍7座桥的路线呢?这个问题谁也回答不了。这就是著名的“七桥问题”。

    大哲学康德(kant,1724—1804)终生没有离开过哥尼斯堡。每天下午他都要在城里散步,但是他也一次都没有成功过七桥而不重复的路线。七桥问题引起了大数学家欧拉(Euler,1707—1783)的关注。他把具体七桥布局化归为图2所示的简单图形。于是七桥问题就变成一个一笔画问题:要怎样才能从A、B、C、D中的某一点出发,一笔画出这个简单图形即笔不离开纸,而且a、b、c、d、e、f、g各条线只画一次不准重复呢?欧拉证明了这样的走法不存在。

    如图1所示:河中的小岛A与河的左岸B、右岸C各有两座桥相连接,河中两支流间的陆地D与A、B、C各有一座桥相连接。哥尼斯堡的居民中流传着这样一道难题:一个人怎样才能一次走遍七座桥,每座桥只走过一次呢?这个问题看起来不难,大家都试图找出问题的答案,但是谁也解决不了这个问题。

    如果我们从某点出发,一笔画了某个图形,到某一点终止,那么除起点和终点外,画笔每经过一个点一次,总有画进该点的一条线和画出该点的一条线,因此就有两条线与该点相连接。如果画笔经过一点n次,那么就有2n条线与该点相连接。因此,这个图形中除起点与终点外的各点,都与偶数条线相连。

    如果起点和终点重合,那么这个点也与偶数条线相连;如果起点和终点是不同的两个点,那么这两个点都是与奇数条线相连的点。综上所述,一笔画出的图形中的各点或者都是与偶数条线相连的点,或者其中只有两个点与奇数条数相连。

    现在再看看图2。A点与5条线相连接,B、C、D各点与3条线相连接,所以图中就有4个与奇数相连的点。不论是否要求起点与终点重合,都不能一等画出这个图形。

    1736年,欧拉研究解决了七桥问题,他认为这是一种全新的数学研究方法,决定把这种只研究各部分相互位置的规律而不考虑其大小的数学分支,取名为“位置几何学”,后来叫做“拓扑学”。他的研究是图论研究的开始。七桥问题本身似乎只是一个游戏,但是欧拉给出的抽象意义和论证方法开创了畋论研究的先河。从那之后,数学家们开始研究图论。在现代,科技的迅猛发展为图论提供了越来越多需要解决的问题,而图论研究也为计算机科学和另外一些科学领域的研究发展作出了显著的贡献。

法律声明  |  网站地图  |  联系我们  |   友情链接  |  北京市公安局海淀分局备案编号:1101083525

Copyright © 2009-2014 人民教育出版社 人教学习网 版权所有