（每日一题）与“七桥问题”再回到前面的宝藏收集问题

——拉普拉斯

1. 如何设计路线

前两天，一位朋友在群里讨论了以下问题。

这让我想起了春节期间我一直在思考的问题。 大年初一，我要给长辈们拜年。 从我家出发，我先去姨家、二姨家、姐夫家、姐夫家，然后再去嫂子家。晚餐。 （每间屋子的位置图如下。） 每间屋子我只能经过一次吗？ 终于到嫂子家了？

简单的尝试告诉我们，这似乎行不通，但能否给出严格的数学证明又是另一回事了。 这个特殊问题可以这样想：以 0-1 间隔标记顶点，那么任何路径都将以 0-1-0-1 间隔。 图中一共有6个点，3个0，3个1。 起点是0，如果我们想全部遍历一遍而不重复，那么最后一个肯定是1，但是我嫂子家的标记是0，所以不可能。 而如果你最终在你姨家吃饭，那么有一条可行的路径：你自己家-->你二姨家->你姐夫家->你姐夫家->你妹妹- 婆家-> 你姨妈家。

2.欧拉和“七桥问题”

回到之前的寻宝问题，大多数人尝试了一下，觉得放弃4可以遍历所有节点，但只放弃3不行（8成为度数为1的挂点）。

但为什么不把它们都经历一遍呢？ 老王又出现了，说因为奇数点不是2，不能一笔画出来，所以无法遍历。 但这一次，是老王带头了。

一笔画问题属于著名的欧拉图问题。 无独有偶，它也来源于生活。 据说柯尼斯堡有两个岛屿和连接它们的七座桥梁。 普雷格河流经市内的两个岛屿。 岛屿与河岸之间有六座桥梁，还有一座桥梁连接两个岛屿。 岛上有古老的柯尼斯堡大学、一座教堂以及哲学家康德的坟墓和雕像。 因此，城市居民，尤其是大学生，经常沿着河边、过桥散步。 有一天，一个好奇的人问了一个问题：一个步行者是否可以一次走过7座桥，并且每座桥只允许通过一次，最后回到起点。 这就是七桥问题。

这个问题看似简单，但很多人都尝试过却始终找不到答案。 于是，一群大学生写信给当时年仅20多岁的伟大数学家欧拉，请他分析一下。 没想到这个问题影响深远，开创了数学中图论和拓扑的分支！

欧拉用简单的几何图形来表示土地和桥梁，如图“七桥连线”所示，于是七桥问题转化为能否遍历图中所有边一次，且只能遍历一次。 经过一番研究，他提出了图可遍历（或称为笔画）的充要条件：

(1)图形必须是连通的。

(2)图中“奇异点”的数量（即与顶点相连的奇数条边）为0或2。

如果图中奇异点的个数为0，则可以一笔画完回到原点，对应的路径就是欧拉环。 而如果奇异点的数量为2，则可以一笔画出，但无法回到原点。 七桥问题之所以无解，是因为它有四个奇点。 直观地想一下，如果想要遍历所有边而不重复，那么所有既不是起点也不是终点的节点的连通边数必须是偶数（一进一出必须匹配） ）。

以前看到一位老师写汉字和一笔画，觉得挺有趣的。 有兴趣的读者可以尝试一下。 日文、中文、川、木、虫等汉字能一笔画出来吗？ 英语也有类似的问题，比如能否一笔画出26个大写英文字母？

3. 哈密尔顿图与欧拉图

你清楚新年问题和七桥问题之间的区别吗？ 一种是所有点都遍历一次，一种是所有边都遍历一次。 这两个看似相似的问题实际上有着本质的不同。

其实所有节点是否都能被遍历一次也是一个著名的图论问题，称为“汉密尔顿问题”，即图中所有相邻边都是0-1。 我们之前证明拜年问题没有遍历路径，实际上是利用了图的特殊性，即标注。 边上不存在同时使用相同标签的两个顶点。 但现实中，这样的图片大量存在。 只要是边数为奇数的多边形（如三角形、五边形），就不能用上述方法进行标记。 要判断这样一个图是否可以遍历一次所有顶点，需要更深厚的图论知识。

回到一开始的收宝问题，由于图中不存在奇数边的多边形，所以可以用0-1交替的方式来标记。 由于起点为0，终点为0，任意路径都是0-1-0-1交替出现，所以必须遍历所有节点（8个0，8个1），最后一个应该为1，所以不能穿越。

前段时间，甄提出暑假去旅行，去很多地方。 如果你有足够的时间和资金，你可以围绕这个设计一个类似的游览问题。 比如下图中，有没有一条从南京出发，经过所有城市一次且仅一次，然后返回南京的出行路线？ 或者有没有一条从南京出发，经过所有城市一次且仅一次，最终到达成都的旅行路线？

欧拉被公认为数学史上最伟大的四位数学家之一，与阿基米德、牛顿、高斯并列。 他不仅对数学做出了巨大贡献，而且将数学应用到了几乎整个物理学领域。 他是科学史上最多产、最杰出的数学家之一。 据统计，他在孜孜不倦的一生中，共撰写了886篇书籍和论文。

欧拉对数学的贡献涵盖了从数论、函数、微积分到图论的许多领域。 正是因为他贡献如此之大，所以当我们谈论欧拉公式时，我们不禁会问：等等，你说的是哪一个欧拉公式？

在图论领域，除了著名的七桥问题外，还有一个著名的欧拉公式：在任意正球面地图上，用R记录区域数，用V记录顶点数， E 记录区域数量。 边界的数量为R+VE=2。 这是什么意思？ 我们可以用一个立方体来简单解释一下。 立方体有 8 个顶点 (V=8)、6 个面 (R=6)、12 个边 (E=12)、8+6-12=2。

当然，说到欧拉，就不能不提证明上帝确实存在的欧拉公式：

爸爸说奥数公众号二维码