平衡超立方体限制边连通性

《平衡超立方体限制边连通性》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学位论文版权使用授权书本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定．特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅．同意学校向国家有关部门或机构送交论文的复印件和磁盘．(保密的学位论文在解密后适用本授权说明)学位论文作者签名：芗饪影导师签名：签字日期：2形步∥月ff日新锻签字日期：叨卢年歹归肜日中图分类号：0157．50152．1UDC：519．1学校代码：10004密级：公开北京交通大学硕士学位论文平衡超立方体的限制边连通性Res

2、trictededge—connectivityofbalancedhypercubes作者姓名：张茹学号：10121849导师姓名：郝荣霞职称：教授学位类别：理学学位级别：硕士学科专业：运筹学与控制论研究方向：图、网络与组合优化北京交通大学2012年6月致谢本文是在我的导师郝荣霞教授的亲切关怀和悉心指导下完成的．无论是在科研上，还是在平时的生活中，郝荣霞老师都给了我无微不至的关怀与鼓励。当我在专业课学习中遇到困难时，她总能从更高的角度看问题，并且以独特的讲解使我豁然开朗；当我在科研上遇到困惑时，郝荣霞老师给了我很多新的思路和方法

3、，使我受益腰浅．在此深深的感谢郝荣霞老师两年来在各个方面对我的关心和帮助!衷心感谢冯衍全、何卫力、周进鑫老师．诸位老师严谨的治学态度穰科学的工作方法对我有极大的帮助和影响，是我学习的榜样．在平时的理论学习遇到困难时，老师们耐心指导，为我指点迷津．衷心感谢修乃华教授、常彦勋教授等．感谢他们在做科研及论文撰写上所提出的宝贵意见．衷心感谢研究生期间和我一起学习生活的同窗好友们，他们是：高西娜、尚怡洁、杨大伟、杜晓静、吴志霞、张伟娟等，是他们的鼓励和热心帮助，让我解决了很多问题，共同的学习生活使我收获多多．衷心感谢我的父母对我的培育和对我

4、学业的默默支持．最后衷心感谢各位专家在百忙中审阅我的论文．我愿意认真听取专家的宝贵意见，使本文更加完善，并为今后的学习及科研工作打下基础．北京交通大学硕士学位论文中文摘要摘要：平衡超立方体是目前发现的非常重要的网络拓扑结构．平衡超立方体的连通性成为重要的研究课题．设G是一个有限简单无向图，如果图G的每一个最小边割都孤立一个顶点，则称图G为超边连通图．设F∈E(G)，如果G—F是不连通的并且G—F的每一个连通分支至少含有两个点，那么我们称F为图G的限{

5、i9性边割．如果图G的每一个最小限制性边割孤立一条边，即每一个最小限制性边割是与

6、G中度数最小的边相关联的，我们称这个图G是超限制边连通图．一条路P如果经过图G的所有点一次，这条路P被称为图G的汉密尔顿路．如果P=(ul，V2，⋯，V。一1，V竹)是汉密尔顿路，那么P又记为(V1，‰)．汉密尔顿路．本文主要研究平衡超立方体的超限制边连通性和汉密尔顿容错连通性．第一章绪论部分．主要介绍本文所要用到的图论和连通的基本概念，以及相关的背景知识和主要研究工作．第二章总结了平衡超立方体的定义和性质．在第一节中引入平衡超立方体的定义，然后第二节余绍了平衡超立方体的性质和已有结论．第三章证明了平衡超立方体是最大边连通图，超边

7、连通图，最大限制边连通图．同时也根据Wang证明定理的方法，类似地证明了连通的点传递图平衡超立方体满足度k>2，围长g=4，是超限制边连通图．第四章对平衡超立方体的性质特点进一步分析，证明了在有n一1条错误边的平衡超立方体中，对任意相邻的鼹个顶点％V，一定存在一个无错(“，u)一汉密尔顿路．同时也证明了在有佗一1条错误边的平衡超立方体中，一定存在一个无错汉密尔顿圈．关键词：平衡超立方体；超限制边连通；容错性分类号：0157．5；0152．1．111北京交通大学硕士学位论文ABSTRACTABSTRACT：Thebalancedhy

8、percubeisaveryimportantnetworktopologystructure．、Theconnectivityofbalancedhypercubeisanimportantresearchtopic．LetGbeafinite，simpleandundirectedgraph．AgraphGissaidtobesuperedge—connected，ifeveryminimumedge-cutofGisolatesavertex，thatis，everyminimumedge-cutofGisasetofedg

9、esadjacenttoacertainvertexwithminimumvertex-degreeinG．F∈E(G)，ifG—FdisconnectedandG—Feverycomponenthasatleasttwovertices，then