证明环的递归方差网络的性质

证明环的递归方差网络的性质

1时空连接网络拓扑结构图来表示连接网络网络拓扑结构的事实已经被计算机和工程专家广泛接受和应用。图理论是设计和分析连接网络拓扑结构的非常有用的数学工具。一个图g是一个有序的二进制组（v（g），e（g））。其中v（g）是g的尖端，v（g）中的元素称为g的顶端。因为边缘是g的边，元素是g的边。当边端的一端与边端相同时，边端被称为边缘端。当边端v（g）v（g）是对边的有序结组时，称为图g是对边的正相关。当v（g）v（g）是对排列端的对齐时，称为图g是一个无向的图。互连网络可以用图来表示,图的顶点表示系统中的元件,图的边表示元件之间的物理连线,其中有向边表示单向通信连线,无向边表示双向通信连线,关联函数指定了元件之间的连接方式.这样的图称为互连网络拓扑结构,或简称为拓扑结构.Sun等介绍了一种新的可扩展的互连网络,叫做环的递归立方体网络(RecursiveCubeofRingsNetwork,RCR网络).一般地,一个RCR网络是由一些链互相连接的许多环构成,这些链叫做立方体链(cubelinks).环中的节点由另外一些链连接,那些链叫做环链(ringlinks).一个RCR网络记成RCR(k,r,j),其中k是立方体的维数,r是环上节点的数目,j是生成种子(generationseed)的扩张数.图1画出了一个RCR(2,2,2)网络.Cayley图是由英国数学家Cayley于1895年最早构造出来的高对称正则图.Cayley图由有限群导出,构造方便,深受网络设计者的欢迎和重视.徐俊明等证明了Cayley图的笛卡尔乘积还是Cayley图.文献提出RCR网络是很好的互连网络拓扑,它拥有很多良好的拓扑性质,比如固定的度数、小的维数、广泛的对剖宽度、对称性、容错性等.然而,文献中证明RCR网络是Cayley图时,其证明不是很详细完整,并且其节点的标记也出现了一些错误.用有限群导出Cayley图的方法,文献证明了立方连通圈(cubeconnectedcycle)是Cayley图.本文也用有限群导出Cayley图的方法,首先构造一个新的群,然后在定义的群上证明RCR网络是Cayley图.对于RCR网络中节点的标号,也做了相应的更改.2维数的定义与假设在这一节中,将给出RCR网络的定义和Cayley图的定义.RCR网络中的节点地址记成[a1a2…ai…ak+j-1ak+j,b],其中ai是一个二进制位,1≤i≤k+j,0≤b<r.在这个网络中,每个节点都有k个立方体邻点(cubeneighbors)和两个环邻点(ringneighbors).地址为[a1a2…ai…ak+j-1ak+j,b]的节点的k个立方体邻点的地址为[a1a2…bj+x…ak+j-1ak+j,b](其中1≤x≤k),它的两个环邻点的地址为[a1a2…ak+j-1ak+j,b+1(modr)]和[a1a2…ak+j-1ak+j,b-1(modr)].Hu等证明了RCR(k,1,j)网络是一个不连通的图.Choi等扩展了这个结论,并证明了当k(r-1)≥j时,RCR(k,r,j)是一个连通图.Choi等还证明了对于一个连通图RCR(k,r,j),它的维数D是k+j+「j/k┐+└r/2」.下面给出一些定义,首先介绍群的定义.定义1设G为非空集合,“。”为G上的一个代数运算,如果G的运算满足:(1)“。”满足结合律,即∀a,b,c∈G,都有(a。b)。c=a。(b。c);(2)G中有元素e,使对每个元a∈G,有e。a=aue0c9e=a;(3)对G中每个元素a,存在元素b∈G,使a。b=bue0c9a=e.当群G的代数运算满足交换律时,称G是一个交换群,或称Abel群,或称加群.将交换群G称为加群时,通常将代数运算写作“+”,记群为(G,+).群的直积是研究群的重要手段之一.利用群的直积可以从已知的群构造出新的群,也可以用小群构造大群.下面介绍群的直积的概念.定义2设G1,G2是群,G={(a1,a2)|a1∈G1,a2∈G2}为集合G1与G2的笛卡尔乘积(Cartesianproduct),在G中定义乘法运算(a1,a2)·(b1,b2)=(a1b1,a2b2);(a1,a2),(b1,b2)∈G.则G关于上述定义构成群,称为群G1与群G2的外直积(externaldirectproduct),记作G=G1×G2,G1,G2称为G的直积因子.如果G1,G2都是加群(运算写作“+”)时,则用G1⊕G2来表示G1,G2的直积,此时也称为直和,其运算为(a1,a2)+(b1,b2)=(a1+b1,a2+b2).下面给出Cayley图的定义.定义3设Γ=(X,。)是非平凡有限群,S是X的非空子集,且不含Γ的单位元e.定义有向图如下:V(G)=Γ;(x,y)∈E(G)⇔x-1y∈S,∀x,y∈Γ,称G为群Γ关于S的Cayley图(Cayleygraph).由于x-1y∈S⇔y∈xS,故G为群Γ关于S的Cayley图,即V(G)=Γ,(x,y)∈E(G)⇔y∈xS,∀x,y∈Γ.类似地,如果G为群Γ关于S的Cayley图,则V(G)=Γ,(x,y)∈E(G)⇔y∈Sx,∀x,y∈Γ.下面给出一个新的定义:定义4代数运算Γ=((Z2)n×Zr,+)是一个可交换群.即对于(Z2)n×Zr中的任意两个元素(X1,b1)和(X2,b2),其中X1,X2∈(Z2)n,b1,b2∈Zr,那么(X1,b1)+(X2,b2)=(X2,b2)+(X1,b1)=(X1+X2,b1+b2)注意到,定义4是群Γ=((Z2)n×Zr,+)对于一般的加法运算是一个交换群.在下一节中,将在同一个集合(Z2)n×Zr上定义一个新的运算,发现新的群不是交换群,但是通过这个新的群,可以得到主要结论,即RCR网络是一个Cayley图.3行向量与向量加速度定理1RCR(k,r,j)网络是Cayley图.证明令(Z2)n表示n个集合Z2的笛卡尔乘积Z2×Z2×…×Z2.设是一个n阶循环矩阵,其中n=k+j.把(Z2)n中的元素看成是一个行向量v,令vC中向量加法按模2计算,那么vC也是(Z2)n中的元素.定义一个新的代数运算Γ=((Z2)n×Zr,*),对任意的[X,y],[A,b]∈(Z2)n×Zr运算“*”定义为[X,y]*[A,b]=[X×Cbj+A,y+b].其中,第一个向量加法是模2的(在(Z2)n中),第2个向量加法是模r的(在Zr中).令Zr表示r的整数集合{0,1,…,r-1}.那么(Z2)n和Zr是Cayley图.从矩阵C可以得到:下面首先证明代数结构Γ=((Z2)n×Zr,*)是一个群.对于(Z2)n×Zr中的任意3个元素[U,v],[X,y]和[A,b],有(1)[u,v][x,b][x,y+b]{[U,v]*[X,y]}*[A,b]=[U×Cyj+X,v+y]*[A,b]=[(U×Cyj+X)×Cbj+A,v+y+b]=[U×C(y+b)j+X×Cbj+A,v+y+b].另一方面,又有[U,v]*{[X,y]*[A,b]}=[U,v]*[X×Cbj+A,y+b]=[U×C(y+b)j+X×Cbj+A,v+y+b].故{[U,v]*[X,y]}*[A,b]=[U,v]*{[X,y]*[A,b]}.(2)单位矩阵的单位元属性分析由[X,y]*[A,b]=[X×Cbj+A,y+b]=[A,b]得:X=0(k+j阶单位矩阵),y=0.即:*[A,b]=[A,b].另一方面,又有[A,b]*=[A×C0j+0,b+0]=[A,b],所以*[A,b]=[A,b]*=[A,b],即[A,b]的单位元是,其中第一个0是k+j阶单位矩阵.(3)[a,b][a,b][a,b]],b],b],b],b],b],b],b],b],b],[a000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000b000000b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.由[X,y]*[A,b]=[X×Cbj+A,y+b]=,得X=-A×C-bj和y=-b,即[-A×C-bj,-b]*[A,b]=.另一方面,又有[A,b]*[-A×C-bj,-b]=[A×C-bj-A×C-bj,b-b]=.所以[-A×C-bj,-b]*[A,b]=[A,b]*[-A×C-bj,-b]=,即[A,b]的逆元是[-A×C-bj,-b].从定义1,可知Γ=((Z2)n×Zr,*)是一个群.接下来证明RCR(k,r,j)是一个Cayley图.令Η={[000⋯000,1],[000⋯000,r-1],[100⋯000,0],[010⋯000,0],⋯,[00⋯01k0⋯000,0]}H={[000⋯000,1],[000⋯000,r−1],[100⋯000,0],[010⋯000,0],⋯,[00⋯01k0⋯000,0]}注意到H的每个元素的逆元也在H中,所以H是一个Cayley集.对于(Z2)n×Zr的任意元素[A,b]和H中的任意点,可以得到如下RCR(k,r,j)中点[A,b]的链:([A,b],[000…000,1]*[A,b])=([A,b],[A,b+1]),([A,b],[000…000,r-1]*[A,b])=([A,b],[A,b+r-1])=([A,b],[A,b-1]),因为[100⋯000,0]*[A,b]=[(100⋯000)×Cbj+A,b+0]=[(100⋯000)×[000⋯0100⋯00000⋯0010⋯00000⋯0001⋯00⋮⋮⋮⋱⋮⋮⋮⋮⋱⋮⋮000⋯0000⋯01100⋯0000⋯00010⋯0000⋯00001⋯0000⋯00⋮⋮⋮⋱⋮⋮⋮⋮⋱⋮⋮000⋯1000⋯00]+A,b]=[(00⋯01bj+10⋯00)+A,b]=[(00⋯010⋯00)+(a1a2⋯ak+j-1ak+j),b]=[a1a2⋯ˉabj+1⋯ak+j-1ak+j,b],有因为[100⋯000,0]*[A,b]=[(100⋯000)×Cbj+A,b+0]=[(100⋯000)×⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢000⋮0100⋮0000⋮0010⋮0000⋮0001⋮0⋯⋯⋯⋱⋯⋯⋯⋯⋱⋯000⋮0000⋮1100⋮0000⋮0010⋮0000⋮0001⋮0000⋮0⋯⋯⋯⋱⋯⋯⋯⋯⋱⋯000⋮0000⋮0000⋮1000⋮0⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥+A,b]=[(00⋯01bj+10⋯00)+A,b]=[(00⋯010⋯00)+(a1a2⋯ak+j−1ak+j),b]=[a1a2⋯a¯bj+1⋯ak+j−1ak+j,b],有([A,b],[100⋯000,0]*[A,b])=([A,b],[a1a2⋯ˉabj+1⋯ak+j-1ak+j,b]).([A,b],[100⋯000,0]*[A,b])=([A,b],[a1a2⋯a¯bj+1⋯ak+j−1ak+j,b]).同样地‚有([A,b],[010⋯000,0]*[A,b])=([A,b],[a1a2⋯ˉabj+2⋯ak+j-1ak+j,b])‚⋯‚([A,b],[00⋯01k0⋯00,b]*[A,b])=([A,b],[a1a2⋯ˉabj+k⋯ak+j-1ak+j,b]).同样地‚有([A,b],[010⋯000,0]*[A,b])=([A,b],[a1a2⋯a¯bj+2⋯ak+j−1ak+j,b])‚⋯‚([A,b],[00⋯01k0⋯00,b]*[A,b])=([A,b],[a1a2⋯a¯bj+k⋯ak+j−1ak+j,b]).由定义3可知RCR(k,r,j)是Cayley图.证毕.需要注意的是这里所定义关于运算*的群不是交换群.例如,可以假设[A,b]=[010…000,b]和[X,y]=[100…000,y]都在(Z2)n×Zr中.因为另一