网络泛圈性与泛连通性的研究

来源 :中国科学技术大学 | 被引量 : 0次 | 上传用户:whicky
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
我们通常用一个连通的无向图G=(V,E)作为互连网络的拓扑结构,这时图G的顶点代表网络中的组件,组件之间的通信联系用相应顶点之间的连线来表示.网络的拓扑结构决定着该网络的性能.可嵌入性是度量网络优劣的一个重要性能.一个网络是否具有泛圈性可以度量该网络是否可以嵌入任意长度的圈.泛连通性是泛圈性的深化,如果一个网络是泛连通的则一定是泛圈的.一个大型网络在投入使用的过程中,它的某些组件和连线难免会发生故障.我们所说的网络容错性是指该网络能容忍多少组件和(或)连线同时发生故障,剩余的子网络中仍然含有某些特殊结构.故考虑网络的容错性具有实际意义. 本文主要研究几个著名网络的泛圈性、泛连通性和边容错泛圈性、泛连通性.全文共分五章. 第一章介绍了本文用到的一些图和网络的基本概念,泛圈性和泛连通性的定义,几个著名的网络的定义以及目前已经取得的一些结果. 第二章研究了几个著名网络的泛圈性.首先,研究了折叠立方体网络FQn(n≥2)的边泛圈性,根据它的维数n的不同的奇偶性,证明了它的每条边位于不同长度的奇圈或偶圈上;然后,证明了交叉立方体网络CQn(n≥2),局部纽立方体网络LTQn(n≥2)的每条边位于一个长为e的圈上,其中4≤e≤2n;通过证明类立方体网络的点泛圈性,用统一的方式证明了交叉立方体网络,Mobius立方体网络,纽立方体网络以及局部纽立方体网络等具有小的直径的超立方体网络的一些变型的点泛圈性.统一了前人的证明. 第三章研究几个著名网络的泛连通性.对于折叠立方体网络FQn中的距离为d的两点x和y,它们之间存在长为e的xy路,其中h≤e≤2n-1,h∈{d,n+1-d}且e与h具有相同的奇偶性;对交叉立方体网络CQn(n≥3),Mobius立方体网络MQn(n≥3),局部纽立方体网络LTQn(n≥3)中的任意两点u和v,存在长为e的uv路,其中d(u,v)+2≤e≤2n-1. 第四章研究了超立方体网络的边容错泛连通性,折叠立方体网络的边容错边泛圈性以及限制边容错哈密顿性,得到了以下几个结果: 1.如果超立方体网络Qn(n≥2)的故障边集为F且|F|≤n-2,则对Qn中任意两点u和v,存在长为e的不含故障边的uv路,其中dQn(u,v)+2≤e≤2n-1且2|(e-dQn(u,v)).如果dQn(u,v)≥n-1,则还存在长为dQn(u,v)的不含故障边的uv路. 2.当n≥3时,如果n是奇数,则FQn是(n-1)边容错边偶泛圈的.如果n是偶数,FQn的故障边集为F且|F|≤n-1,则FQn-F中任意一条边e位于长为e的偶圈上,还位于长为e’的奇圈上,其中4≤e≤2n,n+1≤e’≤2n-1. 3.在n(≥3)维折叠立方体网络FQn中,如果故障边集F满足|F|≤2n-3,且FQn-F中的每个顶点至少与两条边相邻,则FQn-F含有哈密顿圈. 在第五章中,对本文的工作进行了总结,并且提出了几个有待进一步研究的问题.
其他文献
众所周知,当给参数指定为非正常先验分布时,使用贝叶斯因子(BF)作假设检验并不合适,且在潜在变量模型中,使用贝叶斯因子(BF)的另一问题是它难于计算。Bernardo和Rueda(2002)(BR)
Verma型模在仿射Kac-Moody代数和toroidal李代数的表示理论中已有很多研究,包括一类非常特殊的虚拟Verma模.文献[7]对仿射Kac-Moody代数定义了以一个函数ψ为参量的ψ-虚拟Ver
本文针对非线性系统的相似约化,变量分离,局域激发模式以及同宿轨道等问题,做了以下工作: 1.Lie点对称的方法推广到(1+1)维Toda-like晶格和(2+1)维特殊Toda晶格上。求出相应的
随着可持续发展观念的提出,越来越提倡在建造建筑物的过程中,应用节能产品以及技术。通过将绿色环保技术应用在建筑设计中,尽量不要使用制冷以及保温消耗,可以有效地提升资源
近年来随着我国综合国力的不断提高,城市化进程的速度加快,越来越多的城市实施不同程度的规划建设工程,所以我国建筑市场出现了异常活跃的阶段,越来越多的建筑企业被兴建起来
数据库自然语言界面(NLIDB)是自然语言处理(NLP)最早和最广泛的研究领域之一,它主要涉及到自然语言处理和数据库系统的研究,是一个具有重大理论价值和巨大实用价值的研究领域。
  本文详细介绍了静态影像的压缩标准-JPEG的压缩过程,以及动态影像的压缩标准-MPEG系列,总结了像素域上基于颜色的图像检索算法;压缩域上图像和视频的特征提取的方法。  
高层住宅建筑防火设计是提升高层建筑安全性和适用性的重中之重,随着高层建筑规模的增大,设计师多关注建筑总体的功能布置、艺术造型、空间利用问题,往往忽视了超高层建筑设