论文摘要
多处理机系统的互连网络拓扑通常以（有向或无向）图为数学模型．对互连网络的性能的一个关键要求是希望网络的可靠（容错）性好，这对应于图论的术语来说，就是希望图的连通度和边连通度大．设G是无向简单连通图，最小度为δ，边连通度为λ，则λ≤δ．如果图G满足λ=δ，那么称图G是极大边连通的．如果图G的任一最小边割是与一个最小度顶点相关联的边集，则称图G是超级边连通的．超级边连通性是比极大边连通性更精确的一个网络可靠性指标．在第一章第一节，我们给出本文将用到的图论方面的主要术语、记号．在第二节，我们介绍了边连通性方面的基本概念和基本结论．本文第二章主要研究有向图边连通度的下界，给出了有向图、二部有向图和定向图的边连通度的新的下界．没有2-圈的有向图称为定向图．有许多作者已经给出了定向图极大边连通的充分条件，但到目前为止，对于给定团数的图和定向图是极大边连通和超级边连通的相关条件却不是很受关注．本文第三章我们将给出一些依赖于团数的图和定向图极大边连通和超级边连通的度序列条件：（1）设G是一个团数ω（G）≤p的n阶图，最小度为δ（≥4（p-1）/p），边连通度为λ，度序列为d1≥d2≥…≥dn．若n≤2（?）pδ/2（p-1）」-1或满足n≥2（?）pδ/p-1」且存在整数k（1≤k≤δ）使得sum from i=1 to k(di+dn+i-δ≥k（n-2k+2k（p-1）/p）+2δ+1成立，则G是超级边连通的．（2）设D是一个团数ω（D）≤p的n阶定向图，最小度为δ，边连通度为λ，度序列为d1≥d2≥…≥dn．若n≤2（?）2pδ/p-1」-1或满足n≥2（?）2pδ/p-1」且存在整数k（1≤k≤2δ+1）使得sum from i=1 to k(di+dn+i-2δ-1≥k（n-2k+k（p-1）/p）+2δ-1成立，则λ=δ．（3）设D是一个团数ω（D）≤p的n阶定向图，最小度为δ（≥2（p-1）/p），边连通度为λ，度序列为d1≥d2≥…≥dn．若n≤2（?）pδ/p-1」-1或满足n≥2（?）2pδ/p-1」且存在整数k(1≤k≤（?）δ/p-1」使得sum from i=1 to k di+sum from i=1 to （2p-1）k dn+1-i≥k（p-1）（n-p）+2δ+1成立，则D是超级边连通的．第四章研究了直径为2的图的超级边连通性质．Fiol在1992年给出了有向图是超级边连通的三个充分条件（a）diam（D）=2且D的顶点出度为δ的顶点集或入度为δ的顶点集M的导出子图D[M]没有δ阶完全子图Kδ*；（b）对所有满足d（x，y）≥2的任意一对顶点x，y，有d+（x）+d-（y）≥n成立，且D≠2Kn/2*；（c）对所有满足d（x,y）≥2的任意一对顶点x,y，有d+（x）+d-（y）≥n+1成立．本文证明了（1°）条件（a）不是直径为2的有向图D超级边连通的必要条件；（2°）（c）（?）（b）（?）（a）：（a）（?）（b）（?）（c）