论文部分内容阅读
平衡超立方体是目前发现的非常重要的网络拓扑结构.平衡超立方体的连通性成为重要的研究课题.设G是一个有限简单无向图,如果图G的每一个最小边割都孤立一个顶点,则称图G为超边连通图.设F(∈)E(G),如果G-F是不连通的并且G-F的每一个连通分支至少含有两个点,那么称F为图G的限制性边割.如果图G的每一个最小限制性边割孤立一条边,即每一个最小限制性边割是与G中度数最小的边相关联的,称这个图G是超限制边连通图.一条路P如果经过图G的所有点一次,这条路P被称为图G的汉密尔顿路.如果P=(v1,v2,…,vn-1,vn)是汉密尔顿路,那么P又记为(v1,vn)-汉密尔顿路.本文主要研究平衡超立方体的超限制边连通性和汉密尔顿容错连通性. 第一章绪论部分.主要介绍本文所要用到的图论和连通的基本概念,以及相关的背景知识和主要研究工作. 第二章总结了平衡超立方体的定义和性质.在第一节中引入平衡超立方体的定义,然后第二节介绍了平衡超立方体的性质和已有结论. 第三章证明了平衡超立方体是最大边连通图,超边连通图,最大限制边连通图.同时也根据Wang证明定理的方法,类似地证明了连通的点传递图平衡超立方体满足度k>2,围长g=4,是超限制边连通图. 第四章对平衡超立方体的性质特点进一步分析,证明了在有n-1条错误边的平衡超立方体中,对任意相邻的两个顶点u,v,一定存在一个无错(u,v)-汉密尔顿路.同时也证明了在有n-1条错误边的平衡超立方体中,一定存在一个无错汉密尔顿圈.