星图的一种条件连通度

论文摘要

一个网络可以用一个连通图来表示,其中图的顶点表示网络中的组件,边表示两个组件之间的通信信道。图的连通度可以衡量网络的稳定性。一般来说,一个图的连通性越好,它所代表的网络就越稳定。然而,连通度衡量网络的可靠性是有缺陷的[1]。为了弥补这些缺陷,Harary引入了条件连通度的概念[2]。条件连通度的思想是对于G - F的分支进行限制,使它们具有事先给定的图性质。κ2-点连通度就是其中的一种。令图G = （V,E）是没有环和平行边的有限图。κ2（G） = min{|F| | G - F的每一点在G - F中都有至少两个邻点,并且G - F不再连通}。令X是一个群,S是X的子集。有向凯莱图Cay（X,S）是一个有向图,它的点集是X,弧集是{（g,gs） | g∈X,s∈S}。n维-星图Sn是一类凯莱图Cay（Σn,S）,其中Σn表示由{1,···,n}的所有置换构成的群,S = {（1i） |1 < i n}（i = 2,3,···,n）。星图因为具有强对称性（点/边传递图）、高容错度（n - 2）、较小的度（n - 1）、较小的直径（ 32（n - 1） ）和递归的层次结构[3],在网络设计中越来越受到人们的重视。本文主要证明了κ2（Sn） = 6（n - 3）。论文的组织结构如下:在第一章,介绍条件连通度的背景和意义;在第二、三章,我们给出星图的一些性质和主要定理的证明。

论文目录

• 中文摘要
• 英文摘要
• 第1章 引言
• 1.1 网络容错度、连通度及条件连通度
• 1.2 星图与超立方体性质的比较
• 第2章 预备知识
• 第3章 主要结果及证明
• 第4章 结论
• 参考文献
• 攻读硕士学位期间的研究成果
• 致谢