论文部分内容阅读
汉诺塔问题是一个古老的问题。根据汉诺塔问题,我们可以构造一类分形网络:汉诺塔图。自从汉诺塔图提出以来,许多学者从不同角度对汉诺塔图进行了研究,例如最短距离,平均距离,平面性,扩散问题,哈密尔顿回路等。然而,一些重要的问题,例如汉诺塔图生成树的数目,随机游走问题,一致性问题等,依旧是相关研究领域的空白,而这些问题无论在理论上和实际应用中,都有重要意义。本论文主要在三个方面研究汉诺塔图,即生成树数目,随机游走问题和一致性问题。生成树数目与网络的诸多拓扑和动力学性质密切相关,例如网络稳定性,同步性能,通信效率等等。然而,求解大规模网络的生成树数目依然缺乏高效的算法。本论文中,我们用枚举的方法,求解了二维和三维汉诺塔图生成树的数目,并给出了解析结果。分形上的随机游走问题在众多领域都有重要应用。本论文中我们研究d维汉诺塔图上的随机游走问题。借助于汉诺塔图的自相似结构,我们可以精确地求解随机游走相关的几个重要的量。我们首先求解了汉诺塔图中最外面两个结点之间的随机游走平均首达时间,接着,我们求解了所有结点间的全局平均首达时间。我们给出了上述两个量的解析结果以及其如何随着网络规模增长。随后我们求解了汉诺塔图概率转移矩阵的谱,接着我们运用所求得的谱,求得了汉诺塔图生成树的数量和随机游走特征时间常数。分布式一致性算法是多智能系统和交通运输中使用的重要工具。除了算法本身的正确性以外,其鲁棒性、收敛速度等性质,也是相关研究领域重点考虑的。在本论文中,我们研究了汉诺塔上的一致性问题,包括收敛速度,鲁棒性和一阶系统及二阶系统的一致性量。接着我们将汉诺塔图上的主要结果与一类小世界网络作比较,这类小世界网络与汉诺塔图有相同的结点和边的数目。