论文部分内容阅读
超立方体网络具有高对称性、强层次性、可嵌入性、哈密尔顿性、容错性和网络通信能力的可扩展性等优良性质,是迄今为止最为重要和最具吸引力的网络拓扑结构之一,然而超立方体网络有其固有的缺陷,如直径较大,由于节点的连通度和网络的直径均随着网络的维数同比例增长,对超立方体网络进行扩展的复杂度比较高,且易出现传输延迟.因此研究者们提出了超立方体网络的推广及许多变形,如广义超立方体网络Q(d1d2…dn)、纽立方体网络TQn、折叠立方体网络FQn、交叉立方体网络CQn等,它们的出现旨在改进超立方体网络的缺陷.
本文分为两部分,主要研究纽立方体网络和广义超立方体网络的容错性质和圈的嵌入问题.
互连网络中处理器或处理器链路发生故障的情形是不可避免的.第一部分针对条件容错问题,讨论纽立方体网络中圈的嵌入,包含以下几个方面的内容:(1)鉴于纽立方体不具有对称性,在故障的纽立方体中构造出非故障的Hamiltonian圈是比较困难的,我们采用构造性的方法得到一些辅助引理;(2)基于每个节点至少与两条非故障边相连的前提假设,我们利用一些技巧性的路径方法和归纳法得到TQn在含有2n-5条故障边的情况下,仍能嵌入长度从4到2n的圈,其膨胀系数为1;(3)用反证法证明当TQn中有2n-4条故障边时,它不含Hamiltonian圈,更不是泛圈图,所以故障边数2n-5在上述结论中是最优的;(4)我们还推出TQn中每个节点至少与两条非故障边相连的概率,它的值非常接近1,这说明我们的前提假设是非常有意义的.
第二部分研究广义超立方体网络的边泛圈性.如果图G的每条边位于长为l(g(G)≤l≤v(G))的圈上,则图G是边泛圈的.首先我们用构造性的方法证得当n=2时Q(d1d2…dn)是边泛圈的;其次利用小圈构造大圈的方法和归纳法证明广义超立方体网络中每条边都包含在长从3到v(G)的圈中,即Q(d1d2…dn)是边泛圈的;最后我们把结论推广得到Q(d1d2…dn)是点泛圈图.