论文部分内容阅读
我们通常用一个连通的无向图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含有哈密顿圈.
在第五章中,对本文的工作进行了总结,并且提出了几个有待进一步研究的问题.