几个图类的邻域连通性

《几个图类的邻域连通性》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、劣拿未交万方数据硕士学位论文几个图类的邻域连通性赡名≯一Neighborconnectivityofsomekindsofgraphs作者：尚怡洁导师：郝荣霞教授北京交通大学2014年6月万方数据学位论文版权使用授权书本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。学校可以为存在馆际合作关系的兄弟高校用户提供文献传递服务和交换服务。(保密的学位论文在解密

2、后适用本授权说明)学位论文作者签名：向1台蔼导师签名：∥乡万；匆线签字日期：如降年b月f多日签字日期：加／V年∥月，弓日万方数据学校代码：10004北京交通大学硕士学位论文几个图类的邻域连通性Neighborconnectivityofsomekindsofgraphs作者姓名：尚怡洁导师姓名：郝荣霞密级：公开学号：11121757职称：教授学位类别：理学学位级别：硕士学科专业：运筹学与控制论研究方向：图、组合与网络优化北京交通大学北尿父遇大字2014年6月万方数据致谢本论文是在我的导师郝荣霞教授的悉心指导下完成的。在攻读硕士学位期间，无论是在学习上，还是在生活

3、中，郝老师都给予了我无微不至的关怀和鼓励。她严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此谨向郝老师表达我最衷心的感谢!衷心感谢冯衍全教授、何卫力教授、周进鑫教授和JinHoKwak教授一直以来对我的关心和教育，并且在论文的写作过程中给我提出了许多宝贵的建议，让我受益匪浅。感谢北京交通大学理学院数学系修乃华教授、常彦勋教授等诸多老师对我的关心和教育。感谢我的父母对我的养育之恩以及对我学业的默默支持。感谢研究生期间给予我巨大帮助的师兄弟姐妹们以及和我一起学习生活的同窗好友们，他们是：张茹、杨大伟、王培艳、才仁文毛、李甜甜、张伟娟、谷梅梅等，是他们的鼓励

4、和热心帮助，让我解决了很多问题，共同的学习生活使我收获良多。最后，衷心感谢各位专家在百忙之中审阅我的论文，并提出宝贵意见。万方数据北京交通大学硕士学位论文摘要网络的可靠性是指当网络中某些链路或节点失效时，网络能继续进行通讯的能力。而图的连通性在网络可靠性研究中具有重大的理论和实际意义。1978年，Gunther和Harmell[9]基于间谍网络提出了图的邻域连通度的概念，在邻域意义下考虑图的连通性。设G=(y，昱)为一个图，对于图G中的任意顶点甜∈V，Ⅳ(Ⅳ)={vEVIv与”相邻)表示顶点“的开邻域，N[u】-Ⅳ(材)U伍}表示顶点Ⅳ的闭邻域。对于一个顶点集U

5、cV，Ⅳ(u)={v

6、v与U中的顶点相邻)，ⅣⅣ】=N(U)UU。如果G—N[UI得到的新图GOU或者为空，或者是完全图，或者不连通，我们就称U是G的一个点割策略。图G的所有点割策略中的最小基数称为G的点邻域连通度，记为r珊(G)。类似地，对于图G中的边e∈E，Ⅳ(P)={fE吲f与P相邻)表示边e的开邻域，N[e】：Ⅳ(e)U{P}表示边e的闭邻域。对于一个边集ScE，Ⅳ(s)={flf与s中的边相邻}，N[S】一N(S)US。如果从图G中删去N【S】以及S中的边所关联的端点后得到的新图GOS或者为空，或者是平凡图，或者不连通，我们就称S所包含的边的集合为G的

7、一个边割策略，图G的所有边割策略中的最小基数称为G的边邻域连通度，记作五。(G)。目前，国内外针对邻域连通度的研究成果并不多，在文献【5】中，作者给出了图的边邻域连通度的一些基本结论。文献【30】研究了图与线图的关系，得到了图的边邻域连通度与它的线图的点邻域连通度之间的关系。文献[26】给出了笛卡尔积图Gx／q和KxK2的边邻域连通度。文献【2l】则得到了折叠超立方体图吆的边邻域连通度。由此可以看出，针对图的点邻域连通度的研究空间还很大，而且许多具体图类的邻域连通度结论也未知，这也正是我们的研究意义所在。本论文所得出的结论包含以下几个方面：首先讨论了k．正则图G

8、和疋的笛卡尔积图G×墨，，z个墨的笛卡尔积图瓯的边邻域连通度，证明满足一定条件时有‰(Gx／q)=k+l，‰(q)=刀。此外，对一类特殊的Cayley图：交错群网络戤=Cay(a．，Q)，其中4是(疗)={1，2，⋯，刀}上全体偶置换构成的子群，Q={(123)，(132)，(12)(30：i=4，⋯，门}。我们导出了它的点邻域连通度和边邻域连通度，证明了‰(烈)=n-1，‰(彳^7：I)=n-2。最后，基于由交换树生成的Cayley图r。的概念和性质，研究了r。的邻域连通性，证明了它的点邻域连通度和边邻域连通度分别为‰(r。)=n-1，‰(r。)=n-1，在此

9、基础上又得到了关于星图瓯