【作者】 王晓丽；

【导师】 王世英；

【作者基本信息】 山西大学 ， 应用数学， 2008， 硕士

【摘要】 多处理机系统的互连网络拓扑通常以（有向或无向）图为数学模型．对互连网络的性能的一个关键要求是希望网络的可靠（容错）性好，这对应于图论的术语来说，就是希望图的连通度和边连通度大．设G是无向简单连通图，最小度为δ，边连通度为λ，则λ≤δ．如果图G满足λ=δ，那么称图G是极大边连通的．如果图G的任一最小边割是与一个最小度顶点相关联的边集，则称图G是超级边连通的．超级边连通性是比极大边连通性更精确的一个网络可靠性指标．在第一章第一节，我们给出本文将用到的图论方面的主要术语、记号．在第二节，我们介绍了边连通性方面的基本概念和基本结论．本文第二章主要研究有向图边连通度的下界，给出了有向图、二部有向图和定向图的边连通度的新的下界．没有2-圈的有向图称为定向图．有许多作者已经给出了定向图极大边连通的充分条件，但到目前为止，对于给定团数的图和定向图是极大边连通和超级边连通的相关条件却不是很受关注．本文第三章我们将给出一些依赖于团数的图和定向图极大边连通和超级边连通的度序列条件：（1）设G是一个团数ω（G）≤p的n阶图，最小度为δ（≥4（p-1）/p），边连通度为λ，度序列为d₁≥d₂≥…≥d_n．若n≤2（?）p^δ/2（p-1）」-1或满足n≥2（?）p^δ/p-1」且存在整数k（1≤k≤δ）使得sum from i=1 to k(d_i+d_n+i-δ≥k（n-2k+2k（p-1）/p）+2δ+1成立，则G是超级边连通的．（2）设D是一个团数ω（D）≤p的n阶定向图，最小度为δ，边连通度为λ，度序列为d₁≥d₂≥…≥d_n．若n≤2（?）2p^δ/p-1」-1或满足n≥2（?）2p^δ/p-1」且存在整数k（1≤k≤2δ+1）使得sum from i=1 to k(d_i+d_n+i-2δ-1≥k（n-2k+k（p-1）/p）+2δ-1成立，则λ=δ．（3）设D是一个团数ω（D）≤p的n阶定向图，最小度为δ（≥2（p-1）/p），边连通度为λ，度序列为d₁≥d2≥…≥d_n．若n≤2（?）p^δ/p-1」-1或满足n≥2（?）2p^δ/p-1」且存在整数k(1≤k≤（?）δ/p-1」使得sum from i=1 to k d_i+sum from i=1 to （2p-1）k d_n+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≠2K_n/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）更多还原

【Abstract】 Graphs are often as models for the multiprocessor interconnection networks. One fundamental consideration in the design of such networks is overall reliability, which can usually be measured by the connectivity or the edge-connectivity of the graphs. If G be an undircted, simple and connected gragh of minimum degreeδ, edge-connectivityλ. thenλ<δ. A graph G is called maximally edge-connected ifλ=δ. A graph is called super-edge-connected if every minimum edge-cut consists of edges incident to a vetex of minimum degree. The super-edge-connectivity provides a more accurate index of fault-tolerance of networks than maximally edge-connectivity.In Chapter 1, after a short introduction to the used basic notation and terminology on graphs, we give in Section 1.2 some concepts and results on the edge connectivity.In Chapter 2 we mainly study lower bounds on the edge-connectivity of digraphs. New lower bounds on the edge-connectivity of digraphs, bipartite digraphs and oriented graphs are given.A graph without any directed cycle of length 2 is called an oriented graph. Sufficientconditions for oriented graphs to be maximally edge-connected and super-edge-connected have been given by several authors. However, closely realated conditions for maximally edge-connected and super-edge-connected graphs and oriented graphs depending on the clique number were received little attention until recently. In Chapter3 some degree sequence conditions for graphs as well as oriented graphs depending on the clique number to be maximally edge-connected and super-edge-connected are given as follows:（1） Let G be a graph of order n, clique numberω（G）≤p, minimum degreeδ（≥4（p-1）/p）,edge-connectivityλ, and degree sequence d₁≥d₂≥…≥d_n. If n≤2（?）p^δ/2（p-1）」-1 or if n≥2（?）p^δ/p-1」and sum from i=1 to k(d_i+d_n+i-δ≥k（n-2k+2k（p-1）/p）+2δ+1 forsome integer k with 1≤k≤δ,then G is super-edge-connected.（2） Let D be an oriented graph of order n, clique numberω（D）≤p,minimumdegreeδ, edge-connectivityλ, and degree sequence d₁≥d₂≥…≥d_n. If n≤2（?）2p^δ/p-1」-1 or if n≥2（?）2p^δ/p-1」and sum from i=1 to k(d_i+d_n+i-2δ-1≥k（n-2k+k（p-1）/p）+2δ-1 forsome integer k with 1≤k≤2δ+1,thenλ=δ.（3） Let D be an oriented graph of order n, clique numberω（D）≤p, minimumdegreeδ（≥2（p-1）/p）,edge-connectivityλ, and degree sequence d₁≥d2≥…≥d_n.Ifn≤2（?）p^δ/p-1」-1 or if n≥2（?）2p^δ/p-1」and sum from i=1 to k d_i+sum from i=1 to （2p-1）k d_n+1-i≥k（p-1）（n-p）+2δ+1for some integer k with 1≤k≤（?）δ/p-1」,then G is super-edge-connected. In Chapter 4, we study super-edge-connectivity of graphs with diameter 2. Fiol showed in 1992 that there are 3 sufficient conditions for a digraph to be super-edge-connected （a） diam（D） = 2, and D contains no complete symmetric digraph K_δ^* with all its vertices of out-degreeδor all its vertices of in-degreeδ; （b） d⁺（x） + d^-（y）≥nfor all pairs x,y of vertices such that d（x,y）≥2, and D is different from 2K_n/2^*; （c）d⁺ （x） + d^-（y）≥n + 1 for all pairs x, y of vertices such that d（x, y）≥2. We provedthat （1°） the condition （a） is not a necessary condition for a digraph with diameter 2 to be super-edge-connected: （2°） （c） （?）（b） （?）（a）, （a）（?） （b） （?） （c）.更多还原