簡易檢索 / 詳目顯示
| 研究生： |
呂存策 LYU CUNCE |
|---|---|
| 論文名稱： |
漢諾圖上的哈密頓路徑 Hamiltonian Walks on the Hanoi Graph |
| 指導教授： |
陳隆奇
Lung-Chi Chen |
| 口試委員: |
陳隆奇
Lung-Chi Chen 張書銓 Shu-Chiuan Chang 張宜武 Yi-Wu Chang |
| 學位類別： |
碩士
Master |
| 系所名稱： |
理學院 - 應用數學系 Department of Mathematical Sciences |
| 論文出版年： | 2021 |
| 畢業學年度： | 110 |
| 語文別： | 英文 |
| 論文頁數： | 29 |
| 中文關鍵詞： | 漢諾圖 、哈密頓路徑 、漸進表現 |
| 外文關鍵詞： | Hanoi graph, Hamiltonian walk, Asymptotic behaviour |
| DOI URL： | http://doi.org/10.6814/NCCU202101772 |
| 相關次數： | 點閱：267 下載：19 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
本文給出了 n 階 2 維漢諾圖（又稱漢諾塔圖、河內圖）上哈密頓路徑的數量，其漸進表現是 h(n) ∼ 25×16^n/624 。這類漢諾圖上的哈密頓路徑總數量與起點在最上面的顶點的哈密頓路徑數量的對數的比值漸進至 2。同時，當這類漢諾圖上三個方向的平行邊分別被 x, y, z 這三個數
加權後，我們也推導出了它們的哈密頓路徑的加權和，其漸進表現為h′(n) ∼(25w*16^n(xyz)^(3n−1))/(16*27*13)其中 w =(x + y + z)^2/(xyz)。
We’ve derived the number of Hamiltonian walks on the twodimensional Hanoi graph at stage n, whose asymptotic behaviour is given by h(n) ∼ 25×16^n/624 .
And the asymptotic behaviour the logarithmic ratio of the number of Hamiltonian walks on these Hanoi graphs with that one end at the topmost vertex is given by 2. When the parallel edges in the three directions on these Hanoi graphs are weighted by three numbers, x, y, z, the weighted sum of their Hamiltonian paths is also derived by us, and the asymptotic behaviour of it is given by
h′(n) ∼(25w*16^n(xyz)^(3n−1))/(16*27*13) in which w =(x + y + z)^2/(xyz).
致謝 i
中文摘要 ii
Abstract iii
Contents iv
List of Figures v
1 Introduction 1
1.1 Hanoi graphs 1
1.2 Hamiltonian walk 2
2 Hamiltonian paths in weightless Hanoi graph 4
2.1 Preliminaries 4
2.2 Building recursions to count the number of Hamiltonian walks 6
2.3 Number of Hamiltonian walks 8
3 Hamiltonian paths in weighted Hanoi graph 11
3.1 Preliminaries 11
3.2 Building recursions to calculate the weighted sum of Hamiltonian walks 16
3.3 Get the weighted sum 22
Bibliography 29
[1] RM Bradley. Analytical enumeration of hamiltonian walks on a fractal. Journal of Physics A: Mathematical and General, 22(1):L19, 1989.
[2] ShuChiuan Chang and LungChi Chen. Structure of spanning trees on the twodimensional sierpinski gasket, 2008.
[3] ShuChiuan Chang and LungChi Chen. Hamiltonian paths on the sierpinski gasket, 2009.
[4] Sunčica ElezovićHadžić, Dušanka Marčetić, and Slobodan Maletić. Scaling of hamiltonian walks on fractal lattices. Physical Review E, 76(1):011107, 2007.
[5] Andreas M Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr. The Tower of Hanoimyths and maths. Springer, 2013.
[6] Wilfried Imrich, Sandi Klavzar, and Douglas F Rall. Topics in graph theory: Graphs and their Cartesian product. CRC Press, 2008.
[7] Sandi Klavžar and Uroš Milutinović. Graphs s (n, k) and a variant of the tower of hanoi problem. Czechoslovak Mathematical Journal, 47(1):95–104, 1997.
[8] Dušanka Lekić and Sunčica ElezovićHadžić. Semiflexible compact polymers on fractal lattices. Physica A: Statistical Mechanics and its Applications, 390(11):1941–1952, 2011.
