柯尼斯堡七桥问题答案解析

橘子网 9,902 0

今天的俄罗斯加里宁格勒州首府加里宁格勒,二战之前属于德国的领土,原名叫做柯尼斯堡(Königsberg)。

柯尼斯堡七桥问题答案解析

柯尼斯堡这座小城在历史上曾是德国的文化中心之一,大哲学家伊曼努尔·康德(Immanuel Kant)、文学家E·T·A·霍夫曼(Ernst Theodor Wilhelm Hoffmann)、数学大师大卫·希尔伯特(David Hilbert)和四维时空理论的创立者赫尔曼·闵可夫斯基(Hermann Minkowski)都曾在此居住过,这里也是数学家克里斯蒂安·哥德巴赫(Christian Goldbach)的故乡,而数学中著名的柯尼斯堡七桥(Seven Bridges of Königsberg)问题就源于这个城市。

在柯尼斯堡市区,有一条普列戈利亚(Pregolya)河流经,河中心有两个小岛。小岛与河的两岸有七条桥连接。当地曾有人提出:在所有桥都只能走一遍的前提下,如何才能把这个地方所有的桥都走遍?这就是著名的柯尼斯堡七桥问题。

柯尼斯堡七桥问题答案解析

著名的瑞士数学家莱昂哈德·欧拉(Leonhard Euler)在1735年提出,并没有方法能圆满解决这个问题,他更在第二年发表在论文《柯尼斯堡的七桥》中,证明符合条件的走法并不存在,也顺带提出和解决了一笔画问题。这篇论文在圣彼得堡科学院发表,成为图论史上第一篇重要文献,也成为拓扑学的出发点。

柯尼斯堡七桥问题答案解析

欧拉把真实世界的数学问题抽象简化为平面上的点与线组合,每一座桥视为一条线,桥所连接的两岸和小岛视为点。这样若从某点出发后最后再回到这点,则这一点的线数必须是偶数,这样的点称为偶顶点。相对的,连有奇数条线的点称为奇顶点。欧拉论述了,由于柯尼斯堡七桥问题中存在4个奇顶点,它无法实现符合题意的遍历。

柯尼斯堡七桥问题答案解析

欧拉把问题的实质归于一笔画问题,即判断一个图是否能够遍历完所有的边而没有重复,而柯尼斯堡七桥问题则是一笔画问题的一个具体情境。欧拉最后给出任意一种“河桥图”能否全部走一次的判定法则,从而解决了“一笔画问题”。

对于一个给定的连通图,如果存在两个以上(不包括两个)奇顶点,那么满足要求的路线便不存在了,且有n个奇顶点的图至少需要n/2笔画出。如果只有两个奇顶点,则可从其中任何一地出发完成一笔画。若所有点均为偶顶点,则从任何一点出发,所求的路线都能实现,他还说明了怎样快速找到所要求的路线。

下面我进一步解析一下欧拉这篇论文中的主要思想。

先介绍一个概念:顶点的度数(degree),即顶点所连接的边数。度数是奇数的点叫做奇点(odd vertex),度数是偶数的点叫做偶点(even vertex)。

柯尼斯堡七桥问题答案解析

奇点的情况:

柯尼斯堡七桥问题答案解析

偶点的情况:

柯尼斯堡七桥问题答案解析

因此,我们可以发现:凡是经过奇点,“一进一出”后依旧是奇点;凡是经过偶点,“一进一出”后依旧是偶点。这是理解柯尼斯堡七桥问题的关键之处。

下面分两种情况讨论:

一、起点与终点相同的情况:

柯尼斯堡七桥问题答案解析

一笔画成,意味着“边走边减”,结果所有的顶点的度数都变为0(偶数)。因为假如还存在度数不为0的顶点,那么也就存在没经过的边。

经过“边走边减”之后,经过的顶点的奇偶性不变。由此我们可知度数变为0(偶数)的经过点,在原图中本来就是偶点。此外,起点度数减1,终点度数也减1,变为0。然而,起点和终点是相同的,因此相同顶点的度数减了2,所以该顶点也变成了偶点。

结论,在“起点和终点相同”的一笔画中,图中的顶点都是偶点。这样的路线后来被称作“欧拉图(Euler Graph)”。如下图:

柯尼斯堡七桥问题答案解析

二、起点和终点不同的情况:

柯尼斯堡七桥问题答案解析

和第一种情况相同的思路,凡是经过的顶点全部是偶点。只有起点和终点是奇点。据此,在“起点和终点不同”的一笔画中,图中只有2个奇点。

因此,我们可知以下命题是成立的:如果可以一笔画成,则所有的顶点都是偶点,或者有2个奇点;反之,如果所有的顶点都是偶点,或者有2个奇点,则可以一笔画成。

欧拉的论断重点在于:不反复试验也能证明是否可以一笔画成。不用频繁地尝试各种路径,只要观察各顶点的度数就可以了。

欧拉的证明中还蕴含着重要的数学思维,那就是在观察各顶点的边数时,着眼点并不在于“数的本身”,而是“数的奇偶性”。并不是1条、3条、5条这样分散地思考路径,而是概况为“奇数条”来整体考虑。在一笔画问题中,这个“奇偶性”就是解题的关键。

在前面的文章里,我曾经提到过一个关于分蛋糕的问题:用5条直线最多可将圆形纸片划分成多少部分?

柯尼斯堡七桥问题答案解析

这个问题的关键在于,我们要发现每一条线划下去会增加多少个区域?如果从纯粹的分割后的块数去看,我们是很难发现规律的。如下图所示:

柯尼斯堡七桥问题答案解析

再来看一道题目:前3个六边形如下如所示,求前5个六边形之和。

柯尼斯堡七桥问题答案解析

这里求和不是难点,难的是如何看出变化的规律。仔细观察可以发现,每个图形都在前一个图形的基础上套了一个点数加1为边长的六边形,而增加的点数是由其中4条边产生的,因此我们可以发现增加的数量应该是4倍的边长(点数)减去其中重复计算的3个点。

柯尼斯堡七桥问题答案解析

这两道题的解题关键与欧拉解决柯尼斯堡七桥问题所运用的数学思维有类似之处,就是都抛开了数字本身看问题,欧拉从数字的奇偶性发现问题的核心,后两者则从数字的增减变化找突破口。

现在大部分孩子在学习数学知识的时候,光顾着背公式记答案,完全没有考虑到抛开数字本身看问题本质的重要性,导致数学这门课举步维艰,心存怯意。数学是一门很好玩的课程,只要多问几个为什么,理解每一个原理和基础知识的来龙去脉,学会从知识的关联性上看问题,掌握数形结合,就一定可以在这门课上走得很远。

数学与物理学有很大的不同,假如说物理学是学知识,那么数学则是学思维。如果数学思维掌握了,数学就能很快打通全身经脉,实现自我运行。可惜现在的教育模式只是在乱贴膏药,舍本逐末,把最不需要记忆或者背诵的课程硬生生地变成了语文课。中国奥数教父单墫教授曾在一本给初中生写的书中说到:“学数学,不是为了当熟练的‘操作工’、‘模仿秀’,而是为了学会思考。大量重复的练习,不利于培养学习的兴趣,甚至会弄坏了学习的‘胃口’。

最后提一下瑞士数学家欧拉,他是我心中的偶像。如果说阿基米德、牛顿和高斯是人类历史上最伟大的三位数学家,那么欧拉就是这三人之后的第四位数学大师。欧拉在数学的多个领域,包括微积分图论都做出过重大发现。他引进的许多数学术语书写格式,例如函数的记法一直沿用至今。此外,他还在力学光学天文学等学科有突出的贡献。法国数学家皮埃尔-西蒙·拉普拉斯曾这样评价欧拉对于数学的贡献:“读欧拉的著作吧,在任何意义上,他都是我们的大师。

在欧拉的数学生涯中,他的视力一直在恶化。在1735年一次几乎致命的发烧后的三年,他的右眼近乎失明,但他把这归咎于他为圣彼得堡科学院进行的辛苦的地图学工作。视力在他在德国期间也持续恶化,以至于被誉为“独眼巨人”。后来,欧拉的原本正常的左眼又遭受了白内障的困扰。在他于1766年被查出有白内障的几个星期后,导致了他的近乎完全失明。即便如此,病痛似乎并未影响到欧拉的学术生产力,这大概归因于他的心算能力和超群的记忆力。在人生的最后7年里,欧拉的双目完全失明,在助手的帮助下,他还是以惊人的速度产出了生平一半的著作(他一生写有近80本著作)。

上一篇:

下一篇:

相关阅读

分享