多处理机系统的互连网络拓扑通常以（有向或无向）图为数学模型，因此网络拓扑的性能可以通过图的性质和参数来度量.在设计大规模多处理机系统的网络拓扑时，我们要考虑的一个问题是系统的可靠性（容错性）.边连通度是度量网络可靠性的一个重要参数.然而这个参数有一个明显的缺陷:它假定系统的任何部分都可能同时损坏，这在实际应用中几乎不可能发生.为弥补这个缺陷，人们推广边连通度，提出k限制边连通度的概念.设k是正整数，无向简单连通图G的边割F称为k限制边割，如果G-F的每个连通分支都至少包含k个顶点.G的最小k限制边割所含的边数称为G的k限制边连通度，记为λk(G).根据最近的研究，人们发现λk(G)越大，所对应的网络就越可靠.一般地，ξk(G)=min{|[X,(X)]|:X(∈)V(G)，|X|=k，G[X]连通}是λk(G)的一个上界.因此，我们称一个存在k限制边连通度的图G是极大k限制边连通的，如果λk(G)=ξk(G).进一步，如果极大k限制边连通图G的每个最小k限制边割都孤立了一个k阶连通子图，则称G是超级k限制边连通的.极大2限制边连通图和超级2限制边连通图习惯上也称极大限制边连通图和超级限制边连通图.本文主要研究极大k限制边连通图和超级k限制边连通图.　　本文共分六章.第一章首先给出本文将用到的图论方面的术语、记号，然后综述k限制边连通度的应用背景、研究进展以及相应的基本概念，最后概述本文的研究内容和获得的主要结果.　　当用图模拟网络时，图中每点邻域的大小能反应构建网络的费用的大小.第二章主要研究极大k限制边连通图和超级k限制边连通图的邻域充分条件.极大限制边连通图的邻域条件和极大k限制边连通图的Ore型条件已经由前人给出.在本章，我们首先推广或改进上面的条件，证明如果任意两个不相邻顶点u,v都有|NG,(u)∩NG(v)|≥2k-1，那么图G是极大k限制边连通的，并用例子说明我们的结果在某种意义上是不可改进的.其次，我们给出超级k限制边连通图的邻域条件.最后，我们研究与k限制边连通度密切关联的一个概念—k等周边连通度，并给出极大k等周边连通图和超级k等周边连通图相应的邻域充分条件.　　网络的传输延迟性是设计网络时最关心的性质之一，它可以用图的直径来度量.第三章主要研究直径D相对围长g较小时，图的极大k限制边连通性和超级k限制边连通性.2001年，王应前和李乔证明所有最小度至少为3，且满足D≤g-2的图G都是极大限制边连通的;并猜测，除了一个例外，满足上述条件的图还是超级限制边连通的.本章指出这个猜想是不正确的，并证明当D=2时这个猜想正确.此外，我们将王应前和李乔的结果推广，给出极大k限制边连通图的直径围长条件，并相应地考虑超级k限制边连通图的直径围长条件.最后，我们引进条件直径的概念，并研究超级k限制边连通图用条件直径和围长表示的充分条件.　　度量网络可靠性的另一个传统的参数是连通度.近来，人们也推广连通度，提出（k，l）限制连通度的概念.（k,l）限制连通度与k限制边连通度有着紧密的联系.第四章主要研究（1，k）限制连通度κ1，k与k限制边连通度λk相等时图的性质.我们首先提出超级（k，l）限制连通图的概念，然后推广徐俊明等给出的一个结果，给出κ1，k(G)=λk(G)时图G的最小k限制边割的性质，最后利用这个性质，证明当κ1，k(G)=λk(G)时，如果图G是超级（1，k）限制连通图或者G是线图，则G是超级k限制边连通的.　　Kautz图是有竞争力的下一代大型网络—Kautz网络的拓扑结构.第五章主要研究无向Kautz图的k限制边连通度.首先，我们证明当d≥3，n≥2时，无向Kautz图UK(d,n)是超级限制边连通图.利用这个结果和其它一些已知结论，我们对所有无向Kautz图的超级限制边连通性的情况作了一个总结.然后，对一般的较小的k，我们计算无向Kautz图的k限制边连通度的一个上界.最后，我们确定一类特殊无向Kautz图UK(2，n)的4限制边连通度，并证明当n≥4时，UK(2,n)是极大4限制边连通图.　　各种连通性在有向图中的研究还比较少.第六章主要研究极大限制弧连通有向图.在2007年，Volkmann将限制边连通度的概念推广到有向图，提出限制弧连通度的概念，并给出限制弧连通度的一个上界.在本章，我们首先介绍最小弧度的概念，证明对大多数有向图，最小弧度是限制弧连通度的上界，并且说明在多数情形下，这个上界比Volkmann所给的上界更好.其次，我们将极大限制边连通性推广到有向图，提出极大限制弧连通性的概念，并讨论极大限制弧连通有向图的一些性质.最后，我们给出极大限制弧连通有向图的一个邻域条件，并说明这个条件是无向图中相应条件的推广.