I don't think you proved the sufficiency in the Euler problem. Counter-example: Imagine two disconnected triangles. 6 points each with 2 degrees. I presume the graph needs to be connected for sufficiency. But video offered no proof even in this case. For the original problem, let U, D, L, R be the number of moves in the Up, Down, Left and Right directions respectively. Then D - U = 2, L = R and U + D + L + R = 17 necessarily, which is impossible. [Q.E.D.] But I indeed enjoy your series very much and I have learned quite a lot. Many thanks.
学了数学之后，我深刻地体会到：有的人活着，他却已经死了；有的人死了，他却不让别人活。
THANATOID Z. 陈独秀同志坐下
特别喜欢你这段话。牛逼。
說得真好XDDD
哇，好哲學，這不就是薛丁格的貓嗎！佩服
副作用 你想多了 他只是在說數學折磨人😂
這題是可以簡單證無解的，方法是用奇偶特性來就。
把毎個點塗上顏色，變成黑白棋盤格狀。可以發現，從黑到白或白到黑，會走過奇數條線；而黑到黑或白到白會走偶數條線。
原問題，編號 1, 3 會是同色，要走偶數條邊。根據植數原理，會走過奇數個點，但全不有 18 個點，故不可能。
也就是說，這題其實是西洋棋騎士問題
但是可以畫出那些空格...
我還是畫出界好了。
缺了对角两个角的国际象棋盘覆盖问题，也是这么涂色能证否。但数学家更加深入，并能带来更多的延伸，甚至创立一个数学分支。
正在想為甚麼沒有人給出這個解………
我需要说明一件事，此农民是数学家退休，问的几万清华北大学生都是体育系这一类的学生，不接受反驳谢谢！
清华的退休数学教授出题考了一下体育生。。。
我猜根本沒有這個農民工的存在，只是吸引大家目光的一個幌子。幾萬個清華北大高材生沒有一個知道這個是無解的??怎麼可能。
如果斜對格也能走的話倒是有很多解。
對，講得好像清華北大高材生沒一個是數學系的
我第一眼以为是IQ题，可以画出方格
学数学和计算机的基本都能知道吧。只能匡一下我们这种文科生
我觉得有没有农民工已经不是重点，而是身份和阶级这种敏感的元素怎么能当做幌子呢？
没看到上面写了不能有斜线?
啊，讲的真的是好，我睡得特别香，比什么ASMR都好使，苟头。
哈哈
入眠神曲
厉害了
你是魔鬼吗
这个农民工的哈密尔顿问题好像有非常容易的解法：
对每个格子给出一个颜色，分别是黑色和白色，左右和上下相邻两个是不同颜色，所以标注如下：
黑，白，黑，白，黑，白，黑，白，
白，黑，白，黑，白，黑，白，黑，
黑，白，黑，白，黑，白，黑，白，
因为不能走斜线，所以走奇数步骤后的格子颜色和初始颜色相反，走偶数步骤后的格子颜色和初始颜色相同。
因为要遍历所有的格子，所以要走步骤数是：(3*6-1)=17，步骤数是奇数，所以起点和终点的颜色如果相反是有可能的，而现在题中给的起点和终点的颜色一致(不是题目中的图，是我画的黑白色图)，都是黑色，所以不可能。
好像有一道小学奥数题是关于在国际象棋棋盘上跳马的问题，也是同样的思路，国际象棋盘天生就是黑白色的，马跳一下也是格子要变一次颜色
度數為奇數的點我們稱為 G點
遍及所有邊，所經路徑為歐拉路徑(奇頂點=0or2) 歐拉回路條件:每個頂點度數為偶數
遍及所有點，所經路徑為哈密頓路徑
關於P=NP:不建議大家在這上面浪費時間 XD
最近在看图论，介绍的清晰简洁，赞一个！
各位兄弟 懶人包在這
12分的片段結論是 無解
我看過另一種證明法是把這些格子化成棋盤格-->起點與終點同色且黑白兩色的數量相同，把經過的每一格的顏色照順序排出來-->黑之後必定是白且白之後必定是黑，要起點和終點同色且兩色數量相當是不能地所以無解(同時解釋為何只有偶數結尾的哈密頓路徑，這裡的基偶數呈棋盤分布可以視為前面假設的兩色) 不過這方式只能證明必定無解而不能證明有解
规则得加一条不允许走到方块外面，不然直接从外面绕
我也是想到这个，规则没写嘛
Mo enen 把平面图形抽象成3D圆柱体，这样子就不会走出格子外，就有解了
我为什么先想到的是 口袋妖怪红蓝宝石冰系道馆的 走格子😂
最后一句才讲到核心。一共18个点要走17步，从奇点出发最后一步肯定踏在偶点，所以“1进-3出”无解。
单就这个问题，可以用数学归纳法证明此题无解。
首先，该问题可重新描述为：在原连通图的基础上裁掉部分边，从而得到一个子图，该子图中除起点和终点的度为1之外，所有其它点的度均为2。
其次，点2的度若变为2，必然裁去（1，2）或（2，3）其中之一。那么最终路径的起始部分和结尾部分必然是（1，2，5，… 6，3）或者（1，4，… 5，2，3）。从而该问题等价于：在去掉最左侧一列的情况下，找到一个（起点4，终点5）或者（起点5，终点6）的路径。此为第一次归纳。
在（起点4，终点5）的情况下，点6仅有的两条边必然全部保留，因此其路径的起始部分和结尾部分必然是（4，7，… 9，6，5）。从而，该问题等价于：在去除左侧两列的情况下，找到一个（起点7，终点9）的路径。类似的，（起点5，终点6）的情况也可以归纳为相同的问题。
因此，原问题等价于：在去除左侧两列的情况下，找到一个（起点7，终点9）的路径。此问题与原问题形式相同且规模减小。此为第二次归纳。
重复使用第二次归纳，立即得出，此问题等价于最右两列，（起点13，终点15）的问题。
又根据第一次归纳，该问题进一步等价于最右一列，（起点17，终点18）或（起点16，终点17）的问题。很显然，最终最小的问题无解，因为除起点和终点之外的那个点只剩下一条边了。
从而，根据数学归纳法，原问题无解。证毕。
使用归纳法，无论问题的列数如何扩展，均可以立即给出答案。
这种类型的哈密顿图，可以用一种通用的方法证明，可以推广到更多格子的哈密顿图。
将所有的格子分别涂成黑白相间的棋盘格（形如国际象棋棋盘）。从而可以发现，从黑色的点出发，只能走到白色的点；而从白色的点出发，只能走到黑色的点。这个图的点共18个点，分别为９个黑点、９个白点。对应的起点是白点，那走的路就是白－黑－白－黑－……－白－黑，即不可能出现起点是白点、终点也是白点的解。
只有3個格子你就破功了
jacky chong 你用腦吧
這證明只能證明「不能走到」，無法證明「可以走到」。另外，假如是三個點互相相連就不能只塗黑白，或許可以塗成三個顏色討論
jacky chong 减少一排也可以，原因影片中和层主也说了，奇数和偶数的区别
减少一排，就只有15个点了，奇数
你的假设，3个点，奇数
但题目是18个点，偶数
陳致穎 这方法也可以证明“可以走到”，但是没有影片中能知道路径。
三个相连的点，意思是像三角形那样吗？
歐拉表示：大家好～我又出現了。
哈哈哈，欧拉：“谢谢大家捧场”
歐拉歐拉歐拉歐啦！
Oooooooh shit
讲得好清楚啊👍
妈咪叔最近刷算法正好刷到哈密顿问题快递员问题，写程序写的头都大了 看了看数学的意义有了更深的理解 对计算机图论也有了更深的理解 谢谢🙏
我相信我對該命題已經有一個十分美妙的解決方法
只是這裡空間太小 寫不下
費馬啊你
多謝分享影片
支持妈咪叔！
看这个视频我一直在想百度地图推荐路径的问题，我们真的是站在巨人肩膀上，很幸运
媽咪老師的科普教學片做得很不錯啊！
很多人已經提出了沒有規定筆畫不能走方格外的限制。
另一個「解」是：它也沒限制那筆劃不可以有多粗！要是即筆劃的闊度足以覆蓋所有橫向格子，那就一筆過向下劃一筆！
这道题根本不需要暴力求解，因为这种正方格子矩阵不是一般化的哈密顿问题，它有特殊性
凡是格子矩阵图，只需要把格子涂成国际象棋盘那种黑白相间格子就行了，这样你会发现每移动一次，必定是从白格走到黑格或者黑格走到白格。于是可以得出结论：对于偶数格子矩阵，要遍历所有格子，起点格子和终点格子的颜色必须相反；对于奇数格子矩阵，要遍历所有格子，起点和终点必须是同一种颜色，且该颜色必须是数量较多的那一种颜色
对于视频中3×6矩阵的图，格子数是偶数，所以起点格子和终点格子的颜色必须相反；而黑白相间格子涂色时左上格和左下格是同色的，故无解
先推再看
李永乐老师有这方面的完美解答
李永乐不是清华的吗？标题明明是农民工难倒清华
成功让我想起，在大学已经还给老师的数学。
好像没有要求不能走到图外吧，去图外绕一圈就能做到了
绕地球三圈w
11:17 一个简便的解释：按照只能横竖走、不能斜着走的走法，从奇数编号点1起始，走到奇数编号点3终止，必然经过n个偶数编号点，(n+1)个奇数编号点（包括起点1、终点3），所以会共经历(2n+1)个点；然而总共有18个点（偶数），所以（起点1，走到终点3）不能遍历此图。也就是说要求（起点编号，终点编号）分别为（奇数，奇数）和（偶数，偶数）的，此图都不能遍历。
你的說話聲音真的很好聽...而且我居然能聽得懂...我天生患有理論障礙症似乎在你這邊解決了
他的規則只說1.要走完全部格子2.不能走斜線3.不能重複走同一格子，但沒說不能超出格子
話說媽咪叔可以展示一下如何 construct a reduction from Travelling salesman problem to Hamiltonian path problem 嗎？
想请问一下 玻璃 水晶 钢化玻璃和普通玻璃有什么区别呢
fully support your work
这种特殊的图其实有更简单的证法，不需要暴力破解。
①观察可知其标注奇数的点移动一次必然到达标注偶数的点，同样标注偶数的点移动一次必然到达标注奇数的点。
那么将原本标注奇数的点重新标注为1，原本标注偶数的点重新标注为-1，计算路径所经过点的点数之和。
可知若起点为奇数点，那么路径所经过的点所标注的数字之和要么为0+1=1(停在奇数点)要么为1+(-1)=0(停在偶数点)，即只有1和0两个值。
同样若起点为偶数点，那么只有-1和0两个值。
②已知图中共有9个奇数点和9个偶数点，所有奇数点和偶数点的点数之和为0，即若存在路径能够遍历所有点则点数之和必为0。
③那么如果存在一条能够遍历所有点的路径最后一个点为奇数点，则意味着路径在到达最后一个点时已经遍历了除最后一个点以外的所有点，即路径点数之和为0-1=-1
但在起点为奇数点的情况下路径之和只能为1或0，不存在出现-1的情况，所以假设不成立，即不存在从奇数点出发回到另一个奇数点的路径。
我不知道我这样说你听懂了没？
所有哈米頓路經不難得出, 只是電腦難算而已
如果用AI求解, 不算訓練時間的話, 求解時間N應該不在指數的範圍
當然, 也可以說, 人腦的解部份NPC的問題等於N, 而電腦不行
這片也看懂了 好爽
请问P=NP和快递员的视频在哪？求链接。多谢！
有一个很简单的方法证明无解：将棋盘黑白交错染色。显然起点和终点同色。然而一笔路径必须是黑-白-黑-白顺序而行，所以若有一笔路径起点终点必须异色。矛盾。
简而言之，应该就是搭建黑白棋棋盘方格阵：若起终同色点走全路径，长乘宽的积（格子总数）若为偶数则无解；若起终异色点走全路径，长乘宽的积若为奇数则无解。
最喜欢妈咪叔关于数学的视频🙂
讲的好干，放入助眠分类了
是我想错了么？没明白哈密顿的意义在哪里，从运动轨迹来理解点和边的概念是可以完全互换的，有什么区别呢？
NPC問題很多人想破頭也無解，其實只要耐著性子等官方更新就行了。
哈哈哈哈哈 我tm听数学老师讲课都没这么认真过
把解法法过来看看呢想看你的程序咋解的哈
不能划出格子吗？
從外面走，可以過，Easy
没说不能走格子外绕圈圈啊，哈哈哈
有机会能不能说些化学方面的故事会？谢谢
而且，寻找任意图的哈密顿路径都是NPC问题…… 不仅仅是有条件的哈密顿路径
看了这个视频，我决定明天早餐去吃茶杯，不，是吃甜甜圈……
這個頻道會紅！
改變 空間 維度🤣
算法课基本知识：求最优解是NP-Hard问题，P，NP，NP-Complete都是Decision Problem，就是答案为是或否
厉害了
I don't think you proved the sufficiency in the Euler problem. Counter-example: Imagine two disconnected triangles. 6 points each with 2 degrees.
I presume the graph needs to be connected for sufficiency. But video offered no proof even in this case.
For the original problem, let U, D, L, R be the number of moves in the Up, Down, Left and Right directions respectively. Then D - U = 2, L = R and U + D + L + R = 17 necessarily, which is impossible.
[Q.E.D.]
But I indeed enjoy your series very much and I have learned quite a lot. Many thanks.
Plz notice the constrain: a CONNECTED unidirectional graph.
@@alenpete8480 Thanks Pete. That's what I thought.
這讓我想起2年前買了本關於圖論的書
結果到現在一頁都沒看過。。。
说的非常好，如果可以的话，像我们这些小白，多配一点图文解说，会更容易理解一点！ 这样说有点晕晕，哭哭！...
是說NPC問題你能找出最優算法肯定不只一百萬，基本上全球的大型物流類型的公司都會追著你跑.......
可以啊 往格子外畫就好了 只是讓把格子填滿 沒有說不能出格吧
其实这是一道小学奥数题，，当时教的数几条线交点的个数奇数偶数之类的，，
畫成黑白棋棋盤的顏色，起點終點都是黑色格，要移動到同色格，扣掉起點要移動偶數次，但這裡有3×6=18格，扣掉起點要走17步才能走完全部，終點絕對是在白色格。
一眼就看得出來的東西，要吹成難倒清華北大高材生？有點可笑
鄰接矩陣 要怎麼導入計算機去計算路徑呢？
求大神解惑
或是程式碼概念
Q_Q
How to transfer the adjacency matrix into all of the possible paths?
Jahlun Lai 用ampl来解 算法忘记了 可以自己学一下
这题也没说不让把线画到格子外面去啊
P和nP问题，能否有这样一个思路。比如求物体重心，这本来是一个数学问题，但可以有物理的解法，同样的，复杂的np问题是否也可以被大自然在物理世界中解决，而不必通过形式系统
看到这题直接想到深度优先去遍历，看看是否能够从起点走到终点同时把 boolean [][] visited全用光
連通圖是指每個點都能有一條路徑與其他點相連，意即不存在兩點無法連結
衣服 很有特色
终于能看懂欧拉的思想一次了
如果快遞員能找到所有快遞的最短路徑，那他就不會只是個快遞員了
所以應該設定是快遞公司老闆
单就这个问题是很容易证明无解的，不需要暴力计算
注意到以下事实：每往下走一步，必然会改变奇偶性，也就是从奇数点出发走一步，只能到偶数点，不可能走到奇数点，反之亦然
总共18个点，想要遍历，要走17步，你既然从1出发，那17步后无论如何都会走到偶数点上，不可能到3这个奇数点
完蛋 早知道就學好線性代數了...
鄰接矩陣看不懂...
感觉我要活在那个时代说不定也能想出来这种论证
很簡單~這題問題並不是沒有解的！
乎合以上條件的方法就是用一支足夠粗的筆畫
其中兩個 頂點是奇數也可以破
小学生的题，黑白棋盘分割，不可能奇数步到同色方块。
讲的挺好的，为什么100多dislike?难道是100多北大清华的来点的？
嗯，那十倍的赞，一定都是农民工点的了…
就喜欢看你们这些抬杠的😂
他沒說走到終點不能繼續走( ´_ゝ`)
之前P=NP问题那期视频怎么不见了
我发现每一句话后面都是“嗯, 啊”
Wayne Li 主要是开始一句话吸气声音太响了，需要改观
Wayne Li 被大学老师传染了😄希望能改进吧
你发现了奇点
这个视频还没点进来，我看着那张图大概三四分钟就想好答案了
P=NP....终于把民科们招来了吗？
我们之所以理解“点”理解为“点”，基本是因为运动终止于点，那我们可不可以这么理解，如果画线的运动终止于“边”，同样也可以把这个“边”理解为“点”。我们所谓的“点”和“边”是为了方便理解人为下的定义，并不影响其属性，概念互换也不影响原理，所以所谓的“哈密顿”有什么价值呢？
这道题是有解的。因为并没有说不能走到格子外啊，从外面绕一下就可以了，很简单。变成数学题的话，加个条件4，只能走格子。
哈哈 厉害了
我也這麼想，之前有國小老師出過類似的題目，然後說我們都侷限在框框內了
连通图的定义是任意两点之间都有路径，并不是每点都有边，每边都有点（这半句其实是废话）
跳出柜柜就畫到了,我聰明嗎?
打救打救世人吧!
可以解呀，直接画就能出来
这么好的频道，为什么有人踩？
媽咪叔，這個問題是有方式解的，只要用棋盤格就可以了，而且如果您有發現，你的所有單數點塗同樣顏色，偶數點塗同樣顏色，問題就解決了，我沒有記錯的話應該是換位置問題：「有一個位置為方格的教室，是否所有人都可以換到與之前相鄰的位置」直接處理基偶性就解決了。但我忘記是叫做什麼問題了
我记得图存在哈密顿回路也是NPC啊，不一定再满足什么要求
同意，不用到TSP問題，即便只是問圖是否含有哈密頓路徑就已經是NPC問題了。
林更新你怎么做起兼职了？
有解,题目没有要求不能画出方块外面
這七橋問題第一次遇見是在資料結構
類似加法原理嗎？
又没说不能走到格子外面 题干本身就很有问题
这个cs算法题能解吗
單就農民工的這道題，有紙筆證明方法。
以下提出我的方法，供大家參考及審查，
大家可以邊看邊用紙筆畫下來幫助理解。
令起點為S 終點為E 兩者之間的點為M，
(也就是媽咪叔講的點1,2,3，我稱為S,M,E)
令路線前進方向 左: l 右: r 上: u 下: d
從S,E分別出發一條路線，可對接成一條路徑，
由S,E在角落，可討論局部的路線情況，
S出發的路線A 只有 r , d 兩種前進方向，
E出發的路線B 只有 r , u 兩種前進方向。
路線(A,B)有4種可能的開頭，(r,r) (r,u) (d,r) (d,u)
其中(d,u)完成了對接，而所成路徑不合題設，
(r,r)將M孤立，任何潛在路徑必不滿足題設，
(r,u) (d,r) 上下對稱，討論其中一個即可。
設(A,B)=(r...,u...)，可接續推得下列路線情況:
(r...,ur...)--> (rr...,ur...)--> (rr...,urd...)--> (rr...,urdr...)
(xy表示該路線走了一步x方向後再走一步y方向)
可知路線(A,B)的前幾步必為(rr,urdr)，
設路線(A,B)到達了S',E'，為新的起點、終點，
問題從3x6簡化為3x4，重複推理得到3x2。
最後3x2的圖形，路線A,B會完成對接，
所成路徑不合題設，故不存在滿足題設的路徑。
這個方法配合遞迴可以判定所有3xn的方格圖，
n是奇數則有解，n是偶數則無解。
结果都一样，你说这些的意义何在呢？
@@user-dd6fq9pi3c
知道了結果，也需要進一步思考，
有沒有其他方法? 可以怎麼樣推廣?
我覺得這對於數學問題來說是重要的。
把想法寫下來可以使我的思考過程更完整，
同時分享方法給喜歡知道更多、研究細節的人。
充實自己的學習，也給影片內容一點補充。
還有一個好處是，我的論證如果有疏忽，
互相交流，可以對問題研究得更深刻、更完善。
不錯，你寫得非常清楚