终检评审通过 创新训练 110数学 理论研究-理学基础国家级

系统中元件之间的连接模式称为该系统的网络。一个系统的网络本质上刻画了该系统的结构特征。实践证明，图论是研究和分析网络的最基本和强有力的数学工具。在设计和评估网络的过程中，一个核心问题就是判断一些已知的网络能否嵌入到这个网络中，从图的角度看，这个问题就是所谓的图的嵌入问题。路和圈是并行和分部计算中两种基本的网络，非常适合用于开发低成本的简单的算法程序。在给定的图中，如何寻找具有特定性质的圈称为是图的圈嵌入问题。图的哈密尔顿圈是指图中经过所有顶点一次且仅有一次的圈。如果一个图中两个哈密尔顿圈不共享任何边，称它们为边不相交的。边不相交的哈密尔顿圈可以为使用圈的算法提供优势。如果网络中存在边不相交的哈密尔顿圈，数据可以被分割然后在不同圈上传播，即不存在边的争夺使用。另外，如果一条边发生故障时，可以在另一条边上传播消息。超立方体是迄今发现的用于构建大型并行或分布系统的最著名，最有效的拓扑结构，具有很多非常好的性质，如高对称性等。基于超立方体，许多变形网络被设计，如局部扭立方体网络等。这些网络不仅保留了超立方体网络的部分优良性质，而且在某些方面又优于超立方体，如具有更小的直径等。本项目拟针超立方体变形网络的哈密尔顿圈嵌入问题开展研究。