高等数学最难题(用高等数学清扫脚下路)

高等数学最难题(用高等数学清扫脚下路)(1)

积雪清扫车

用高等数学

清扫脚下路

前几天,北京下了2021年的第一场雪。这让很多生活在南方的孩子羡慕不已。她说:“下大雪看着确实挺好看的,可对那些无家可归的人,还有天没亮就起来扫街的环卫工来说,尤其是老人,下雪会让他们本来就困难的生活更加艰难。

高等数学最难题(用高等数学清扫脚下路)(2)

环卫工人清扫积雪

也就是因为她这句话,突然想到了一个关于雪还有清扫马路的数学问题。

看完以后,谁再问你数学有什么用,可以直接把这篇文章转给他。

数学清扫马路?

高等数学最难题(用高等数学清扫脚下路)(3)

积雪

在上面这张图中,很明显,地面被白雪覆盖,公路上却干干净净。这肯定不是雪花故意绕开的选择,也不能是靠环卫工纯人力去扫除的。

没见过雪的南方孩子或许知道向积雪路面“撒盐”可以融雪,但他们一定没有见过这个东西。

高等数学最难题(用高等数学清扫脚下路)(4)

不好意思,放错了,是下面这个。

高等数学最难题(用高等数学清扫脚下路)(5)

组合铲雪车

当然,在国内,北方孩子最常见的还是下面这种铲雪车:

高等数学最难题(用高等数学清扫脚下路)(6)

那为啥说它跟数学有关呢?这就要说到路线规划问题。

学过数学的人一辈子都不会忘记的知识点中,一定有一句“两点之间直线最短”。可公路并不总是直线连接的,而且也不只有一个“铲”那么宽。

虽然铲雪车出现的目的就是为了铲雪,但也不能随心所欲地开,能够找到一条省时、省油又能清扫干净的路线,可以省一大笔钱。

好比,加拿大的多伦多用“图论原理”对铲雪线路进行规划后,铲雪费用比之前减少了三分之一,每年节省了大约300万美金(约合2千万人民币)

高等数学最难题(用高等数学清扫脚下路)(7)

怎么用数学清扫马路?

一条最短铲雪路线是铲雪车横穿所有所需的过道,而不会回溯路线的任何部分。如果存在这样的路径,则称为欧拉路径;如果该路径在同一位置开始和结束,则称为欧拉回路。

经过一个图中每条边且仅经过一次,并且经过每个顶点的路径,叫做这个图的一条欧拉路径(Euler Path),如果欧拉路径的起点和终点是同一个点则这条欧拉路径为欧拉回路(Euler circuit)。

简单来说:

高等数学最难题(用高等数学清扫脚下路)(8)

数学家发现,表示此问题的简便方法是使用图形。图形只是边缘和顶点交叉的集合。对于扫雪车路线,边缘代表扫雪车必须走的街道,并且顶点是交叉点。

例如,对于世界上最简单的城市(如下左图所示),该图由四个边和四个顶点(如下右图所示)组成。

高等数学最难题(用高等数学清扫脚下路)(9)

数学家发现,确定欧拉路径是否存在的关键是奇数顶点的数量。即使顶点连接偶数个边,也将其视为顶点;如果顶点连接奇数个顶点,则将其视为奇数,反之则为偶数。上面的图形有四个偶数顶点,下面的城市有四个偶数顶点和两个奇数顶点。

高等数学最难题(用高等数学清扫脚下路)(10)

通过多次试验,你很容易就会发现:

高等数学最难题(用高等数学清扫脚下路)(11)

但现实并不像理想中的那么简单,问题很快就出现了:如果有两个以上的奇数顶点,该怎么办?

一种答案是使用更多的铲雪车,这一看就知道不是最佳选择。

高等数学最难题(用高等数学清扫脚下路)(12)

在这种情况下,实际上可以将图形分成“边缘分离的路径”,它们是没有任何公共边的简单路径。对于具有

高等数学最难题(用高等数学清扫脚下路)(13)

奇数个顶点的任何一组连通的顶点,该图可能会覆盖n个边不相交的路径。

比如,如果我们的城市变大了一点,随之我们就添加了另一条途径,则对应的图形将如下图所示。

高等数学最难题(用高等数学清扫脚下路)(14)

请注意,它具有

高等数学最难题(用高等数学清扫脚下路)(15)

个奇数顶点,因此可以用2条边缘分离的路径覆盖,如下所示。

高等数学最难题(用高等数学清扫脚下路)(16)

(虚线为1条,实线为另1条)

这种情况下,如果你是想找到一条最少重复的路径,而不是尝试去找一条不相交的路径,该怎么办?

一种非常简单的办法就是加边,通过添加“边”,就可以使奇数顶点的数量减少2个,这样就能找到一条欧拉路径。而且,如果把奇数顶点的数量减少到0(如下图),就可以找到一个欧拉回路。

高等数学最难题(用高等数学清扫脚下路)(17)

所以,如果你看到铲雪车在街道上来回开两次,这可不代表效率低,实际上可能非常高效。 洒水车和垃圾扫地车也是这个原理。

七桥问题与中国邮差问题

然而实际上,公路可能七扭八拐,这要怎么找奇偶数顶点?如果不能应用到实际生活中,那么从这个角度来看,“欧拉途径”这个数学问题确实“没什么用”。

高等数学最难题(用高等数学清扫脚下路)(18)

但是,随着科技的发展,卫星定位技术已经可以把“世界”放在地图上。

高等数学最难题(用高等数学清扫脚下路)(19)

又得益于计算机技术的进步,一些软件能够把城市的交通网进行分割分析,然后再分别进行计算,进而规划出路径,欧拉途径就这样被应用到了“铲雪”一事上。

高等数学最难题(用高等数学清扫脚下路)(20)

但是,计算机并不是直接在欧拉问题的基础上开始的,而是先从中国邮差问题。

1962年,我国数学家管梅谷提出过一个数学问题:一名邮差从邮局出发送信,要求对辖区内每条街,都至少通过一次,再回邮局。在此条件下,怎样选择一条最短路线?后来,美国数学家 Alan J. Goldman 把这个问题命名为“中国邮差问题”。

这个问题同理可以套用扫水车、路面清理......

不过最后还是得绕回欧拉身上,因为欧拉在1735年就研究过一个和管梅谷类似的问题——七桥问题,并得到了一些重要的结论。

高等数学最难题(用高等数学清扫脚下路)(21)

七桥问题 图片来源:wikipedia

在普鲁士的柯尼斯堡有两个小岛,两个小岛和附近一共有7座桥连通。怎样规划路线才能恰好经过每一座桥一次?

可是。欧拉虽然提出了七桥问题,但他给出的能解的一般条件是每块地都必须有偶数座桥,而七桥问题不符合这种情况,也就是说七桥问题不可解。

高等数学最难题(用高等数学清扫脚下路)(22)

欧拉证明,只有当奇顶点的数量等于0或2时,才存在一笔画。七桥问题的奇顶点(蓝点)的数量等于4,因此无法一笔画。

后来,类似七桥问题、中国邮差问题的问题在数学上发展成了图论和拓扑学。因为欧拉的开创性贡献,一笔画的图被叫做欧拉图,一笔画的路径被叫做欧拉路径。

高等数学最难题(用高等数学清扫脚下路)(23)

串的奇顶点有2个(最上和最下)

把欧拉证明的结论用到到中国邮差问题上,遇到三岔路口、五岔路口时就不得不回头。

于是计算机数学家们就把奇数路口单独另算,再找到这些路口间的最短路径;又因为偶数岔路口一定存在只走一次的方法,最后把这两部分拼起来就找到了“最短路径”。

也就是:

就这样,北方的孩子再也不用滑雪橇上学了。

写在最后

所以,如果有一天你听见有人说博士生“扫大街”,千万不要再惊讶了!

高等数学最难题(用高等数学清扫脚下路)(24)

在这个浮躁的时代,一些人觉得研究纯数学和应用数学的数学家要名难出名,要利难获利,他们应该把自己的聪明才智用在搞金融上。

数学研究是一个功在后世的学科,正如200多年前欧拉的一个数学证明,可以在今天方便我们的生活一样。伟大的数学家看的不是眼前,而是未来。

然而,科学的发展不能只靠数学家来推动!每一位数理爱好者的出现,都是科学长远发展的推动力。

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页