农民工 一道 题 难倒 百万 人 ？一 笔画 问题 与 哈密顿 问题 该 怎么 解？ Migrant workers have a problem that stumped millions of people? How to solve the one-stroke problem and the Hamiltonian problem? ¿Los trabajadores migrantes desconciertan a millones de personas con una pregunta? ¿Cómo resolver el problema de un golpe y el problema hamiltoniano? Трудящимся-мигрантам трудно решить один вопрос для миллионов людей? Как решить проблему одного удара и проблему гамильтониана?

妈咪 说 知识 就是 力量 大家 好 我 是 妈咪 叔 Mommy says knowledge is power, everybody. Okay, I'm, uh, Uncle Mommy. Mami dice que el conocimiento es poder Hola a todos, soy el Tío Mami

前 几天 有 同学 给我发 私信 问 了 一个 一 笔画 的 问题 A few days ago, a classmate sent me a private message asking a one-stroke question. Hace unos días, un compañero de clase me envió un mensaje privado haciéndome una pregunta sobre la pintura de un solo trazo.

说 这道题 研究 半天 也 没画 出来 I've been working on this problem for half a day, but I can't figure it out. Se dice que esta pregunta ha sido estudiada durante mucho tiempo y no ha sido dibujada.

问 我 有没有 解 pregúntame si tengo una solución

还 说 这 是 一位 农民 伯伯 出 的 题 说 难倒 了 好多 人 He also said that a farmer's uncle asked the question, and said that it was difficult for a lot of people. También dijo que esa era una pregunta que le hizo un tío de un agricultor y dijo que dejó perplejos a muchas personas.

说实话 这道题 水 还 真 挺 深 的 To be honest, it's a pretty deep question. Para ser honesto, esta pregunta es muy profunda.

首先 它 的 答案 是 没有 解 First of all, the answer is no. En primer lugar su respuesta es que no hay solución.

就是 正常 解法 画 不 出来 It's just that the normal solution doesn't work. Es solo que la solución normal no puede dibujarlo.

你 别说 什么 对折 斜 着 画 啥 的 啊 那 不算 Don't say anything about folding and drawing diagonally, that doesn't count. No digas nada de doblar por la mitad y dibujar oblicuamente, eso no cuenta.

其实 这道题 不是 一 笔画 问题

它 是 一道 哈密顿 问题

别着急 咱们 先 来说 一 笔画

一 笔画 问题 肯定 大家 都 接触 过 The question of strokes is one that I'm sure we've all come across.

但是 大家 也 别 觉得 哎呀 好 简单 啊 But don't think it's so easy.

小学 奥数 我 就学 过

一 笔画 问题 可是 数学 当中 图论 的 鼻祖 The stroke problem is the originator of graph theory in mathematics.

最早 解决 这个 问题 的 人 正是 数学 大神 欧拉

欧拉 解决 的 问题 就是 著名 的哥 尼斯 堡七桥 问题 The problem Euler solved was the famous problem of the Seven Bridges of Gönigsberg.

那 咱们 就 一起 来看 一下 是 咋 回事 Well, let's take a look at what's going on.

先 来 讨论一下 什么样 的 一 笔画 有解

什么样 的 一 笔画 没有 解 呢

话 说 当年 古 普鲁士人 有 这么 一处 定居点 叫做 特旺 斯特 It is said that in those days there was a settlement of the ancient Prussians called Twente.

后来 这个 地方 被 条顿 骑士团 征服 了 改名 为哥 尼斯 堡 Later, this place was conquered by the Teutonic Knights and renamed Gönigsberg.

再 后来 哥 尼斯 堡 几经 转手 And then, later on, Gönigsberg changed hands.

到 了 二战时期 被 苏联 占领 了

战后 英美 苏三国 就 商量 都 想要 点 啥 After the war, the British, the Americans, and the Soviets all agreed on what they wanted.

于是 仨 人 合伙 签订 了 一份 《 波茨坦 协定 》 So, the three of them teamed up and signed the Potsdam Agreement.

根据 这份 协定 哥 尼斯 堡 就 归 苏联 所属 了 In accordance with this agreement, Gönigsberg is now part of the Soviet Union.

苏联 把 哥 尼斯 堡 改成 了 加里宁格勒

到 现在 也 是 俄国 的 领土

你别 看 人家 俄罗斯 整体 都 在 东欧 Don't look at me, but Russia, as a whole, is in Eastern Europe.

人家 在 中欧 也 有 一块 领土 就是 加里宁格勒 They also have a territory in Central Europe, Kaliningrad.

现在 谁 要 也 不能 给 了 是 吧 哪 哪 都 在 射程 Now, no one wants it, no one can give it. Yeah, right. Everywhere, everywhere.

咱们 之前 总提 的 大 数学家 希尔伯特 就是 出生 在 曾经 的哥 尼斯 堡 The great mathematician Hilbert, whom we've mentioned before, was born in what used to be Gönigsberg.

好 言归正传 Okay, back to business.

说哥 尼斯 堡 这个 地方 中间 是 两座 小岛 It says, "Gonesburg, this place, in the middle of it, are two small islands.

被 几条 河 分开 了 Separated by a couple of rivers.

岛 与 陆地 之间 的 连接 有 这么 七座 桥 There are seven bridges connecting the island to the land.

这 七座 桥 几乎 是 每天 哥 尼斯 堡 人 的 必经之路 These seven bridges are used almost every day by the people of Gönigsberg.

于是 人们 走 着 走 着 就 在 民间 流传 着 一个 问题 And so, as they went along, there was a question circulating among the people.

说 能 不能 在 哥 尼斯 堡 内 任何 一个 地方 出发 Say if you can start from any place in Gönigsberg.

然后 途径 这 七座 桥 And then, by way of these seven bridges.

且 每座 桥 只 经过 一次 然后 能够 回到 原点 呢 ？

就是 有没有 这么 个 地方 和 相应 走法 That is, is there such a place and a corresponding way to go?

你 看 每座 桥 只 经过 一次 有点 一 笔画 的 意思 吧 ？

哥 尼斯 堡 人 走 了 好些 年 隐约 感觉 做 不到 The people of Gönigsberg have been gone for years with a vague feeling of not being able to do it.

但是 又 不能 确定 But, uh, we can't be sure.

于是 据说 是 当时 有人 给 欧拉 写 了 一封信 求助 So, the story goes that someone wrote a letter to Ola asking for help.

也 有 一种 说法 是 欧拉 听说 了 这个 问题

反正 欧拉 是 知道 有 这么 个 事儿 了 Anyway, Ola knows about it.

这是 1735 年 的 事儿 欧拉 28 岁

正在 俄罗斯 圣彼得堡 科学院 帮着 画 地图 I'm helping draw maps at the St. Petersburg Academy of Sciences in Russia.

然后 右眼 失明 了 这 一年 And then he went blind in his right eye for a year.

欧拉 一看 这个 问题 不错

于是 转年 也 就是 1736 年 就 在 圣彼得堡 科学院 发表 了 一篇 论文 So the following year, in 1736, he published a paper at the St. Petersburg Academy of Science.

名为 《 哥 尼斯 堡 的 七桥 》

明确 证明 了 此题 无解 Clearly proves that the problem is unsolvable.

不仅如此 欧拉 还 给出 了 此类 题型 的 通解 Not only that, but Euler gives a general solution to this type of problem.

就是 什么样 的 一 笔画 有解 什么样 的 一 笔画 没解 呢 ？

正是 欧拉 的 这篇 论文 发展 成为 了 现在 的 图论

欧拉 是 这么 考虑 的 Well, Ola, here's what he's thinking.

河流 把 哥 尼斯 堡 分成 了 四个 部分

就是 四块 陆地

这 四块 陆地 你 随便 选 一个 作为 起点

然后 你 会 发现 无论 你 从 这 上边 哪 出发 都 是 一样 的 And then, you'll realize that no matter where you go from here, from up here, it's the same.

所以 我们 就 可以 把 四块 陆地 抽象 成 四个 点

反正 从 哪 走 都 一样 嘛

那 联通 这 四个 点 的 就是 这 七座 桥 啊

所以 欧拉 第一步 就是 把 哥 尼斯 堡 的 地形图

抽象 成 了 四个 点 七条 线 的 连通 图 Abstracted into a connected graph of four points and seven lines.

那 现在 哥 尼斯 堡七桥 问题 就 变成 了

这个 图形 能否 从 其中 一点 出发 一 笔画 成 还要 回到 原点 呢 ？

你 看 简洁 多 了 吧

其实 这种 思想 就是 拓扑

你们 听过 在 数学界 有 一个 冷笑 话 吧

说 在 数学家 眼中 一个 茶杯 和 一个 甜甜 圈 是 等价 的 Say that in the eyes of a mathematician a teacup and a donut are equivalent.

因为 它们 可以 相互 拓扑 而成

搞笑 是 吧

咱们 来看 这个 图 啊

这个 图 在 图论 中 叫做 无向 连通 图 This graph is called an undirected connected graph in graph theory.

无向 就是说 边 是 没有 方向 的

如果 你 规定 每条 边 只能 往 一个 方向 走 就 叫做 有向图

那 所谓 连通 就是 每个 点 必定 有 边 连接

每条 边 也 必定 有点 连接

很 好 理解 对 吧

图中 每 一个点 上 的 连 线条 数 叫做 这个 点 的 度

有 几条 连线 这个 点 的 度 就是 几

理解 吧 ？ 好

那 我 现在 说 一个 命题 你们 看 对 不 对 哈

对于 任意 一个 连通 图 来说

所有 点 的 度数 之 和 必定 是 偶数 对 吗 ？ The sum of the degrees of all points must be even, right?

因为 每条 边 必定 连接 两个 点

也 就是 每条 边 给 这个 图 贡献 的 度数 是 2

那 假设 有 n 条边 连通 图 的 总 度数 就是 2n

一定 是 偶数 明白 吧

接下来 欧拉 是 这么 考虑 的

说 你 想 从 某 一点 出发 经过 七座 桥 再次 回到 这 一点

那 我们 简单 理解

对于 每 一个点 来说 是不是 有 进必 有 出 啊 ？ For every point, is there an in and an out?

你 看 对于 其他 的 点 要 先 到达 然后 离开 一进 一出

对于 起点 来说 先是 离开 最后 又 回来 了

还是 一进 一出

说明 了 什么 呢 ？

说明 了 无论 你 经过 某个 点 几次

这个 点 的 度数 只能 是 偶数

也就是说 对于 哥 尼斯 堡七桥 问题 如果 想要 有解

四个 点 的 度数 必须 都 是 偶数

那来 吧 再 看 一眼 哥 尼斯 堡 的 连通 图

你 发现 四个 点 的 的 度数 都 是 奇数

证毕 所以 欧拉 说 此题 无解

到 这 还 不行 如果 我们 放宽 条件 呢 ？

我 现在 不 要求 回到 原点 了

只要 是 能 一次 走 完 七座 桥 就 行 有没有 解 呢 ？ Is there any solution as long as the seven bridges can be completed in one go?

欧拉 说 还是 没有 为啥 呢 Ola said, "No, why?

因为 度数 为 奇数 的 点 我们 简称 为 奇点

它 只能 出现 在 起点 或者 终点 It can only be at the beginning or the end.

中间 的 点 一定 得 是 偶点 The point in the middle must be an even point.

你 笨 想起 点 可以 一出 终点 可以 一进

但是 中间 的 点 必须 还 得 是 一进 一出

所以 欧拉 又 得到 这样 一个 结论 So, Euler, again, comes to this conclusion.

要 想 一 笔画 奇点 个数 只能 是 0 或者 是 2

如果 （ 奇点 个数 ） 是 2 那么 必须 一个 是 起点 一个 是 终点 If (number of singularities) is 2, then one must be the starting point and one the ending point.

哥 尼斯 堡 连通 图 四个 点 全部 是 奇点

所以 放宽 条件 仍然 无解

有 同学 说 奇点 不能 是 1 个 或者 3 个 吗 ？ Did someone say that there can't be 1 or 3 singularities?

不能

因为 刚才 咱们 证明 了 一个 连通 图 总 度数 必须 是 偶数

如果 奇点 是 奇数 个 那 总 度数 就是 奇数 了

不行 你 也 画 不 出来 这样 的 图

好 咱们 来 总结 一下

在 图论 当中 能够 一 笔画 的 图

用 数学 语言 就是 能够 遍历 所有 边 而 没有 重复 的 图

叫做 欧拉 图

你 一 笔画 的 这个 路径 就 叫做 欧拉 路径

如果 这个 路径 是 闭合 的

啥意思 啊 就是 原始 的 七桥 问题 What do you mean? The original Seven Bridges.

能够 回到 原点 的 这种 路径 叫做 欧拉 回路

以下 是 结论

对于 一个 无向 图 来说

存在 欧拉 回路 的 充要条件

就是 回到 原点 的 这种 一 笔画

要求 每个 顶点 的 度数 必须 是 偶数

放宽 条件 存在 欧拉 路径

就是 可以 不 闭合 的 这种 一 笔画 的 充要条件 是

奇 顶点 的 个数 等于 0 或者 2

注意 哦 这 都 是 充要 的

明白 了 吧 ？

所以 以后 谁 要是 问 你 某个 图能 不能 一 笔画 啊 ？

首先 查奇 顶点 个数 First, look up the number of vertices.

如果 不是 0 或者 2 直接 优雅 的 告诉 他

此图 并非 欧拉 图

至此 咱们 的 疑问 解决 一半 了 So we're halfway to solving our problem.

但是 欧拉 还 在 继续 研究

欧拉 在 想 说 哥 尼斯 堡 图 有 四个 奇点

那一 笔画 不成 最少 几笔 能 画成 呢 ？

欧拉 又 给出 了 定理 二 ：

如果 一个 无向 图有 2n 个奇 顶点

那么 它 至少 需要 n 笔画 成 Well, it takes at least n strokes to form

所以 哥 尼斯 堡图 至少 需要 画 两笔

终于 算 解决 了 是 吧

哥 尼斯 堡 人 听说 之后 高兴 坏 了 The people of Gönigsberg were overjoyed when they heard about it.

再也 不用 天天 溜达 了 I don't have to sneak around every day anymore.

那 为啥 说 咱们 的 问题 才 解决 一半 呢 ？ Then why do you say that only half of our problems have been solved?

我们 回过头来 看 最 开始 的 问题

现在 你 的 第一 想法 肯定 是 我 也 把 这个 图 拓扑 一下

把 每个 小 方格 给 它 抽象 成 一个点

每个 点 之间 用线 来 连通

于是 这个 图 就 变成 了 这样

可是 咱们 的 问题 并 不是 这个 图能 不能 一 笔画 啊

如果 要是 这个 问题 这道题 就 简单 多 了

你 一查 奇点 个数 有 十个

直接 得出 答案 此图 并非 欧拉 图

但是 你 发现 这道题 不 一样

哪 不 一样 呢 ？

对于 一 笔画 问题 我们 只 考虑 的 是 遍历 所有 边

至于 点 你 走 几遍 这是 无所谓 的 As far as the point of you going over it a couple times, it doesn't matter.

但是 这道题 是 我 要 遍历 所有 点

至于 边 你 走 不 走 是 无所谓 的

点 就是 原来 的 小 方格 嘛

要求 是 所有 小 方格 只能 走一遍

能 明白 这个 逻辑 吧 ？

它 正好 反过来 了

那像 这样 和 欧拉 图 刚好 反过来 的 问题 就 叫做 哈密顿 问题

这是 1856 哈密顿 提出 来 的

就是 对于 一个 图能 不能不 重复 的 遍历 所有 顶点 呢 ？

如果 能 这个 图 就 叫做 哈密顿 图

每 一种 走法 就是 一个 哈密顿 路径

比如说 对于 这个 图 来说 我 就 可以 画 一个 S 形 遍历 所有 顶点

那 这个 S 形 的 路径 就是 一个 哈密顿 路径

同样 如果 路径 是 闭合 的 就 叫做 哈密顿 回路

你 会 发现 感觉 好像 容易 多 了 呀 You're gonna find that it feels like it's a lot easier.

是 随便 找 一条 哈密顿 路径 好像 不难

但是 如果 让 你 寻找 某个 特定 的 哈密顿 路径 就 不 那么 容易 了

比如说 这道题 我 规定 了 起点 和 终点

你 看 有 要求 了 You see, there's a request.

再 比如说 咱们 之前 再 讲 P=NP 的 问题 当中 介绍 过 一个 快递 员 问题

说 有 一个 快递 员 想要 派送 50 个件

这 50 个件 地理位置 他 都 知道

那 他 如何 寻找 一个 一次 送 完 所有 快递 的 最 短 路径 呢 ？ So how does he find the shortest route to deliver all the couriers at once?

这 不 就是 遍历 所有 点 嘛

也就是说 寻找 一个 最优 的 哈密顿 路径

这种 题 是 典型 的 NPC 问题 This kind of question is a typical NPC question.

也 就是 在 多项式 时间 内 无法 完成

这 就是 开篇 说 的 这道题 水 很 深 的 原因

它 就是 一个 典型 的 NPC 问题

有 同学 说 那 妈咪 叔 你 怎么 还 明确 的 说 此题 无解 呢 ？

好 在 它 点 不 多 啊 Good thing it's not too much.

我 没有 简单 解法 我 还 不能 暴力 求解 吗 ？

NPC 问题 并 不是 说 不能 解

只是 它 的 时间 复杂度 一般 都 超级 高 It's just that its time complexity is generally super high.

如果 基数 大 一点 用 计算机 也 很 困难 是 吧

那 这道题 还好 一共 就 18 个点 呗 So, it's okay. It's only 18 points.

首先 把 每个 点 编个 号 1 到 18

然后 改写 成 邻接矩阵 的 形式

再用 计算机 计算 一下 这个 图 所有 的 哈密顿 路径

就 是从 哪进 从 哪出 都 无所谓

只要 能 不 重复 的 走过 所有 点 就行了

我 计算 了 一共 是 672 条

然后 再 从中 挑选 符合要求 的 And then, we'll pick the ones that fit the bill.

也 就是 起点 得 是 1 终点 得 是 3 的 路径

答案 是 没有 The answer is yes, no.

也就是说 你 想要 找 一条 起点 是 1 终点 是 3 的 哈密顿 路径 找 不到

所以 我 敢肯定 的 说 此题 无解

但是 有 很多 有趣 的 发现

比如说 起点 如果 规定 是 1

一共 有 78 条 哈密顿 路径

这 78 条 路径 的 终点 全部都是 偶数 All 78 routes end in even numbers.

也 就是 你 想 从 1 出发 不 重复 的 遍历 所有 点 That is, you want to start at 1 and go through all the points without repeating.

回到 任意 一个 奇数 点 都 是 无法 做到 的 Going back to any odd number of points is impossible.

这里 边 说 的 奇数 点 就是 我 标号 的 这些 点哈

然而 起点 是 1 终点 随便 选 一个 偶数 都 有 相应 的 走法 However, the starting point is 1, and the ending point is any even number, and there's a corresponding way to go.

你们 可以 自己 试一下

至此 这位 同学 的 问题 是 终于 解决 了 This student's problem is finally solved.

现在 有 同学 肯定 是 这么 想 的

说 哎呀 那 我 要是 找到 了 寻找 哈密顿 路径 的 最优 算法

没准 就 解决 了 P=NP 问题 了 呀

理论 上 是 而且 你 还 能 得 100 万 呢

但是 不 建议 大家 在 这 上面 浪费时间

之前 还有 朋友 给 我 留言 说 解决 了 P=NP 问题 的 A friend left me a message saying that the P=NP problem had been solved.

这个 P=NP 并 不是 一个 数值 等式 This P=NP is not a numerical equation.

P 和 NP 都 不是 一个 具体 的 数

它们 表示 的 是 一种 类型 的 问题

还是 建议 感兴趣 的 同学 可以 去 看 一下 之前 那 期 视频

今天 就 不 多 说 了

好 感谢 各位 关注

我 是 妈咪 叔 一个 较真儿 的 理工 男

下期 见 拜拜