您的位置:   网站首页    行业动态    一笔画问题

一笔画问题

阅读量:3669562 2019-10-22


猜一猜,下面哪张图是一笔画不成的?

什么样的图形只用一笔就能画出来?笔既不离开纸面,也不重复。这实际上是十八世纪一个经典的数学问题:哥尼斯堡七桥问题。
七桥问题
在普鲁士的哥尼斯堡(今俄罗斯加里宁格勒)有一个公园,公园里有七座桥将普雷格尔河中两个岛与与河岸连接起来。

1736年,当地居民举办了一项有意思的健身活动:在星期六作一次走过所有七座桥的散步,每座桥只能经过一次而且起点与终点必须是同一地点。
有许多人进行了尝试,但是都失败了。此时当时世界上最伟大的数学家欧拉刚好在这里,他敏锐的发现这里蕴藏着深刻的数学内涵,并把它称为一笔画问题。

欧拉把七座桥画作七条线段,并把问题转化为是否可以通过一笔将这个图形画出来。经过思考,欧拉认为这是不可能的。
不仅如此,欧拉还得出了哪些图形可以一笔画,哪些不能一笔画的条件。
首先,欧拉把图形中的点分为两种:如果过该点的线段有偶数条,就称为偶点;如果过该点的线段有奇数条,就称为奇点。比如下面的图形中,红色圆圈的点就是偶点,绿色圆圈的点就是奇点。

欧拉指出:如果一个图形可以一笔画,那么它的奇点个数一定是0个或者2个。
如果奇点个数是0个,那么起点和终点是同一个点,从图形中任何一点出发都可以一笔画,比如上图中左边的图形就是这样。
如果奇点个数是2个,那么只能从一个奇点出发,画到另一个奇点,才能将图形画出来,这就是上图中右边的情况。
理解这个问题其实并不难,因为:

例题解析


知识点延伸:
出发:欧拉定理
哥尼斯堡七桥问题非常著名,大意就是能否从一块陆地出发,不重复地遍历所有的桥,在欧拉于1736年提出的一篇论文中解决。当时,许多当地居民以走七桥为消遣,引发了欧拉的兴趣。因为没有手工枚举出一种走法,这个问题就困扰了许多数学家。之后,欧拉将七桥抽象成几何图案,也就是现在大家很熟悉的一笔画问题,欧拉定理并就此产生。

欧拉定理是判断在一个连通的无向图中,能否一笔画不重复地走遍所有的边。先定义每个点的度数,为从一个点出发,往外连接的边有多少条,也就是直接的邻居点有多少个。现在将所有点的度数分为奇数和偶数,也就能将点分成奇数点和偶数点。若全都是偶数点,则可以从任意一个点出发,不重复地遍历所有边之后再回到起点。若有且仅有两个奇数点,则可以以其中任意一个为起点,另一个为终点,同样进行遍历。其余的情况就不可能一笔画了,所以上图中的七桥问题是无解的。如果起点和终点相同,则称其为欧拉回路;反之,如果起点和终点不同,则称其为欧拉路径。
寻找路径:Fleury 算法
一笔画问题简单又好记,现在新的问题来了:如果给定一个一定能够一笔画的图,求任何一条可行的欧拉回路或路径。当然,你可以用最朴素的做法进行枚举,可是如果点数或边数特别多,就会很费时。在此介绍 Fleury 算法,可以直接地解决这个问题。
如果是你而不是计算机来做一笔画,你肯定有个大致的方向,什么边不能先走。所以定义一种边,称为桥。如下图所示,将图分为 A 与 B 两个部分,且两者之间只有一条连接,我们称这条边为图中的一座桥,同时也可以进一步得出以下结论。如果没有遍历完 A 中所有的边就通过桥,将无法返回 A 遍历剩余点,因为不能够重复走过桥。因此,我们必须遍历完 A 中的所有边,之后才能够通过桥,去遍历右边的边且不再返回了。

因为需要不重复地遍历所有边,所以我们在走过一条边之后需要把其擦掉,那么就需要做两个 Copy。Copy 1 记录下目前剩下的边,也就是不包括擦掉的边;Copy 2 记录下整个路径,凡是走过的边都染成红色。接下来我们就通过一个例子来具体讲一讲 Fleury 算法。如下图所示,首先我们一定可以根据欧拉定理找到一个起点,F点(任意的)。然后查看 F 点 的邻居 C 和 D,这里我们选择 C。然后再看 C 的邻居 A,D,E,这里我们选择 D。

然后查看 D 的邻居 A,B,F,这里我们选择 A,但是我们并不能选择 F,因为 F 是一座桥,如果去了就相当于进了一个 “ 死胡同 ”。然后从 A 到 C,但不能去 B,因为 AB 是一座桥。接着就更简单了,因为剩余部分就只有一条路了(第六步省略了详细操作过程)。上图和下图为具体的过程,之前提到的邻居(只要不是桥)都是能够选择且存在回路的。

上述做法针对欧拉回路,即全都是偶数点。实际上,有两个奇数点的欧拉路径用的也是类似方法。这里还有最后一个问题,即如何判断是否为桥。其实并不困难,只要做一遍深度优先搜索(宽度优先搜索也行),犹如走迷宫或是倒水一样,看看在去掉这条边之后还是否全部连通。别忘了,以后再做到一笔画的问题,可以试试 Fleury 算法(如果是数学考试的时候,图不是很大),可能会比你手工枚举要快哦。
尾声:一笔画的应用及伟大的数学家
欧拉回路,或是说一笔画问题,不仅仅限制于普通的判断是否存在路线或是寻找路线,还有另外一个用途:增添或删减一些边,使得能够一笔画。这同样需要用到欧拉定理,在此就举些例子吧。夏天,某辆洒水车需要负责一块区域马路的洒水工作,当然,我们并不希望多次对同一条路进行洒水。并且很有可能,我们不能够直接不重复地走遍所有的马路,为了使得开销(走过的马路总长度)最小,需要设计一种走法。如果马路数量过多,可能就要考虑一种优化的办法来求得开销近似的结果。还比如,警车在一个地区巡逻的时候,如何行驶过所有的街道;邮递员每天送报纸,骑车如何经过所有的街道,等等。这样的例子还有很多,都可以用到同样的算法。

最后介绍一下欧拉,他是瑞典杰出的数学家、自然科学家。你一定会觉得他是个全才,还是个天才。不论做那方面的数学或算法题,似乎总会遇到欧拉。他在许多领域都有贡献,数论、代数、微积分、函数、几何学、力学……连数独也是欧拉发明的拉丁方块的概念!至于 Monsieur Fleury,他并不是很出名,是法国人,这个关于欧拉定理的算法在 1885 年才正式被归功于他。

欧拉
一年级奥数启蒙第一讲:看图数一数
一年级奥数启蒙第二讲:组合之谜
二年级奥数启蒙第一讲:图形规律
二年级奥数启蒙第二讲:图形计数
2020重点校小升初模拟题1
备考丨小升初数学试卷2
2020人大附早早培(RDF-ZZP)备考指南:学前儿童家长关注
分享至朋友圈加微信:math1221 获得此答案案打印版及网课咨询
2020海淀区七年级上册数学备考训练1
2020海淀区七年级上册数学备考训练2
2020海淀区七年级上册数学备考训练3
人大附中2019-2020学年度第一学期10月统练2
北京四中2019-2020学年度初三10月阶段性测试
七上 “绝对值几何意义”最全精讲
2018-2019 北京育英中学四年制初一(上)期中数学试卷
2018-2019 北京四中初一(上)数学期中试卷
国庆大放送:初一月考期中备考及希望杯历届真题
不要相信低价课!按需报课!
《中国机长》火了,先别急着给川航点赞!拯救飞机的英雄机长背后,可能有群不负责任的猪队友
70年,北京最高建筑Top5,从天宁寺到中国尊……真的是五环内都能看得到
为何天安门升旗只升28.3米,这是作为中国人你必须清楚的事
校园装修环评质量未过关仓促入学?北大附中实验学校逾百名初中生身体现异常
2019.10.11北大数学金秋营第一天试题及金秋营注意事项
痛心! 高一女生和学长发生关系, 学长讲给同学后流言四起, 女生自杀!
北大教授:别再争论素质教育与应试教育了,真正的敌人是功利主义
牛!请看深圳中学及北京中学的教师配置,真的吓死人!
人大附中2019年开学典礼 1分18秒聪明可爱的早培班学生出境
北大教授: 高收入群体纷纷逃离公立学校, 教育为何让我们如此焦虑年赚8500万的补习班老师,背后是真实的香港
一直上培训班的孩子和一直在玩儿的孩子长大后的区别
教育减负:一场寒门的灾难
我送外孙女去美国,那种内在的力量是我们抗拒不了的
李克强:“卡脖子”问题根子在基础研究薄弱,数学是基础的基础,是其他科学研究的主要工具

在线QQ咨询,点这里

QQ咨询

微信服务号