随着VLSI技术的进步,发展包含数十万个处理器的高性能大型多处理器系统已经成为可能。处理器之间的连接模式称为该系统的互连网络,它可以用图来表示,其中图的顶点表示系统中的处理器,图的边表示处理器之间的物理连线。由于在系统运行过程中处理器发生故障是难免的,因此,互连网络的可靠性成为设计和选择大规模多处理器的互连网络拓扑时人们最关心的问题之一在一定程度上,连通度可以反映互连网络的可靠性。但是,用传统的连通度来度量网络可靠性有一定的缺陷,为了弥补这些缺陷,Latifi和Fiol分别提出了Rg一连通度(记作舻)和h一限制连通度(记作kh)的概念。研究表明,当Rg-连通度(h-限制连通度)越大,网络越可靠；当Rg-连通度(h-限制连通度)确定时,Rg-割(h-限制点割)的数目越少,网络越可靠。作为超立方体网络的一个推广,k元n立方体网络是一类很重要的网络,如已投入实际应用的Cray T3D,J-machine和iWarp等系统都采用k元n立方体网络作为连接方式。本文主要研究了k元n立方体的Rg-连通性和h-限制连通性。本文共分为四章。第1章首先介绍了互连网络Rg-连通度和h-限制连通度的应用背景和研究现状；其次,介绍了本文将用到的图论方面的基本概念和记号；然后,介绍了k元n立方体的基本概念和性质；最后,概述了本文的研究内容和主要结果。第2章主要研究了3元n立方体(记作Qn3)的Rg-连通度,K9(Qn3)图G的Rg-割F是使得G-F不连通,且G-F中每个顶点都至少有9个邻点的顶点集。图G的Rg-连通度kg(G)是图G中最小的Rg-割的顶点数。我们得到以下主要结果：(a)设整数0≤g≤n-1若9为偶数,则3元n立方体的Rg-连通度Kq(Qn3)=3g/2(2n-g)若9为奇数,则3元n立方体的Rg-连通度Kg(Qn3)-3g-1/2(4n-2g-1).(b)设整数0≤g≤n-2,若F是Qn3的最小吃-割,且B是Qn3-F的最小分支,则当g为偶数时,B(?)Qg/23；当g为奇数时,B(?)ng-1/23×K2.第3章延续第2章的工作,主要研究了k≥4时k元n立方体(记作Qnk)的Rg-连通度,Kg(Qnk)不同于第2章的方法,我们通过研究Qnk中同构于.9-维超立方体(记作Qg)的导出子图的邻集得到了以下的主要结果：设整数0≤1g≤n,n≥3则Qnk的Rg-连通度Kg(Qnk)=(2n-9)29.第4章主要研究了3元n立方体的h-限制连通度,kh(Qn3).图G的h-限制顶点割F是使得G-F不连通,且G-F的每个分支中至少有h个顶点的顶点集。图G的h-限制连通度kh(G)是图G中最小h-限制顶点割的顶点数。我们得到以下主要结果：(a)设整数0≤h≤n,n≥3则3元n立方体的h-限制连通度Kh(Qn3)=(b+1)2n-3h-Ch2嚷(其中Ch2为组合数h(h-1)/2;(b)设整数0≤h≤n-1,n≥3且h≠3.若F是Qn3的一个最小h-限制顶点割,则Qn3-F的最小分支H(?)K1,h.且H中任意三个顶点都不在Qn3的同一个三圈上。(c)设整数0≤h≤n-1,n≥3且h≠3,若F是Qn3的一个最小h-限制顶点割,则F恰好是某个子图H(?)Qn3的邻集,其中H(?)K1,h且H中任意三个顶点都不在Qn3的同一个三圈上。