猜一猜，下面哪张图是一笔画不成的？

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

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万的补习班老师，背后是真实的香港
一直上培训班的孩子和一直在玩儿的孩子长大后的区别
教育减负：一场寒门的灾难
我送外孙女去美国，那种内在的力量是我们抗拒不了的
李克强：“卡脖子”问题根子在基础研究薄弱，数学是基础的基础，是其他科学研究的主要工具