论文部分内容阅读
多处理机系统的互连网络的拓扑结构通常以图为数学模型.设G=(V,E)是有限的无向简单连通图，S是G的一个边割，如果G-S的每个连通分支至少有k个顶点，则称S是k限制边割.把G的最小k限制边割所含的边数称为G的k限制边连通度，记为λk(G).k限制边连通度作为边连通度和限制边连通度的推广，更精确地反映了一个互连网络的容错性和可靠性.对图G的任一个子图X，我们用(e)(X)表示连结X和G-X的边的数目，定义ξk(G)=min{(e)(X）:v(X)=k，X连通}.称一个连通图G是极大k限制边连通图，如果λk(G)=ξk(G).称一个极大k限制边连通图G是超级k限制边连通的，如果G的每个最小k限制边割只能分离一个k阶连通子图，即G的每个最小k限制边割都是G的一个k阶连通子图的关联边集. 无向Kautz图是一个重要的图类，它被广泛地应用在互连网络的设计和分析上.本文主要研究一类无向Kautz图UK(2，n)的k限制边连通性. 在第一章第一节，我们给出本文将用到的图论方面的主要术语和记号，以及连通性方面的基本概念和基本结论.在第二节，我们介绍了无向Kautz图的基本概念和基本结论. 本文第二章第一节研究无向Kautz图UK(2，n)的k限制边连通度的上界ξk，证明了ξ5(UK(2，3))=6，ξ6(UK(2，3))=7，且当n≥4时，ξ5(UK(2，n))=ξ6(UK(2，n))=8.在第二节，我们证明了当4≤k≤n时，ξk(UK(2，n)）≤2(k-([)k/3」). 在本文第三章中，我们先给出了已有的无向Kautz图的k限制边连通性方面的结论.在第二节，首先证明了当n≥4和5≤k≤v/2时，ξk(UK(2，n)）≥7，并由此得到一个重要的结论:当n≥4时，UK(2，n)是超级4限制边连通的.