关于加强超立方体的一些性质研究

摘要

网络拓扑结构的性质直接决定互联网络的效率和性能.本文主要研究一种互联网络拓扑结构，即加强超立方体，它是超立方体的一种重要变型.论文主要分为两大部分，讨论加强超立方体的一些参数以及加强超立方体中路和圈的嵌入情况。
　　 第一部分主要研究加强超立方体中路和圈的嵌入情况.包含以下三方面内容：
　　 (1)基于超立方体和加强超立方体的相似结构，我们研究了加强超立方体的一些代数性质，证明了它是Cayley 图，并且自同构群 Aut (Qn)是，Aut (Qn,k)的真子群，由Cayley 图的优良性质进一步获得了加强超立方体的点可迁性和边可迁性等一些性质；
　　 (2)讨论了加强超立方体的边容错性，证明了当n (≧)2时，加强超立方体，Qn,k的任意边e 都包含于n-k+1个长为n-k+2的圈C1,C2,…Cn-k+1，k-1个长为n-k+4的圈Cn-k+2,Cn-k+3…Cn且满足Ci∩Cj=e 其中I,j=1,2,…n且I≠j.在此基础上进一步证明了加强超立方体，Qn,k的任意非故障边都包含于长从4到2n的无故障边偶圈中，同时当n和k 有不同的奇偶性时，每一条非故障边都包含于长从n-k+4到2n-1的非故障奇圈中；
　　 (3)利用加强超立方体的代数性质研究了加强超立方体中路的嵌入情况，证明了当n与k的奇偶性相同时，加强超立方体是偶泛连通的.当n与k的奇偶性相异时，对，Qn,k中距离为d的两点x和y，研究了不同长度的xy 路的分布情况。
　　 第二部分研究加强超立方体的cubicity 参数，Boxicity和cubicity在生态位重叠和军队维修业务研究中有广泛的应用，但是计算任意图的cubicity是被证明是NP-困难的.在这部分中，通过构造一种称为单位区间图的特殊图。