簡易檢索 / 詳目顯示

回結果列表
研究生： 黎維邦
Li, Wei-Bang
論文名稱： 在漢諾以圖形上的拓展樹統計物理問題
The number of spanning tree on Hanoi tower
指導教授： 張書銓
Chang, Shu-Chiuan
學位類別： 碩士
Master
系所名稱： 理學院 - 物理學系
Department of Physics
論文出版年： 2014
畢業學年度： 102
語文別： 中文
論文頁數： 73
中文關鍵詞： 拓展樹 、拓展林 、Tutte多項式 、Laplace矩陣
外文關鍵詞： spanning tree, spanning forest, Tutte polynomial, Laplacian matrix
相關次數： 點閱：63  下載：2 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 本論文主要探討拓展樹（spanning tree）在二維Hanoi tower上的個數，並找出其在Hanoi tower上的遞迴關係式。我們使用數學運算軟體maple驗證數據，並拿來跟spanning tree在Sierpinski gasket的二維無限延伸圖形上的個數和遞迴關係式做比較。

    This thesis investigates the number of spanning trees on the Hanoi tower HT(n) at stage n with dimension equal to two. We double-check the general expression of the number of spanning trees on HT(n) with Tutte polynomial and Laplacian matrix by maple. The graphs and the result on HT(n) will be compared with that on Sierpinski gasket SG(n).

    摘要 ..............................................................Ⅰ Abstract ...........................................................Ⅱ 中英文關鍵字.......................................................Ⅲ 致謝 ..............................................................Ⅳ 目錄 ..............................................................Ⅴ 圖表索引 .........................................................VII 第一章 緒論 §1-1 前言 ..........................................................1 §1-2 論文結構 ......................................................1 第二章 簡介拓展樹spanning tree和拓展林spanning forest §2-1 什麼是拓展樹(spanning tree)？...................................3 §3-2什麼是拓展林(spanning forest)？..................................5 第三章 spanning tree在各種圖形上的例子 §3-1 在三角形上的拓展樹(spanning tree)圖形...........................7 §3-2 在四邊形上的拓展樹(spanning tree)圖形………....................10 §3-3 Hanoi tower圖形...............................................12 第四章 計算方法介紹以及驗算結果 §4-1 常用的計算方法................................................18 4-1.1 幾何排列圖形重新定義....................................19 4-1.2 重新定義f(n)、g(n)、h(n)的好處..........................22 §4-2 幾何排列圖形討論Hanoi tower..................................28 §4-3 Tutte polynomial驗證Hanoi tower的結果...........................37 4-3.1 Tutte polynomial定義.....................................37 4-3.2 Tutte polynomial範例.....................................38 4-3.3 Tutte polynomial驗證計算結果.............................40 §4-4 Laplacian matrix驗證Hanoi tower的結果........................44 4-4.1 Laplacian matrix定義.....................................44 4-4.2 Laplacian matrix範例與驗算結果...........................45 第五章 結果分析 ...........................................49 第六章 結論 ................................................52 參考文獻................................................53 參考資料一................................................54 參考資料二................................................57 參考資料三................................................66

    [1] A. Pothen, H. Simon, and K.-P. Liou, "Partitioning sparse matrices with eigenvectors of graphs", SIAM J. Matrix Anal. Appl., 11:430-452.(1990).
    [2] J.-P. Allouche, "Note on the Cyclic Towers of Hanoi." Theor. Comput. Sci. 123, 3-7, (1994).
    [3] D. Berend and A. Sapir, "The Diameter of Hanoi Graphs." Information Processing Lett. 98, 79-85, (2006).
    [4] D. Babić; D. J. Klein; I. Lukovits; S. Nikolić; and N. Trinajstić, "Resistance-Distance Matrix: A Computational Algorithm and Its Applications." Int. J. Quant. Chem. 90, 166-176, (2002).
    [5] N. L. Biggs, "The Tutte Polynomial." Ch. 13 in Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, pp. 97-105, (1993).
    [6] B.-Y. Wu and K.-M. Chao, “Spanning Trees and Optimization Problems” (Chapman & Hall/CRC,Boca Raton,)(2004).
    [7] Daniele D’Angeli,” Weighted spanning trees on some self-similar graphs”, Universidad de los Andes Carrera 1, 18A - 70 Bogot´a, Colombia (2011).
    [8] F.-Y. WU,” Dimers and spanning trees: some recent result”, International Journal of Modern Physics B, Vol. 16, 1951-1961.(2002)
    [9] D.G. Poole, "The Towers and Triangles of Professor Claus (or, Pascal Knows Hanoi)."Math. Mag. 67, 323-344, (1994).
    [10] S.-C. Chang and L.-C. Chen and W.-S. Yang,” Spanning Trees on the Sierpinski Gasket”, J. Stat. Phys, Vol. 126, No. 3, February 2007 (2007 ).
    [11] S.-C. Chang and R. Shrock,” Exact Potts model partition functions on wider arbitrary-length strips of the square lattice”, Physica A 296 234–288 (2001)
    [12] S.-C. Chang and R. Shrock, J. Phys. A: Math. Gen. 39 5653–8(2006)
    [13] S.-C. Chang and R. Shrock,” Some exact results for spanning trees on lattices.” J. Phys. A: Math.Gen. 39:5653–5658 (2006).
    [14] S.-C. Chang and W. Wang, “Spanning trees on lattices and integral identities”. J. Phys. A: Math.Gen. 39:10263–10275 (2006).
    [15] S. Wu and Z. Zhang” Eigenvalue spectrum of transition matrix of dual Sierpinski gaskets and its applications” J. Phys. A: Math. Theor. 45 (2012)

    下載圖示 校內：立即公開
    校外：立即公開
    QR CODE