有关加强超立方体泛连通性的证明-论文.pdf

《有关加强超立方体泛连通性的证明-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、学园lXUEYUAN2014年第13期有关加强超立方体泛连通性的证明范漪涵刘红三峡大学理学院【摘要】在本文中，我们研究容错加强超立方体Q，中的路和圈的嵌入问题。利用已知的结论当(≥2)和k有不同奇偶性时，Q一{_厂}包含了长从4到2一2容错偶泛圈和长从，z—k+2到2一1的容错奇泛圈；当和k有不同奇偶性时Q，(1≤≤一1)是哈密顿连通的。【关键词】加强超立方体偶泛连通性哈密顿连通性【中图分类号】029【文献标识码】A【文章编号】1674—4810(2014)13—0078—01在互联网络中，一个

2、网络是否可以被另一个网络模拟是现在考虑下面两种情况：非常重要的，这就是我们所说的嵌入问题。超立方体Q是情况1：X和Y在不同的二部划分集中，设“是Q中X现如今最受欢迎的互联网络之一，它具有很多优良的性质，的一个邻点，并且，“≠，“不和Y相邻。因此X和是属如可嵌人性、可迁性、对称性、正则性、递归性等。关于折于Q中不同的二部划分集。从引理可得，不管Q是(一叠超立方体的一些性质，前人已做了很多的研究。然而，对1)．维的加强超立方体还是(一1)．维的超立方体在Q中于更一般的形式，加强超立方体的研究却比较少

3、，我们主要都存在和“之间的一条哈密尔顿路P，并且这条路长为证明：当n和k有不同的奇偶性时，．维加强超立方体Q，2"-1—1。因为∈Q，并且和“相邻，“和Y是属于Q是哈密顿连通的。中不同的二部划分集。从引理可得，不管Q：是(一1)．一预备知识维的加强超立方体还是(一1)．维的超立方体，在Q：中都下面给出一些对于我们的主要证明很重要的一些引理：存在和y之间的一条哈密尔顿路R，并且这条路长为一1。引理1：设厂是FQ中的一个故障点，其中≥3，那么因此P+(”，)+R是，中X和Y之间的一条哈密尔顿路。Q一

4、{“，}包含从4到2一2lFJl任意长，的偶圈，且如果情况2：X和Y在相同的二部划分集中，如果Q和Q是n是偶数，对于"≥2，FQ_厂包含从+1到2“一2任意长z两个("一1)．维的超立方体。设“是Q中的一个邻点且使的奇圈。得0n“中，“不是Y的补边。因此X和是属于QiO中不引理2：n维超立方体是二部图并且是强哈密顿脆弱的。同的二部划分集。从引理可得，在Q中存在X和之间的一引理3：当n和k具有相同奇偶性时，维加强立方体条哈密尔顿路P，并且这条路长为～一1。又因为和具是强哈密顿脆弱的。有不同的奇偶性

5、时，hw()和hw()有相同的奇偶性。引理4：当n=l或者n(≥2)是偶数时，"维折叠超立因为和的奇偶性相同而和”的奇偶性不同，和Y是属于方体FQ是哈密尔顿连通的。Q中不同的二部划分集。由引理可得，在Q中存在和Y引理5：当是奇数时，维折叠超立方体FQ是偶泛之间的一条哈密尔顿路R，且这条路长为2一1。因此P+连通的。(甜，)+R是Q枞中X和Y之间的一条哈密尔顿路。如果Q二加强超立方体的偶泛连通性和哈密顿连通性和Q是两个(”一1)．维的加强超立方体。设“是Q中X下面的一个定理证明了当n和k具有不同的

6、奇偶性时，的一个邻点，且使得“≠。由归纳可知，在Q中存在X和n维加强超立方体Q，的连通性质。之间的一条哈密尔顿路P，且在Q中存在和Y之间的一定理1：当n和k具有不同的奇偶性时，”维加强超立条哈密尔顿路R，并且这两条路的长都为～一1，这P+(“，方体Q，是哈密尔顿连通的。)+R是Q，中X和Y之间的一条哈密尔顿路。证明：我们对n用归纳假设法来证明这个定理，从引理三小结可知，当=1，一是偶数时，这个定理是成立的。现在我们在互联网络中，圈和路的嵌入问题是一个非常重要的课考虑≥3的情况，当n=3，k=2时

7、，这个结果很明显是成题。而对于作为超立方体变形得到的网络——加强超立方体立的。现在我们来讨论当”，4和”；k有不同的奇偶性时，中的圈和路的嵌入问题更是值得我们讨论。在本文中，我们这个定理也是成立的。设X：XlX2⋯Xn和：=)，2⋯是Q，得到了；当和k的奇偶性不同时，加强超立方体是哈密顿中不同的两个顶点。很明显，存在一个f使得Xi≠。对Q，连通的，即对加强超立方中的任意两个顶点与Y之间必存进行f一划分后得到两个(”一1)．维的加强超立方体或者是在一条长为V(G)一1的路来连接这两个顶点。两个("

8、一1)一维的超立方体Q和Q使得和Y不在同一个子立方体中。不失一般性，我们可以设∈Q和Y∈Q，[责任编辑：李锦雯]一78一