图的对称性和容错性分析

发布时间：2017-12-09 08:39

  本文关键词：图的对称性和容错性分析

  更多相关文章： 对称图 正则覆盖 Basic图 圈嵌入 外连通度

【摘要】：称图Γ是对称图或弧传递图,如果r的全自同构群作用在r的弧集上传递.对称图,特别是小度数对称图,常被用来设计互连网络.互连网络投入使用过程中出现故障是不可避免的,这就要求互连网络应该具有一定的容错性.而图的一些定义和性质可以用来有效的评估互连网络的容错性.本文主要研究五度对称图的分类和构造,以及讨论两类基于对称图设计的互连网络的容错性.论文结构组织如下.第1章绪论部分,主要介绍了本文所要用到的有限群论和图论的基本概念,以及与图的对称性和容错性研究相关的背景知识和本文的主要研究工作.第2章研究二倍素数阶连通五度对称图的正则覆盖.称一个连通图的正则覆盖为循环覆盖或二面体覆盖,如果其覆盖变换群分别是循环群或二面体群.如果保簇自同构群作用在覆盖图上弧传递,则称此覆盖为弧传递覆盖或对称覆盖.本章给出了二倍素数阶连通五度对称图的弧传递循环覆盖和二面体覆盖的完全分类.所有的覆盖图都是以凯莱图的形式构造出来,而且它们的全自同构群也被完全决定.第3章研究小整数倍素数幂阶五度对称图.一个连通的素数度对称图是Basic图,如果其全自同构群不包含非平凡的正规子群作用在顶点集合上有多于两个轨道.设p是一个素数.首先,我们给出了2p3阶连通五度对称图的完全分类.所有的2p3阶连通五度对称图都是某个2p3阶群上的正规凯莱图,而且其全自同构群也被完全决定.证明了当p=3时,不存在2p3阶连通的五度对称图；当p=2或5时,在同构意义下只有一个2p3阶连通的五度对称图；当p≥7时,有七个无限类图,其中六类当且仅当5 |(p-1)时存在而且为1-正则图,另外一类当且仅当5 |(p士1)时存在而且为1-传递非1-正则图.其次,我们给出了4pn阶和6pn阶连通五度Basic图的完全分类,其中n是一个非负正整数.证明了在同构意义下,只有两个4pn阶连通五度Basic图,阶分别为16和36；有五个6pn阶连通五度Basic图,阶分别为6,42,66,114和162.作为应用,我们给出了4p2,4p3和6p2阶连通五度对称图的完全分类.4p阶和6p阶连通五度对称图在[Discrete Mathematics,2011 (311):2259-2267]中已经被分类.第4章给出了无平方因子阶连通五度对称图的一个刻画.作为应用,2pqr阶连通五度对称图被完全分类,其中rqp是三个奇素数.第5章研究n-维超立方体网络Qn和n-维平衡超立方体网络BHn的容错性分析.首先,我们从容错圈嵌入方面分析Qn的容错性.设F是Qn的一个错误集,fv,和fe分别是F中错误顶点和错误边的个数.称一条边e是自由边,如果e以及其两个端点均不在F中.图Γ的一个圈是无错圈,如果它既不包含F中的点又不包含F中的边.我们证明了当n≥3时,如果fv+fe≤2n-5,fe≤n-2且每个无错顶点至少关联两条自由边,那么Qn的每条自由边都位于长从6到2n -2fv的无错偶圈中.这一结论证实了Tsai在[Information Processing Letters,2007(102):242-246]中提出的一个猜想.最后,我们从外连通度方面分析BHn的容错性,其中n≥2.连通图Γ的h-外、连通度,记为Kh(Γ),是指去掉最少的顶点的个数使得Γ不连通且每个连通分支至少含有h+1个顶点Yang在[Applied Mathematics and Computation,2012(219):970-975]中证明了K1(BHn)=4n-4.本章,我们推广了Yang关于BHn的外连通度的结论,证明了κ2(BHn)=κ3(BHn)=4n-4,κ4(BHn)=κ5(BHn)=6n-8,以及给出了κh(BHn)的一个上界,其中h≤2n-1.第6章讨论一些有待研究的问题.
【学位授予单位】：北京交通大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O157.5
，

本文编号：1269777