N维立方体的性质盛集明（荆楚理工学院数理学院湖北荆门）摘要：n维立方体是一个n-正则的二部图，既有实际应用价值又有理论价值.文中首先证明了当A为有限集时，的Hasse图就是一个n维立方体，从而建立了有限布尔代数与n维立方体之间的关系；然后证明了：n维立方体是Hamilton图及非平面图，并且给出了一个具体构造Hamilton圈的方法．关键词：N维立方体；Hasse图；Hamilton图；正则图；二部图；平面图中图分类号：O157．5MR（2000）：05C40文献标识码：APropertiesoftheN-CubeShengJi-ming(MathematicsDepartment,Jingchuinstituteoftechnology,Jingmen,Hubei,,China)Abstract:An-cubeisan-regularbipartitegraph.Ithasbothactualvalueandtheoreticalvalue.First,weprovethattheHassegraphofisan-cubewhenthesetAislimited，whichestablishedtherelationshipbetweenalimitedBooleanalgebraandan-cube.Then,weprovethatan-cubeisaHamiltonianandnon-planargraph,andgiveamethodofconstructingaHamiltoncycleinthegraphofn-cube.Keywords:n-cube;Hassegraph;Hamiltonian;regulargraph;bipartitegraph;planargraph.在高性能计算研究方面，一个非常重要的研究方向是网络并行计算，而决定并行计算性能的重要因素是网络拓扑结构。网络拓扑结构通常用图来表示，其中图中点表示处理机，图中边表示处理机之间的通信连接。网络中信件传输的有效性通常用网络容错性、传输延迟等来度量，而这些性能参数在图中就是图的连通度、直径等概念。由于n维立方体具有正规性、对称性、可靠性、直径短等特点而成为并行计算网络中非常重要的网络拓扑结构。文中对n维立方体的基本性质作了一个系统的研究，特别是建立了n维立方体与有限布尔代数之间的联系。1n维立方体定义1.1[1]:已知图，若G满足：并且若，有（1.1）则称图G为n维立方体，并记作.由的定义易知是简单图，而且中元素与分量取值为0或1的n维向量一一对应，而后者恰有个向量，所以.图1所示的图分别是.显然，由的定义知，在中点与点之间有边相连的充要条件是对任意的，有且仅有一个，使得，其余(n-1)个均相同.11011011111001101000010101100001000110011111111110010001011101110000100011101110100000000110011000图1n维立方体（n=1,2,3,4）2有限幂集的Hasse图定义2.1[2]:由两个元素x和y按一定次序排列而成的二元组叫做一个有序对或序偶，记作<x，y>．定义2.2[2]:设A、B为两个集合，定义集合为A和B的笛卡尔积，记作．定义2.3[2]:设A、B为两个集合，的任何子集R称为从A到B的一个二元关系；特别当A=B时，R叫做A上的二元关系．定义2.4[2]:设R为A上的二元关系：（1）若任意，都有，则称R为A上的自反关系．（2）若任意，当，都有x=y，则称R为A上的反对称关系．（3）若任意，当，都有，则称R为A上的传递关系．定义2.5[2]:设R为非空集合A上的二元关系，若R是自反的、反对称的、传递的，则称R为A的偏序关系，记作．设为偏序关系，如果，则记作，读作x“小于或等于”y．注意这里的“小于或等于”不是指数的大小，而是指在偏序关系中的顺序性．定义2.6[2]:非空集合A及A上的偏序关系一起称为偏序集，记作<A,>已知偏序集<A,>，若A的元素个数为有限个，则称<A,>为有限偏序集．若且，记作。若且不存在使，则称x是y的一个覆盖，并记作。定义2.7[2]：已知有限偏序集<A,>，按如下方法构造Hasse图：1）用平面上的点表示A中的元素。2）若，则将y画在x的上层，并在x、y之间用一条曲线段相连。3）若x、y之间没有关系，则把x、y画在同一层上。已知集合，显然集合A的幂集上的关系满足：自反性、反对称性和传递性，所以是偏序集。下面讨论中元素的表示方法及Hasse图的特征。定理2.1:已知，，定义到的一个函数f如下()：其中则是一个双射证明：由f的定义可知f是到的一个函数（1）对，令显然有所以f是满射（2）且所以f是单射由（1）（2）可知f是双射□由于中的元素与中的元素之间一一对应，故可用中的元素来表示中的元素，即，其中定理2.2:已知集合，，则：（1）（2）证明：（1），而所以有（2）由覆盖的定义：先证充分性：由条件知显然有，所以有；又因为，所以有且S2刚好比S1多一...