一道思索数年的小学题目一. 一段经历: 思考数年的问题
初中时，妹妹问了我一个问题：
如下图，相邻2点的间隔是1，只能横连和竖连（当然，间距只能是1），你能一笔把这些点都连起来吗（不重复）？如果能，请，给出连的结果；如果不能，请给出理由.
当时我苦思冥想都没得到一个合理的结果来。直到进入高中后的某一天，我恍然大悟...
二. 数学转换
现在，我们把他转化成一道正规的数学题吧:
Does this graph have a Hamilton Path?
三. 一点引申:
Does this graph have a Hamilton Path?
试问：你能给出一个人人都懂的答案吗？
[冷色蓝天 (5-30 15:05, Long long ago)]
[ 传统版 |
sForum ][登录后回复]1楼
not sure about your solution, pls enlighten mecan you define so-called hamilton path? [陀螺 (5-30 16:44, Long long ago)] [ 传统版 | sForum ][登录后回复]2楼
(引用 陀螺:not sure about your solution, pls enlighten mecan you define so-called hamilton path? )ha? is the simplified version of Euler circle?if you want to have any EUla circle,
then every points must have Even path linking out
if you want just go through , no need to come back
then can have one point with odd number of paths linking out...[MrDJay (5-30 17:23, Long long ago)]
[ 传统版 |
sForum ][登录后回复]3楼
dun have, becoz got points with odd linking[MrDJay (5-30 17:24, Long long ago)] [ 传统版 | sForum ][登录后回复]4楼
(引用 MrDJay:ha? is the simplified version of Euler circle?if you want to have any EUla circle,
then every points must have Even path linkin...)some of your statement is wrongif you want just go through , no need to come back
then can have one point with odd number of paths linking out...
I think it's wrong. Make a simple example.
5 points in a straight line.
got 2 points with odd number of path, right?
From what I have known, to be a shape that can go through at once, it will have the property below.
The point of odd number of paths linking out should be less than 2 or even number. However, not all the shapes fulfil this requirement can be a euler circle. [fool (5-30 17:50, Long long ago)]
[ 传统版 |
sForum ][登录后回复]5楼
(引用 MrDJay:dun have, becoz got points with odd linking)wrong...Also，you should express youself understood by people even at low level[冷色蓝天 (5-30 18:08, Long long ago)] [ 传统版 | sForum ][登录后回复]6楼
(引用 陀螺:not sure about your solution, pls enlighten mecan you define so-called hamilton path? )如果不知道这个概念只看“一”即可[冷色蓝天 (5-30 18:08, Long long ago)] [ 传统版 | sForum ][登录后回复]7楼
(引用 MrDJay:ha? is the simplified version of Euler circle?if you want to have any EUla circle,
then every points must have Even path linkin...)wrong...Hamilton Path和Euler circle完全是2个不同的概念
简单来说，Hamilton Path是包含所有点的一条路径，而且在这条路径上，每个点刚好出现一次[冷色蓝天 (5-30 18:12, Long long ago)]
[ 传统版 |
sForum ][登录后回复]8楼
(引用 fool:some of your statement is wrongif you want just go through , no need to come back
then can have one point with odd number of pat...)sorry, should be EXACTLY 2 odd vertex if it hasan open Euler path
[MrDJay (5-30 19:46, Long long ago)]
[ 传统版 |
sForum ][登录后回复]9楼
(引用 冷色蓝天:wrong...Hamilton Path和Euler circle完全是2个不同的概念
简单来说，Hamilton Path是包含所有点的一条路径，而且在这条路径上，每个点�)well, you are right..:^P, mixing with Euler and HeHemilton path
:$[MrDJay (5-30 19:48, Long long ago)]
[ 传统版 |
sForum ][登录后回复]10楼
(引用 冷色蓝天:wrong...Also，you should express youself understood by people even at low level)well, can group it and use peogeon hole toprove it?
still cannot express in a way that every one understand
release your answer bah:)[MrDJay (5-30 20:03, Long long ago)]
[ 传统版 |
sForum ][登录后回复]11楼
(引用 冷色蓝天:wrong...Hamilton Path和Euler circle完全是2个不同的概念 简单来说，Hamilton Path是包含所有点的一条路径，而且在这条路径上，每个点�)ft看到这里才发现原来hamitton path是原来所学的哈密顿路径。恍然大悟ing[汪！ (5-30 23:19, Long long ago)] [ 传统版 | sForum ][登录后回复]12楼
(引用 汪！:ft看到这里才发现原来hamitton path是原来所学的哈密顿路径。恍然大悟ing)我想可否用博萨定律（sorry,不知道怎么用英语说这个定律），来判断是否是哈密顿图，如果是的话，就可以一笔画通了，可是，点数太多了，好麻烦啊。。。。可否略提点一二。。。。[鬼 (5-30 23:44, Long long ago)] [ 传统版 | sForum ][登录后回复]13楼
(引用 鬼:我想可否用博萨定律（sorry,不知道怎么用英语说这个定律），来判断是否是哈密顿图，如果是的话，就可以一笔画通了，可是，点数太多了，好...)ft,我的第一万贴阿！！不小心用错id了斑竹大大可否给一个一分的小草草安慰安慰，这样我的经验值和发贴数就对得上了^_^[汪！ (5-30 23:45, Long long ago)] [ 传统版 | sForum ][登录后回复]14楼
还是哪位高人提出个答案统一一下吧hamilton path和euler circuit好像不是一回事吧，哪个高人统一一下答案。
有人说没有简单的证明途径，没有什么vertex之类的说法吧。[陀螺 (5-31 3:42, Long long ago)]
[ 传统版 |
sForum ][登录后回复]15楼
(引用 陀螺:还是哪位高人提出个答案统一一下吧hamilton path和euler circuit好像不是一回事吧，哪个高人统一一下答案。 有人说没有简单的证明途径，�...)嗬嗬，知道了，原来好简单！！！[汪！ (5-31 9:38, Long long ago)] [ 传统版 | sForum ][登录后回复]16楼
(引用 汪！:ft,我的第一万贴阿！！不小心用错id了斑竹大大可否给一个一分的小草草安慰安慰，这样我的经验值和发贴数就对得上了^_^)汪！汪！[乖乖龙 (5-31 12:33, Long long ago)] [ 传统版 | sForum ][登录后回复]17楼
看来是公布答案的时候了答案: 用2种颜色给24个点染色，相邻的点颜色不同（如下图）。
假设存在这样的一条线，依题意可知，这条线上的点是红蓝相间。但我们得到的红色的点有13个，蓝色的点有11个，13-11>1。
这是不可能的
[冷色蓝天 (6-1 2:53, Long long ago)]
[ 传统版 |
sForum ][登录后回复]18楼
Newton knows the answer[顽哆拉 (6-5 15:20, Long long ago)] [ 传统版 | sForum ][登录后回复]19楼
(引用 MrDJay:sorry, should be EXACTLY 2 odd vertex if it hasan open Euler path )wrong again,let's make it 5x5 points matrix, how many points with odd vertex? 12points at the side, right?[fool (6-7 11:00, Long long ago)] [ 传统版 | sForum ][登录后回复]20楼
华新中文网 版权所有