N维立方体的性质

湖北省教育厅重点科研项目（D20083501）荆楚理工学院科学研究项目（ZR200603）作者简介：盛集明(1970-）,男，湖北浠水人，荆楚理工学院数理学院副教授，研究方向：图论及其应用。电话：[phone]，E-mail:[e-mail]维立方体的性质盛集明（荆楚理工学院数理学院湖北荆门448000）摘要：n维立方体是一个n-正则的二部图，既有实际应用价值又有理论价值.文中首先证明了当A为有限集时，),2(A的Hasse图就是一个n维立方体，从而建立了有限布尔代数与n维立方体之间的关系；然后证明了：n维立方体是Hamilton图及非平面图，并且给出了一个具体构造Hamilton圈的方法．关键词：N维立方体；Hasse图；Hamilton图；正则图；二部图；平面图中图分类号：O157．5MR（2000）：05C40文献标识码：APropertiesoftheN-CubeShengJi-ming(MathematicsDepartment,Jingchuinstituteoftechnology,Jingmen,Hubei,448000,China)Abstract:An-cubeisan-regularbipartitegraph.Ithasbothactualvalueandtheoreticalvalue.First,weprovethattheHassegraphof),2(Aisan-cubewhenthesetAislimited，whichestablishedtherelationshipbetweenalimitedBooleanalgebraandan-cube.Then,weprovethatan-cubeisaHamiltonianandnon-planargraph,andgiveamethodofconstructingaHamiltoncycleinthegraphofn-cube.Keywords:n-cube;Hassegraph;Hamiltonian;regulargraph;bipartitegraph;planargraph.2在高性能计算研究方面，一个非常重要的研究方向是网络并行计算，而决定并行计算性能的重要因素是网络拓扑结构。网络拓扑结构通常用图来表示，其中图中点表示处理机，图中边表示处理机之间的通信连接。网络中信件传输的有效性通常用网络容错性、传输延迟等来度量，而这些性能参数在图中就是图的连通度、直径等概念。由于n维立方体具有正规性、对称性、可靠性、直径短等特点而成为并行计算网络中非常重要的网络拓扑结构。文中对n维立方体的基本性质作了一个系统的研究，特别是建立了n维立方体与有限布尔代数之间的联系。1n维立方体定义1.1[1]:已知图),(EVG，若G满足：}.,,2,1},1,0{:{)(21nixxxxGVin并且若)(,2121GVyyyvxxxunn，有1||)(1niiiyxGEuv（1.1）则称图G为n维立方体，并记作))(),((nnnQEQVQ.由nQ的定义易知nQ是简单图，而且)(nQV中元素与分量取值为0或1的n维向量一一对应，而后者恰有n2个向量，所以nnQV2)(.图1所示的图分别是4321,,,QQQQ.显然，由nQ的定义知，在nQ中点nxxxu21与点nyyyv21之间有边相连的充要条件是对任意的ni,,2,1，有且仅有一个i，使得iiyx，其余(n-1)个均相同.11011011111001101000010101100001001Q2Q3Q3图1n维立方体nQ（n=1,2,3,4）2有限幂集的Hasse图定义2.1[2]:由两个元素x和y按一定次序排列而成的二元组叫做一个有序对或序偶，记作x，y．定义2.2[2]:设A、B为两个集合，定义集合ByAxyx,|,为A和B的笛卡尔积，记作BA．定义2.3[2]:设A、B为两个集合，BA的任何子集R称为从A到B的一个二元关系；特别当A=B时，R叫做A上的二元关系．定义2.4[2]:设R为A上的二元关系：（1）若任意Ax，都有Rxx,，则称R为A上的自反关系．（2）若任意Ayx,，当RxyRyx,,且，都有x=y，则称R为A上的反对称关系．（3）若任意Azyx,,，当RzyRyx,,且，都有Rzx,，则称R为A上的传递关系．定义2.5[2]:设R为非空集合A上的二元关系，若R是自反的、反对称的、传递的，则称R为A的偏序关系，记作．设为偏序关系，如果yx,，则记作yx，读作x“小于或等于”y．注意这里的“小于或等于”不是指数的大小，而是指在偏序关系中的顺序性．定义2.6[2]:非空集合A及A上的偏序关系一起称为偏序集，记作A,已知偏序集A,，若A的元素个数为有限个，则称A,为有限偏序集．若yx且yx，记作yx。若yx且不存在Az使yzx，则称x是y的一个覆盖，并记作yx。定义2.7[2]：已知有限偏序集A,，按如下方法构造Hasse图：1）用平面上的点表示A中的元素。01100111111111100100010111011100001000111011101000000001100110004Q42）若yx，则将y画在x的上层，并在x、y之间用一条曲线段相连。3）若x、y之间没有关系，则把x、y画在同一层上。已知集合},,,{21naaaA，显然集合A的幂集A2上的关系满足：自反性、反对称性和传递性，所以,2A是偏序集。下面讨论,2A中元素的表示方法及Hasse图的特征。定理2.1:已知},,,{21naaaA，}1,0{X，定义A2到nX的一个函数f如下(},2,1,|),,,{(21niXxxxxXinn)：),,,()(221nAxxxSfS其中SaSaxiii01则nAXf2:是一个双射证明：由f的定义可知f是A2到nX的一个函数（1）对nnXxxx),,,(21，令},,2,1,1,|{nixAaaSiii显然有),,,()(221nAxxxSfS且所以f是满射（2）ASS2,21且),,,()()(2121nxxxSfSf211SaxSaiii21SS所以f是单射由（1）（2）可知f是双射□由于A2中的元素与nX中的元素之间一一对应，故可用nX中的元素来表示A2中的元素，即},,2,1},1,0{|),,,({22121nixxxxxxxSinnA，其中SaSaxiii01定理2.2:已知集合},,,{21naaaA，AnnyyySxxxS2,212211，则：（1）iiyxniSS1215（2）iiiiyxiyxi，SS,,1,021其余的使得唯一的证明：（1）21SS21,SaSaii都有，而0,111iiiixSaxSa所以有21SSiiyxi,（2）由覆盖的定义：212121,SSSS，SSSS使得且不存在先证充分性：由条件知显然有iiyxi,，所以有21SS；又因为iiiiyxiyxi，,,1,0其余的使得唯一的，所以有21SS且S2刚好比S1多一个元素，因此不可能存在S，使得21SSS。故有21SS再证必要性：iiiiyxtsiyxiSSSS..,2121且下证这样的i只有一个，用反证法。假设至少有两个这样的i，不妨设e有nnmmyxyxtsnm..,，那显然是10nmnmyyxx，则有：12,,,SaaSaanmnm但，则存在211}{SSSaSSm使得，矛盾。故只有一个i，使得iiyx，即1,0,iiyxi使得唯一的□已知集合},,,{21naaaA，记,2A的哈斯图为Hn（如图2：H1，H2，H3）.下面研究Hn的特征：AnnyyySxxxS2,212211，由Hasse图的画法可知：S1与S2之间有边的充要条件是1221SSSS或，而由定理2.2的（2）知：1221SSSS或的充要条件是对任意的1111111001110101011100010001000000H1H2H3图2：有限幂集的Hasse图H1,H2,H36ni,2,1，有且仅有一个i，使得iiyx，其余(n-1)个均相同.这与n维立方体的定义完全一致，所以有如下结论：定理2.3：已知集合},,,{21naaaA，则,2A的哈斯图Hn同构于nQ.3n维立方体的性质定理3.1：nQ是2部图.证明：令)(,nQVYX，其中：)}2(mod1:{)}2(mod0:{21212121nnnnyyyyyyYxxxxxxX下证{X，Y}是nQ的2部划分.(1)显然有YXQVYXn),(，(2)若存在nxxxv21和Xxxxvn21使)(nQEvv，则应有niiixx11||，即有1|)()(|2121nnxxxxxx.这与Xvv,矛盾.所以X中任何两顶点间无边相连，同样可证Y中任何两顶点之间也无边相连.所以nQ是2部划分为{X，Y}的2部分图.□定理3.2：nQ是n-正则简单图.证明：任取)(21nnQVxxxu，由于nQ中与u相邻的顶点nyyyv21满足1||1niiiyx，即其分量取值0或1的两个n维向量),,,(21nxxx和),,(21nyyy中分量有且仅有一个不同，其余(n-1)个均相同，显然这样的v恰有n个，所以nQ中与u关联的边有n条。由u的任意性知nQ是n-正则简单图.□由定理3.2知：nQ中的边数为12nn.定义3.1：①定义图)(),(111nnnQEQVQ,其中},2,1},1,0{|0{)(1211nixxxxQVinn7并且若)(0,01121121nnnQVyyyvxxxu,则1||)(111niiinyxQEvu②定义图)(),(111nnnQEQVQ,其中},2,1},1,0{|1{)(1211nixxxxQVinn并且若)(1,11121121nnnQVyyyvxxxu,则1||)(111niiinyxQEvu显然,111nnnQQQ定理3.3：111MQQQnnn,其中1M为nQ的一个1-因子,且1,,2,1},1,0{,1,0|1211211nixxxxvxxxvvvMinn证明:①nixxxxQVinn,,2,1},1,0{|)(21}1,,2,1},1,0{|1{}1,,2,1},1,0{|0{121121nixxxxnixxxxinin)()(11nnQVQV而1M中的点都分别属于)(),(11nnQVQV②)(0,01121121nnnQVyyyvxxxu,且)(1nQEvu)(,nQVvu,且1||11niiiyx1||1niiiyx)()()(1nnnQEQEQEvu同理:)()(1nnQEQE)(1MEvv,其中1,0121121nnxxxvxxxv)()()(1nnQEMEQEvv又1121212|)(|2)1(|)(|2)1(|)(|nnnnnMEnQ