Please use this identifier to cite or link to this item: `https://ah.nccu.edu.tw/handle/140.119/138940`

 Title: 漢諾圖上的哈密頓路徑Hamiltonian Walks on the Hanoi Graph Authors: 呂存策CUNCE, LYU Contributors: 陳隆奇Lung­-Chi Chen呂存策LYU CUNCE Keywords: 漢諾圖哈密頓路徑漸進表現Hanoi graphHamiltonian walkAsymptotic behaviour Date: 2021 Issue Date: 2022-02-10 13:06:31 (UTC+8) Abstract: 本文給出了 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 two­dimensional 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 byh′(n) ∼(25w*16^n(xyz)^(3n−1))/(16*27*13) in which w =(x + y + z)^2/(xyz). Reference: [1] RM Bradley. Analytical enumeration of hamiltonian walks on a fractal. Journal of Physics A: Mathematical and General, 22(1):L19, 1989.[2] Shu­Chiuan Chang and Lung­Chi Chen. Structure of spanning trees on the two­dimensional sierpinski gasket, 2008.[3] Shu­Chiuan Chang and Lung­Chi 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 Hanoi­myths 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ć. Semi­flexible compact polymers on fractal lattices. Physica A: Statistical Mechanics and its Applications, 390(11):1941–1952, 2011. Description: 碩士國立政治大學應用數學系104751019 Source URI: http://thesis.lib.nccu.edu.tw/record/#G0104751019 Data Type: thesis Appears in Collections: [應用數學系] 學位論文

Files in This Item:

File Description SizeFormat