N维立方体的性质.doc

N维立方体的性质 盛集明 （荆楚理工学院 数理学院 湖北荆门 448000） 摘要：n维立方体是一个n-正则的二部图，既有实际应用价值又有理论价值. 文中首先证明了当A为有限集时，的Hasse图就是一个n维立方体，从而建立了有限布尔代数与n维立方体之间的关系；然后证明了：n维立方体是Hamilton图及非平面图，并且给出了一个具体构造Hamilton圈的方法． 关键词：N维立方体；Hasse图；Hamilton图；正则图；二部图；平面图 中图分类号：O157．5MR（2000）Abstract: A n-cube is a n-regular bipartite graph. It has both actual value and theoretical value. First, we prove that the Hasse graph of is a n-cube when the set A is limited，which established the relationship between a limited Boolean algebra and a n-cube. Then, we prove that a n-cube is a Hamiltonian and non-planar graph, and give a method of constructing a Hamilton cycle in the graph of n-cube. Key words: n-cube; Hasse graph; Hamiltonian; regular graph; bipartite graph; planar graph. 在高性能计算研究方面，一个非常重要的研究方向是网络并行计算，而决定并行计算性能的重要因素是网络拓扑结构。网络拓扑结构通常用图来表示，其中图中点表示处理机，图中边表示处理机之间的通信连接。网络中信件传输的有效性通常用网络容错性、传输延迟等来度量，而这些性能参数在图中就是图的连通度、直径等概念。由于n维立方体具有正规性、对称性、可靠性、直径短等特点而成为并行计算网络中非常重要的网络拓扑结构。文中对n维立方体的基本性质作了一个系统的研究，特别是建立了n维立方体与有限布尔代数之间的联系。 1 n维立方体 定义1.1[1]: 已知图，若G满足： 并且若，有 （1.1） 则称图G为n维立方体，并记作. 由的定义易知是简单图，而且中元素与分量取值为0或1的n维向量一一对应，而后者恰有个向量，所以.图1所示的图分别是. 显然，由的定义知，在中点与点之间有边相连的充要条件是对任意的，有且仅有一个，使得，其余(n-1)个均相同. 图1 n维立方体（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上的二元关系： 若任意，都有，则称R为A上的自反关系． 若任意，当，都有x=y，则称R为A上的反对称关系． 若任意，当，都有，则称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图： 用平面上的点表示A中的元素。 若，则将y画在x的上层，并在x、y之间用一条曲线段相连。 若x、y之间没有关系，则把x、y画在同一层上。 已知集合，显然集合A的幂集上的关系满足：自反性、反对称性和传递性，所以是偏序集。下面讨论中元素的表示方法及Hasse图的特征。 定理2.1: 已知，，定义到的一个函数f如下()： 其中 则是一个双射 证明：由f的定义可知f是到的一个函数 对，令显然有 所以f是满射 （2）且 所以f是单射 由（1）（2）可知f是双射 □ 由于中的元素与中的元素之间一一对应，故可用中的元素来表示中的元素，即 ，其中