魔方吧·中文魔方俱乐部

标题: [求助] [打印本页]

作者: 朔月圆 时间: 2007-7-28 20:09:13 标题: [求助]

如图有25个点排成一个正方形，但是第二个点没了，问能不能用一笔把24个点连起来，但所连过的线不能重合，，所连的线也只能是横和竖，如果不能请给出证明，谢谢！

. . . .

. . . . .

作者: 乌木 时间: 2007-7-28 21:16:34

是不是每一根线段只能是一个单位，不能为两个单位，也就是空缺的那一“点”处不可有线段经过？

作者: yoyo 时间: 2007-7-28 22:40:51

这是一个hanmilton道路的问题,楼主的问题可以概括如下

hanmilton道路即经过所有结点一次且仅一次的一条道路

如果空缺的那个点可以有线经过,即概括为下图的hanmilton道路:

易给出解为:

[此贴子已经被作者于2007-7-28 22:42:12编辑过]

附件: lXXG5KE7.jpg (2007-7-28 22:41:22, 10.55 KB) / 下载次数 48
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=OTgxMXwxMGEyODE5MHwxNzMyMjUzMDI0fDB8MA%3D%3D

附件: YYRX2RNg.jpg (2007-7-28 22:41:48, 12.37 KB) / 下载次数 45
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=OTgxMnxiMjAwYWI4OHwxNzMyMjUzMDI0fDB8MA%3D%3D

作者: yoyo 时间: 2007-7-28 22:43:12

如果那个空缺的点不能有线经过,即概括为下图的hamilton道路:

ms现有的判断是非h图的定理对本图不适用..而且我试了很久也不能画出这样一条道路,而且至今未能提出判定h图的有效算法,所以这个图的判定有些困难,

但是hamilton图的特性决定了可以通过复杂讨论来进行判定----hamilton道路中有且只有两个结点与一条边关联,剩余结点都与两条边关联,

所以本图左上角那个结点唯一关联的一条边一定在hamilton道路中,那么它下边的那个结点关联的两条边肯定有一条已经确定,可以讨论两种情况:

1.横的那条在h道路中 2.竖的那条在h道路中.....这只是讨论的一个基本思想...楼主慢慢琢磨吧.....

[em04]

具体讨论太复杂...懒得想了

[此贴子已经被作者于2007-7-28 22:50:40编辑过]

附件: tw1WFAqR.jpg (2007-7-28 22:43:24, 10.33 KB) / 下载次数 49
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=OTgxM3wzYWRlN2VlMnwxNzMyMjUzMDI0fDB8MA%3D%3D

作者: yzsjw0 时间: 2007-7-29 05:03:42

1楼不可能做到。5×5-1、5×3-1、3×3-1等等不可能，而5×4-1、4×4-1、4×3-1等等是可能的。

[此贴子已经被作者于2007-7-29 9:10:18编辑过]

附件: 9cuiRXpl.jpg (2007-7-29 05:04:23, 9.23 KB) / 下载次数 50
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=OTgxNHwxYTM0MGJkMXwxNzMyMjUzMDI0fDB8MA%3D%3D

作者: arimaspu 时间: 2007-9-16 02:42:02

提示: 作者被禁止或删除内容自动屏蔽

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)