怎样解七桥问题通过电脑解
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/28 11:10:14
怎样解七桥问题通过电脑解
怎样解七桥问题
通过电脑解
怎样解七桥问题通过电脑解
18世纪,东普鲁士的首府哥尼斯堡是一座景色迷人的城市,普莱格尔河横贯城区,使这
座城市锦上添花,显得更加风光旖旋.这条河有两条支流,在城中心汇成大河,在河的
中央有一座美丽的小岛.河上有七座各具特色的桥把岛和河岸连接起来.
每到傍晚,许多人都来此散步.人们漫步于这七座桥之间,久而久之,就形成了这样一
个问题：能不能既不重复又不遗漏地一次相继走遍这七座桥?这就是闻名遐迩的“哥尼
斯堡七桥问题.”每一个到此游玩或散心的人都想试一试,可是,对于这一看似简单的
问题,没有一个人能符合要求地从七座桥上走一遍.这个问题后来竟变得神乎其神,说
是有一支队伍,奉命要炸毁这七座桥,并且命令要他们按照七桥问题的要求去炸.
七桥问题也困扰着哥尼斯堡大学的学生们,在屡遭失败之后,他们给当时著名数学家欧
拉写了一封信,请他帮助解决这个问题.
欧拉看完信后,对这个问题也产生了浓厚的兴趣.他想,既然岛和半岛是桥梁的连接地
点,两岸陆地也是桥梁的连接地点,那就不妨把这四处地方缩小成四个点,并且把这七
座桥表示成七条线.这样,原来的七桥问题就抽象概括成了如下的关系图：
这显然并没有改变问题的本质特征.于是,七桥问题也就变成了一个一笔画的问题,即
：能否笔不离纸,不重复地一笔画完整个图形.这竟然与孩子们的一笔画游戏联系起来
了.接着,欧拉就对“一笔画”问题进行了数学分析一笔画有起点和终点,起点和终点
重合的图形称为封闭图形,否则便称为开放图形.除起点和终点外,一笔画中间可能出
现一些曲线的交点.欧拉注意到,只有当笔沿着一条弧线到达交点后,又能沿着另一条
弧线离开,也就是交汇于这些点的弧线成双成对时,一笔画才能完成,这样的交点就称
为“偶点”.如果交汇于这些点的弧线不是成双成对,也就是有奇数条,则一笔画就不
能实现,这样的点又叫做“奇点”.见下图：
欧拉通过分析,得到了下面的结论：若是一个一笔画图形,要么只有两个奇点,也就是
仅有起点和终点,这样一笔画成的图形是开放的；要么没有奇点,也就是终点和起点连
接起来,这样一笔画成的图形是封闭的.由于七桥问题有四个奇点,所以要找到一条经
过七座桥,但每座桥只走一次的路线是不可能的.
有名的“哥尼斯堡七桥问题”就这样被欧拉解决了.
在这里,我们可以看到欧拉解决这个问题的关键就是把“七桥问题”变成了一个“一笔
画”问题,那么,欧拉又是怎样完成这一转变的呢?
他把岛、半岛和陆地的具体属性舍去,而仅仅留下与问题有关的东西,这就是四个几何
上的“点”；他再把桥的具体属性排除,仅留下一条几何上的“线”,然后,把“点”
与“线”结合起来,这样就实现了从客观事物到图形的转变.我们把得到“点”和“线
”的思维方法叫做抽象,把由“点”和“线”结合成图形的思维方法叫做概括.所谓抽
象就是从客观事物中排除非本质属性,透过现象抽出本质属性的思维方法.概括就是将
个别事物的本质属性结合起来的思维方法.
Euler在1736年访问Konigsberg, Prussia(now Kaliningrad Russia)时,他发现当地的市民正从事一项非常有趣的消遣活动.Konigsberg城中有一条名叫Pregel的河流横经其中,在河上建有七座桥如图所示: 这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步,每座桥只能经过一次而且起点与终点必须是同一地点.
Euler把每一块陆地考虑成一个点,连接两块陆地的桥以线表示,便得如下的图后来推论出此种走法是不可能的.他的论点是这样的,除了起点以外,每一次当一个人由一座桥进入一块陆地（或点）时,他（或她）同时也由另一座桥离开此点.所以每行经一点时,计算两座桥（或线）,从起点离开的线与最后回到始点的线亦计算两座桥,因此每一个陆地与其他陆地连接的桥数必为偶数.
七桥所成之图形中,没有一点含有偶数条数,因此上述的任务是不可能实现的.