主題
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, 謝爾賓斯基墊片圖, 漢諾塔

使用 探索

參考文獻

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，出自“整數序列線上百科全書”。

在 中引用

漢諾塔圖

請這樣引用

Weisstein, Eric W. "漢諾塔圖。" 來自 Web 資源。 https://mathworld.tw/HanoiGraph.html

主題分類