[求助]

朔月圆

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

.   . . .

. . . . .

. . . . .

. . . . .

. . . . .

乌木

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

yoyo

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

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

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

易给出解为:

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

yoyo

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

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

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

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

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

[em04]

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

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

yzsjw0

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编辑过]