论文部分内容阅读
限制超立方体类网络是目前发现的非常重要的一类网络拓扑结构,它的不相交的路覆盖性质是近些年非常重要的研究课题.多对多指定型k条不相交的路覆盖(简称k-DPC)是连接图G的任意k个源点与k个终点之间的k条路,每条路之间没有公共点且包含图中所有顶点.如果有错误边或点时,要求这些路不能经过错误边或点,即无错的不相交的路覆盖.在本文中我们分析了低维限制超立方体类网络的不相交的路覆盖情况,在此基础上利用两条不相交的路覆盖的结论,我们证明了限制超立方体类网络RHLm(Restricted hypercube-like graphs)(m≥6)在含有m-5个错误边或点的情况下有多对多指定型三条不相交的路覆盖. 本研究分为三个部分:第一章绪论部分.主要介绍了本文用到的图论的基本概念、相关的研究背景和现状及主要研究工作和方法;第二章总结了限制超立方体类网络的定义与性质。在第一节引入了限制超立方体类网络和局部交叉立方体的定义。在第二节介绍了限制超立方体类网络在顶点集的度,路和圈的嵌入,汉密尔顿等方面的性质,并且证明了m维限制超立方体顶点集满足一定条件时邻集的阶大于等于2m-2,以及证明了一个比含有汉密尔顿圈更强的性质;第三章对限制超立方体类网络的不相交的路覆盖问题进行了分析,讨论了低维的限制超立方体类网络不相交的路覆盖的情况,例举了三维和四维限制超立方体类网络不存在不相交的路覆盖的例子,并证明了在含有m-5个错误边或点的限制超立方体类网络中,任意三个源点及三个终点之间,一定存在三条无错的多对多指定型不相交的路覆盖。