由哈密尔顿图到魔方状态的遍历

noski

１．关于哈密尔顿和哈密尔顿图

哈密尔顿是英国的一位数学家和天文学家。

自从哈密尔顿发现“四元数”之后，他又发现了另外一种他命名为“The Icosian Calculus”的代数系统，这系统有加和乘的运算子，可是乘法不满足交换律（即xy=yx这个规律）。

他发现这代数系统是和正则20面体有关系。他想到一个游戏，怎样跑遍正则多面体上的所有顶点，而最后又能回到起点的问题。在1859年他把这个游戏的想法以25英镑的价钱卖给一位玩具和游戏制造商。

这玩具商把这游戏制造出来了，即“周游世界游戏”。在圆盘上有20个代表城市的圆孔，你必须把20个上面标有1，2，3，…，20的木条顺序插进去，代表你经过不同的城市，最后回到原出发点。这个游戏曾经风靡一时，它有若干个解，称为哈密尔顿圈。

以后人们因这游戏就称这类图为哈密尔顿图。

２．哈密尔顿回路的两个相关定义

定义1 图G的一个回路若它通过G中每个点一次，这样的回路称为哈密尔顿回路。具有这样的回路的图称为哈密尔顿图。

定义2 通过图G中每结点一次的通路（非回路），称为哈密尔顿通路。

3．魔方的状态图

将魔方的每个状态做为一个结点。而魔方六个面中的任何一面顺或逆时针旋转90°，即可生成一个新的状态。在这里，每个边代表某个面旋转了90°。因此，从每个结点出发，有12条边。

魔方状态数为N，则这N个结点组成一张状态图。由魔方的广义复原原理，不存在特殊的结点。每个结点出发，都有相同结构的12条边与其它结点相连。

由于已证明，魔方任意两个状态之间转换的步数不大于22或23步（类似U2这种算一步？），所以魔方的状态图将是一个密集集中在一个直径为22或23步的球体中的网络，或者存在于一个自封闭的三维空间中。

比如U面，四个U操作即回复到原来状态，所以魔方状态图中最基本的结构就是边为4的小四边形。

所有公式，都是此状态图中的一条通路。

魔方的遍历问题，就是寻找魔方状态图的哈密尔顿回路的问题。

4．哈密尔顿问题的求解

哈密尔顿回路与通路至今尚未找到一个判别它的充分必要条件。在大多数情况下，还是采用尝试的方法来解决。

发现这点是让我比较郁闷的事情。还是关注数学的发展吧。

pengw

以下是引用noski在2005-5-11 14:19:33的发言：

1.让人眼睛一亮的见解,非常独到.对离散数学的引用非常传业,少见的传业数学观点

2.一个群论以外的新观点,其实群论在此问题走入死穴已多年没有改变了,凡是基于群论的理论,除了在状态表示上有作为外,其它基本没有可圈可点的表现(引用一个博士级人物的话)

3.基于状态分析的角度,对魔方性质的表达,暂时有比较实用的结论,但在最优解及最远状态处理方面当前也看不到方向

4.NOSKI有22或23步证明的资料吗?

5.最优解及最远状态处理也许与新数学手段相生相随,但还有很多不死心人的人在探索,当然包括我自已

6.好文好文...美酒.

noski

pengw过奖了

对这个问题, 我的描述还很粗略, 现在我还在思考中, 希望能再进一步完善一点, 给出一个详细一点的解释.

对于22或23步, 我是到吧里看帖子才知道的, 目前还没有证明...

和你们严密的理论相比, 我几乎是个猜想主义者, 我把我的想法贴出来, 希望对魔方理论的完善也能做出一点贡献.

pengw

以下是引用noski在2005-5-12 22:10:37的发言：

pengw过奖了

对这个问题, 我的描述还很粗略, 现在我还在思考中, 希望能再进一步完善一点, 给出一个详细一点的解释.

对于22或23步, 我是到吧里看帖子才知道的, 目前还没有证明...

和你们严密的理论相比, 我几乎是个猜想主义者, 我把我的想法贴出来, 希望对魔方理论的完善也能做出一点贡献.

建议继续深入研究下去,大家不要在群论一棵树上吊死,我发的贴子也跟群论毫不相干,而那些相干的又基本没有什么结论,敢踏一条新路真的很勇敢,很大气.反正我是不喜欢去重复验证别人的错误.

ggglgq

提醒 noski 先生能参考乌木先生的理论“魔方态关系网是怎样的”，或许对您的理论有所帮助！
因为如果正六面体三阶魔方的状态图是一个密集集中在“一个直径为 22 步的球体中”，那么它的
分布是不均匀的，比如球心到球体中任何一点的距离最大为 11 步。因此需要改动“一个直径为 22
步的球体中”为“一个大圆的半圆为 22 步的球面上”。

乌木

我想，分布成球体 、成球面，无非为能直观地帮助处理问题。鉴于N太大太大，成什么形状都于事无补。重要的是探究态态关系。我在自我否定的帖子中说过，把它们和水泥石子拌成混凝土也好，把它们抛向广袤的宇宙也罢，全都无所谓，态态之间的关系不变。现在好了，“后哈密尔顿”先生们在探路了。
确实，态A经UDU'D'等等的四边形回路，与UUUU一样，都回到态A，再小的回路（三角形）好像不存在。

[此贴子已经被作者于2005-6-15 20:25:12编辑过]

乌木

还有，1楼说的20面体是否应为12面体，后者才有20个顶点呀。
那周游20个城市的玩具可自制。12面体可“拓扑”为如下平面图形，20个点子相互关系不变：

哎呀，谁踩扁了老猫的五魔方？他还要发货给魔友的呀。
哪里，这是最新产品，搁信封里就可发寄啦。收到后吹口气就复原啦。

[此贴子已经被作者于2005-6-17 0:08:28编辑过]

noski

谢谢乌木,的确是12面体,20个顶点,是我写错了,一直没有注意到...