主题
Search

汉诺塔图

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本
HanoiGraph

汉诺塔图 H_n 对应于 汉诺塔 问题中允许的移动。上图显示了小 n 的汉诺塔图。汉诺塔图 H_n 可以通过取顶点为帕斯卡三角形的奇二项式系数（在从 0 到 2^n-1 的整数上计算）来构造，并在系数沿对角线或水平方向相邻时绘制一条边 (Pool 1994)。

图 H_n 有 3^n 个顶点（OEIS A000244）和 3(3^n-1)/2 条边（OEIS A029858）。每个汉诺塔图都有唯一的哈密顿环。（等效地，每个汉诺塔图恰好有两个不同的有向哈密顿环。）

H_n 有 3^(n-1) 个小三角形，每个三角形最多可以在一个独立顶点集中包含一个顶点。但这些三角形在平面上以这样一种方式排列，即选择每个三角形的顶点可以得到一个（最大）独立顶点集（S. Wagon, 私人通讯, 11月 18, 2011）。

汉诺塔图是完美的，也是唯一哈密顿的。

汉诺塔图在 Wolfram 语言中实现为GraphData[{"Hanoi", n}].

另请参阅

Puz-Graph, 谢尔宾斯基垫片图, 汉诺塔

使用 Wolfram|Alpha 探索

参考文献

Berend, D. 和 Sapir, A. "汉诺塔图的直径。" Information Processing Lett. 98, 79-85, 2006.Hinz, A. M. "帕斯卡三角形和汉诺塔。" Amer. Math. Monthly 99, 538-544, 1992.Hinz, A. M. 和 Parisse, D. "关于汉诺塔图的平面性。" Expos. Math. 20, 263-268, 2002.Hinz, A. M. 和 Schief, A. "谢尔宾斯基垫片上的平均距离。" Probab. Th. Rel. Fields 87, 129-138, 1990.Hinz, A. M.; Klavžar, S.; Milutinovć, U.; Parisse, D.; 和 Petr, C. "汉诺塔图的度量属性和斯特恩双原子序列。" Europ. J. Combin. 26, 693-708, 2005.Lu, X. M. "汉诺塔图。" Internat. J. Comput. Math. 19, 23-38, 1986.Lu, X. M. "具有任意 k>=3 柱子的汉诺塔。" Internat. J. Comput. Math. 24, 39-54, 1988.Poole, D. G. "克劳斯教授的塔和三角形（或者，帕斯卡知道汉诺塔）。" Math. Mag. 67, 323-344, 1994.Scorer; R. S.; Grundy, P. M.; 和 Smith, C. A. B. "一些二元游戏。" Math. Gaz. 28, 96-103, 1944.Sloane, N. J. A. 序列 A000244/M2807 和 A029858，出自“整数序列在线百科全书”。

在 Wolfram|Alpha 中引用

汉诺塔图

请这样引用

Weisstein, Eric W. "汉诺塔图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/HanoiGraph.html

主题分类