漢諾塔圖性質研究.pdf

1、漢諾塔問題是一個古老的問題。根據漢諾塔問題，我們可以構造一類分形網絡:漢諾塔圖。自從漢諾塔圖提出以來，許多學者從不同角度對漢諾塔圖進行了研究，例如最短距離，平均距離，平面性，擴散問題，哈密爾頓回路等。然而，一些重要的問題，例如漢諾塔圖生成樹的數目，隨機游走問題，一致性問題等，依舊是相關研究領域的空白，而這些問題無論在理論上和實際應用中，都有重要意義。本論文主要在三個方面研究漢諾塔圖，即生成樹數目，隨機游走問題和一致性問題。
　　生

2、成樹數目與網絡的諸多拓撲和動力學性質密切相關，例如網絡穩(wěn)定性，同步性能，通信效率等等。然而，求解大規(guī)模網絡的生成樹數目依然缺乏高效的算法。本論文中，我們用枚舉的方法，求解了二維和三維漢諾塔圖生成樹的數目，并給出了解析結果。
　　分形上的隨機游走問題在眾多領域都有重要應用。本論文中我們研究d維漢諾塔圖上的隨機游走問題。借助于漢諾塔圖的自相似結構，我們可以精確地求解隨機游走相關的幾個重要的量。我們首先求解了漢諾塔圖中最外面兩個結點之間

3、的隨機游走平均首達時間，接著，我們求解了所有結點間的全局平均首達時間。我們給出了上述兩個量的解析結果以及其如何隨著網絡規(guī)模增長。隨后我們求解了漢諾塔圖概率轉移矩陣的譜，接著我們運用所求得的譜，求得了漢諾塔圖生成樹的數量和隨機游走特征時間常數。
　　分布式一致性算法是多智能系統和交通運輸中使用的重要工具。除了算法本身的正確性以外，其魯棒性、收斂速度等性質，也是相關研究領域重點考慮的。在本論文中，我們研究了漢諾塔上的一致性問題，包括收