两类网络的偶泛圈性和路覆盖

发布时间：2017-09-03 12:42

  本文关键词：两类网络的偶泛圈性和路覆盖

  更多相关文章： 超立方体 平衡超立方体 不相交路覆盖 容错性 偶泛圈性

【摘要】：互连网络的拓扑结构是一个图,由含圈拓扑结构的图设计出来的网络通讯成本低,应用范围广,因此圈嵌入一直是图论和计算机领域研究的热点.泛圈性是圈嵌入的延伸,研究从围长到顶点个数任意长度的圈嵌入.实际中网络的顶点和链接都可能发生故障,因此容错泛圈性的研究具有极大实际意义.不相交路是指顶点不相交的路,图的不相交路覆盖要求不相交路包含图中的所有点.对应到网络上意味着网络中所有顶点都可以参与并行路的数据路由.不相交路覆盖的研究有利于网络资源的优化利用,能够应用在编码优化、数据库设计等领域.n-维超立方体Qn是并行处理和并行计算系统的首选结构,随着信息科技的发展,人们对于网络结构的要求越来越高,许多超立方体的变形网络如平衡超立方体、折叠超立方体等相继被提出,它们具有许多优于超立方体网络的性质.本文中结合数学归纳推理和分类讨论的方法,对超立方体和平衡超立方体分别进行边容错偶泛圈性和不相交路覆盖的研究.论文组织结构如下：第一章绪论中主要介绍了论文中用到的图论基本概念以及图的不相交路覆盖、容错圈嵌入研究的相关背景知识和研究现状.第二章中详细介绍了论文中主要研究的两个网络：超立方体和平衡超立方体,分别给出了定义、相关概念以及与本论文相关的性质结论.第三章中证明了超立方体Qn的容错偶泛圈性.设F是超立方体Qn(n≥6)的一个错误边集且|F|≤3n-7,如果满足(1)Qn中每个点至少关联两条好边和(2)Qn-F中既无f4-圈,也无f6-圈,则Qn中存在长度为l的偶圈,其中l是介于4到2n的任意偶数.第四章中证明了平衡超立方体BHn的配对的3-不相交路覆盖,证明当n≥3时,设源点集S(?)B和汇点集T(?)W,则BHn中存在以S∪T为端点集的3-不相交路覆盖,其中B和W是BHn中黑点集和白点集.这一结论推广了Cheng等在[Applied Mathematics and Computation,2014,242:127-142]中给出的BHn中的配对的2-不相交路覆盖的结果.第五章结束语对本文进行了总结,并给出了进一步的研究方向.
【关键词】：超立方体 平衡超立方体 不相交路覆盖 容错性 偶泛圈性
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 致谢5-6
• 中文摘要6-7
• ABSTRACT7-10
• 第一章 绪论10-16
• 1 研究背景和意义10-11
• 2 基本概念和预备知识11-13
• 3 研究现状13-16
• 第二章 超立方体及平衡超立方体定义及性质16-22
• 1 超立方体16-19
• 2 平衡超立方体19-22
• 第三章 超立方体的边容错偶泛圈性22-39
• 1 预备引理证明22-23
• 2 超立方体中存在3n-7条错误边时的边容错偶泛圈性23-39
• 第四章 平衡超立方体的不相交路覆盖39-50
• 1 预备引理证明39-40
• 2 平衡超立方体中配对的3-不相交路覆盖40-50
• 第五章 结束语50-51
• 参考文献51-55
• 附录55-63
• 作者简历63-65
• 学位论文数据集65

【相似文献】

中国期刊全文数据库 前10条

1 马美杰,徐俊明;交叉超立方体网络的边泛圈性(英文)[J];中国科学技术大学学报;2005年03期

2 徐露霞;陈芳跃;;n维超立方体中隐含低维超方体的计数问题[J];杭州电子科技大学学报;2012年02期

3 范漪涵;刘红美;刘敏;;故障折叠超立方体中的路和圈(英文)[J];数学杂志;2013年03期

4 侯晶;张先迪;;广义超立方体网络的容错性和通信延迟[J];电子科技大学学报;2006年02期

5 高志军;蔡颖;杜杰;温宇鹏;;超立方体三次幂的可区别数研究[J];大连海事大学学报;2006年02期

6 公维凤;刘红美;宦红伦;谢炜;;广义超立方体网络中一类容错路由选择[J];数学的实践与认识;2006年09期

7 高志军;李懿;张绍兵;;超立方体的边可区别数[J];黑龙江科技学院学报;2007年05期

8 高志军;李懿;何鸣;;维数不超过7的超立方体三次幂的可区别数[J];黑龙江科技学院学报;2008年01期

9 杜正中;经};马美杰;徐俊明;;容错超立方体网络的圈嵌入(英文)[J];中国科学技术大学学报;2008年09期

10 佘卫强;方来金;;边故障超立方体中两条无故障点不交路[J];漳州师范学院学报(自然科学版);2009年01期

中国重要会议论文全文数据库 前7条

1 马美杰;徐俊明;杜正中;;超立方体网络的边容错泛连通性与折叠超立方体网络的边容错边泛圈性(英文)[A];中国运筹学会第七届学术交流会论文集（下卷）[C];2004年

2 许艳;;超立方体切面中的样条方法[A];第六届全国几何设计与计算学术会议论文集[C];2013年

3 司沛;杨小帆;刘怀义;王灿;孙丽萍;;局部扭曲立方体的边泛圈性[A];2008年计算机应用技术交流会论文集[C];2008年

4 公维凤;王传会;刘红美;;广义超立方体的容错路由选择[A];第八届中国青年运筹信息管理学者大会论文集[C];2006年

5 张军英;许进;保铮;;一类离散Hopfield网的特征分析(Ⅱ)——稳定吸引状态的结构[A];1999年中国神经网络与信号处理学术会议论文集[C];1999年

6 张军英;许进;保铮;;一类离散Hopfield网的特征分析(Ⅰ)—稳定吸引状态[A];1999年中国神经网络与信号处理学术会议论文集[C];1999年

7 张修梅;;关于超立方体与M銉bius立方体的连接[A];第八届中国青年运筹信息管理学者大会论文集[C];2006年

中国重要报纸全文数据库 前2条

1 高博;超立方体可充当纳米计算机结构[N];科技日报;2008年

2 冯卫东;越小越精[N];科技日报;2008年

中国博士学位论文全文数据库 前6条

1 陈浩;复杂结构拉丁超立方体设计的构造[D];南开大学;2013年

2 王海亮;超立方体网络的容错泛连通性[D];中国科学技术大学;2009年

3 杜正中;容错网络的路和圈研究[D];中国科学技术大学;2006年

4 王国军;具有大量错误结点的超立方体网络容错模型和容错路由算法研究[D];中南大学;2002年

5 王洪伟;超立方体网络中多播路由优化策略研究[D];哈尔滨工业大学;2013年

6 经衿;某些容错网络的嵌入研究[D];中国科学技术大学;2009年

中国硕士学位论文全文数据库 前10条

1 黄莹;交换超立方体网络的故障诊断策略研究[D];广西大学;2015年

2 刘秀丽;类超立方体网络的g好邻条件诊断度[D];太原科技大学;2015年

3 罗欢;三类网络在PMC模型下的悲观诊断[D];北京交通大学;2016年

4 郭美荣;两类网络的偶泛圈性和路覆盖[D];北京交通大学;2016年

5 文盼;限制超立方体类网络的不相交的路覆盖[D];北京交通大学;2016年

6 马良;超立方体网络上与距离相关的容错性研究[D];苏州大学;2016年

7 乔宏伟;超立方体的生成连通性质以及对换网络的可系性[D];新疆大学;2016年

8 高志军;超立方体可区别数的研究[D];大连海事大学;2006年

9 吴智霞;折叠超立方体的容错泛圈性[D];北京交通大学;2012年

10 张茹;平衡超立方体的限制边连通性[D];北京交通大学;2012年

，

本文编号：785107