1.关于哈密尔顿和哈密尔顿图
哈密尔顿是英国的一位数学家和天文学家。
自从哈密尔顿发现“四元数”之后,他又发现了另外一种他命名为“The Icosian Calculus”的代数系统,这系统有加和乘的运算子,可是乘法不满足交换律(即xy=yx这个规律)。
他发现这代数系统是和正则20面体有关系。他想到一个游戏,怎样跑遍正则多面体上的所有顶点,而最后又能回到起点的问题。在1859年他把这个游戏的想法以25英镑的价钱卖给一位玩具和游戏制造商。
这玩具商把这游戏制造出来了,即“周游世界游戏”。在圆盘上有20个代表城市的圆孔,你必须把20个上面标有1,2,3,…,20的木条顺序插进去,代表你经过不同的城市,最后回到原出发点。这个游戏曾经风靡一时,它有若干个解,称为哈密尔顿圈。
以后人们因这游戏就称这类图为哈密尔顿图。
2.哈密尔顿回路的两个相关定义
定义1 图G的一个回路若它通过G中每个点一次,这样的回路称为哈密尔顿回路。具有这样的回路的图称为哈密尔顿图。
定义2 通过图G中每结点一次的通路(非回路),称为哈密尔顿通路。
3.魔方的状态图
将魔方的每个状态做为一个结点。而魔方六个面中的任何一面顺或逆时针旋转90°,即可生成一个新的状态。在这里,每个边代表某个面旋转了90°。因此,从每个结点出发,有12条边。
魔方状态数为N,则这N个结点组成一张状态图。由魔方的广义复原原理,不存在特殊的结点。每个结点出发,都有相同结构的12条边与其它结点相连。
由于已证明,魔方任意两个状态之间转换的步数不大于22或23步(类似U2这种算一步?),所以魔方的状态图将是一个密集集中在一个直径为22或23步的球体中的网络,或者存在于一个自封闭的三维空间中。
比如U面,四个U操作即回复到原来状态,所以魔方状态图中最基本的结构就是边为4的小四边形。
所有公式,都是此状态图中的一条通路。
魔方的遍历问题,就是寻找魔方状态图的哈密尔顿回路的问题。
4.哈密尔顿问题的求解
哈密尔顿回路与通路至今尚未找到一个判别它的充分必要条件。在大多数情况下,还是采用尝试的方法来解决。
发现这点是让我比较郁闷的事情。还是关注数学的发展吧。 |