汉诺塔图

把汉诺塔谜题的每个合法局面看成顶点、一步移动看成边，得到的图称为汉诺塔图，它把递归难题转化为图论对象。

定义

$n$ 个圆盘、3 根柱的汉诺塔图中，每个顶点对应一个合法状态（小盘在大盘之上），两顶点相邻当且仅当可经一次合法移动互相转化。

性质

• $H_n$ 有 $3^n$ 个顶点，且同构于谢尔宾斯基三角图
• 从一根柱上全部圆盘到另一根柱上全部圆盘的最短路径长度恰为 $2^n-1$，即经典最少移动次数
• 最优移动序列是一个长度为 $2^n-1$ 的序列，可用递归或二进制计数生成

示例

$n=1$ 时 $H_1$ 是三角形 $K_3$：3 个状态，任意两个一步可达。