N维立方体的性质

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业N维立方体的性质盛集明（荆楚理工学院 数理学院 湖北荆门 ）摘要：n维立方体是一个n-正则的二部图，既有实际应用价值又有理论价值. 文中首先证明了当A为有限集时，的Hasse图就是一个n维立方体，从而建立了有限布尔代数与n维立方体之间的关系；然后证明了：n维立方体是Hamilton图及非平面图，并且给出了一个具体构造Hamilton圈的方法 关键词：N维立方体；Hasse图；Hamilton图；正则图；二部图；平面图 中图分类号：O1575 MR（2000）：05C40

2、 文献标识码：AProperties of the N-CubeSheng Ji-ming(Mathematics Department,Jingchu institute of technology,Jingmen,Hubei,China)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，wh

3、ich 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;

4、planar graph.在高性能计算研究方面，一个非常重要的研究方向是网络并行计算，而决定并行计算性能的重要因素是网络拓扑结构。网络拓扑结构通常用图来表示，其中图中点表示处理机，图中边表示处理机之间的通信连接。网络中信件传输的有效性通常用网络容错性、传输延迟等来度量，而这些性能参数在图中就是图的连通度、直径等概念。由于n维立方体具有正规性、对称性、可靠性、直径短等特点而成为并行计算网络中非常重要的网络拓扑结构。文中对n维立方体的基本性质作了一个系统的研究，特别是建立了n维立方体与有限布尔代数之间的联系。1 n维立方体定义1.11: 已知图，若G满足：并且若，有 （1.1）则称图G为n维立方体

5、，并记作.由的定义易知是简单图，而且中元素与分量取值为0或1的n维向量一一对应，而后者恰有个向量，所以.图1所示的图分别是.显然，由的定义知，在中点与点之间有边相连的充要条件是对任意的，有且仅有一个，使得，其余(n-1)个均相同.1 10 11 011 111 001 101 0 00 01 010 110 000 100 0110 0111 1111 1110 0100 0101 1101 1100 0010 0011 1011 1010 0000 0001 1001 1000 图1 n维立方体（n=1,2,3,4）2 有限幂集的Hasse图定义2.12: 由两个元素x和y按一定次序排列而成

6、的二元组叫做一个有序对或序偶，记作定义2.22: 设A、B为两个集合，定义集合为A和B的笛卡尔积，记作定义2.32: 设A、B为两个集合，的任何子集R称为从A到B的一个二元关系；特别当A=B时，R叫做A上的二元关系定义2.42: 设R为A上的二元关系：若任意，都有，则称R为A上的自反关系若任意，当，都有x=y，则称R为A上的反对称关系若任意，当，都有，则称R为A上的传递关系定义2.52: 设R为非空集合A上的二元关系，若R是自反的、反对称的、传递的，则称R为A的偏序关系，记作设为偏序关系，如果，则记作，读作x“小于或等于”y 注意这里的“小于或等于”不是指数的大小，而是指在偏序关系中的顺序性定

7、义2.62: 非空集合A及A上的偏序关系一起称为偏序集，记作已知偏序集，若A的元素个数为有限个，则称为有限偏序集若且，记作。若且不存在使，则称x是y的一个覆盖，并记作。定义2.72：已知有限偏序集，按如下方法构造Hasse图：用平面上的点表示A中的元素。若，则将y画在x的上层，并在x、y之间用一条曲线段相连。若x、y之间没有关系，则把x、y画在同一层上。已知集合，显然集合A的幂集上的关系满足：自反性、反对称性和传递性，所以是偏序集。下面讨论中元素的表示方法及Hasse图的特征。定理2.1: 已知，定义到的一个函数f如下()： 其中则是一个双射证明：由f的定义可知f是到的一个函数对，令显然有所以

8、f是满射（2）且所以f是单射由（1）（2）可知f是双射 由于中的元素与中的元素之间一一对应，故可用中的元素来表示中的元素，即，其中定理2.2: 已知集合，则：（1）（2）证明：（1） ，而所以有 （2）由覆盖的定义：先证充分性：由条件知显然有，所以有；又因为，所以有且S2刚好比S1多一个元素，因此不可能存在S，使得。故有再证必要性：下证这样的i只有一个，用反证法。假设至少有两个这样的i，不妨设e有，那显然是，则有：，则存在，矛盾。故只有一个i，使得，即 已知集合，记的哈斯图为Hn（如图2：H1，H2，H3）.下面研究Hn的特征： 1 11 111 10 01 110 101 011 100 0

9、10 001 0 00 000 H1 H2 H3 图2：有限幂集的Hasse图H1,H2,H3，由Hasse图的画法可知：S1与S2之间有边的充要条件是，而由定理2.2的（2）知：的充要条件是对任意的，有且仅有一个i，使得，其余(n-1)个均相同.这与n维立方体的定义完全一致，所以有如下结论：定理2.3：已知集合，则的哈斯图Hn同构于.3 n维立方体的性质定理3.1：是2部图.证明：令，其中：下证X，Y是的2部划分.(1)显然有，(2)若存在和使，则应有，即有.这与矛盾.所以X中任何两顶点间无边相连，同样可证Y中任何两顶点之间也无边相连.所以 是2部划分为X，Y的2部分图. 定理3.2：是n-

10、正则简单图.证明：任取，由于中与u相邻的顶点满足，即其分量取值0或1的两个n维向量和中分量有且仅有一个不同，其余(n-1)个均相同，显然这样的v恰有n个，所以中与u关联的边有n条。由u的任意性知是n-正则简单图. 由定理3.2知：中的边数为.定义3.1：定义图,其中并且若,则定义图,其中并且若,则显然,定理3.3：,其中为的一个1-因子,且证明: 而中的点都分别属于,且,且同理:,其中又由可知, 定理3不仅说明在中存在一个1-因子,而且删除该1-因子后,恰好得到两个.定理3.4：()是Hamilton图.证明：采用两种方法证明方法一:在中构造一个Hamilton圈.初始值:令，并且，即.第一步

11、：令中的，其它保持不变，得到，即.第二步：按的顺序，分别令中的，其它保持不变，得到，即.第三步：按的顺序，分别令中的，其它保持不变，得到，即.第步：按的顺序，分别令中的，其它保持不变，得到.第n步: 按的顺序，分别令中的，其它保持不变，得到.显然.由上述过程可知：互不相同，恰好为n维立方体的个点，下证相邻两点满足（1.1）式：显然满足（1.1）式，是将中的同时变为1，所以也满足（1.1）式，同理中相邻两点满足（1.1）式，中相邻两点满足（1.1）式.是由改变一个得来，所以满足（1.1）式，是由改变一个得来，所以满足（1.1）式，是由改变一个得来，所以满足（1.1）式.由上可知：中任相邻两点都满

12、足（1.1）式，而与显然也满足（1.1）式，故构成一个Hamilton圈，所以是Hamilton图. 方法二:用数学归纳法.显然当n=2时,是Hamilton图.假设是Hamilton图,下证也是Hamilton图.因为 ,而,由假设知:是Hamilton图,所以在中分别存在Hamilton圈:.不妨设,其中,.显然有,.显然在中存在Hamilton圈:,故是Hamilton图.由归纳法可知:对任意的n, 都是Hamilton图. 例如，在中，按照方法一有：初始赋值：第一步：令中的，其它保持不变，得第二步：按的顺序，分别令中的，其它保持不变，得第三步：按的顺序，分别令中的，其它保持不变，得第四

13、步：按的顺序，分别令中的，其它保持不变，得，所以有：Hamilton圈：0000-1000-1100-0100-0110-1110-1010-0010-0011-1011-1111-0111-0101-1101-1001-0001-0000定理3.5：()是非平面图.证明：用反证法。假设()是平面图，由欧拉公式有：(其中分别表示的点数、边数、面数)一方面因为为二部图，可知中每个面至少由4条边围成，这样f个面的总边数大于或等于4f，另一方面，因为一条边至多在两个面的边界中，所以上述计算的总边数小于或等于，因此有，代入欧拉公式得：，即但在()中，代入上式有：，矛盾。所以()是非平面图。 显然是平面图。参考文献：1 徐俊明. 图论及其应用（第二版）M. 合肥: 中国科学技术大学出版社. 2004.2 洪帆. 离散数学基础（第二版）M. 武汉: 华中科技大学出版社. 1995.3 Bela Bollobas