论文部分内容阅读
图论是一门古老而又活跃的学科，也是一门很有实用价值的学科.它是研究工程技术，自然科学等的重要数学工具，应用极为广泛.在现代社会中，人们的日常生活，学习和工作与多处理机互联网络的关系也越来越密切.因此网络的可靠性和容错性受到人们的普遍关注，从而网络的可靠性和容错性的研究成为了近年来国内外研究的一大热点. 在设计和分析大规模互联网的可靠性和容错性时，一个很重要的模型是将网络的拓扑结构抽象成图或有向图D=(V,E). D的顶点代表处理机，连接顶点的边表示一对处理机之间的直接通信联系(有向边则表示只能进行单向联系).研究这种模型时，假设其节点不会失效，但每条边相互独立地以相等的概率pG(0,1)失效.则D不连通的概率为：其中m表示D的边数，A(D)表示D的边连通度，C从D)表示D的边数为i的边割数目,因而可用D连通的概率（此处公式省略）来衡量网络的可靠性.显然P(D,p)越小，网络的可靠性越好.但是对于一般图，确定所有的系数Q是（此处公式省略）困难的.对此，Colbour做了进一步的阐述.当假设D的边不会失效，但其节点相互独立地以相等的概率（此处公式省略）效时也有类似的讨论. 图或有向图的边连通度是反映其连通性质的一个重要参数.而在精确刻画图或有向图的连通性方面，经典边连通度存在一些不足：首先，边连通度相同的图或有向图的可靠性可能有所不同.其次，不能区分删掉A-割后所得图或有向图的不同类型.最后，默认图或有向图的任何子集中所有元素可能潜在地同时失效.为了克服以上缺陷，自1983年Harary提出了条件边连通度的概念，经过三十多年的发展，边连通性所涉及的内容日益丰富和具体，其中包括极大边连通性、超级边连通性、极大局部边连通性和超级局部边连通性等.目前，对于这一邻域已有了广泛而深入的研究.本人在前人工作的基础上，继续研究图或有向图的边连通的相关性质.本文主要研究有向图与定向图的边连通性的一些条件. 在第一章中，主要介绍本文的研究背景和一些已有的结果，以及文章中涉及的一些基本概念、术语符号. 在第二章中，首先给出定向图依赖于团数的超级边连通性的度序列条件： 为简洁起见，本章所讨论的定向图的阶数n为偶数时，令v=1,否则，令v=0;当所讨论的定向图的团数（此处公式省略）,最小出度，最小入读，最小度分别为（此处公式省略）时，（此处公式省略）. 定理2.1.5设D是 n阶定向图，团数（此处公式省略）,出度序列为（此处公式省略）,入度序列为（此处公式省略）.若（此处公式省略）则D是超级边连通的. 定理2.1.6设D是 n阶定向图，团数（此处公式省略）,度序列为（此处公式省略）.若（此处公式省略）,则D是超级边连通的. 定理2.1.7设D是 n阶定向图，团数（此处公式省略），n为偶数，度序列为（此处公式省略）.若（此处公式省略）则D是超级边连通的 然后又讨论了有向图1和定向图极大局部和超级局部边连通依赖于团数的度序列条件，得到了以下结果： 定理2.2.4设D为 n阶定向图，团数（此处公式省略）,度序列为（此处公式省略）.若（此处公式省略）或若（此处公式省略）且对某整数（此处公式省略）,有（此处公式省略）则D是极大局部边连通的. 定理2.3.4设D为n阶有向图，团数（此处公式省略）,度序列为（此处公式省略）.若（此处公式省略）或若（此处公式省略）且对某整数（此处公式省略）,有（此处公式省略）则D是极大局部边连通的. 定理2.3.11设D为 n阶有向图，团数（此处公式省略）,度序列为（此处公式省略）.若（此处公式省略）或若（此处公式省略）且对某整数（此处公式省略）有（此处公式省略）则D是超级局部边连通的. 在第三章，首先给出了有向图极大局部边连通的度序列条件： 定理3.1.3设D为 n阶有向图,度序列为（此处公式省略）.若（此处公式省略）或若（此处公式省略）对某整数（此处公式省略）,有（此处公式省略）则D是极大局部边连通的. 接着又讨论了二部有向图和定向图的边连通性的度序列条件： 定理3.2.3设D为 n阶二部有向图，度序列为（此处公式省略）.若（此处公式省略）或若（此处公式省略）且对某整数（此处公式省略）,有（此处公式省略）则D是极大边连通的. 定理3.2.5设D为 n阶二部定向图，度序列为（此处公式省略）.若（此处公式省略）或若（此处公式省略）且对某整数（此处公式省略）,有（此处公式省略）则D是超级边连通的. 定理3.2.7(1)设D为 n阶二部定向图，度序列为（此处公式省略）,（此处公式省略）或若（此处公式省略）且对某整数（此处公式省略）有（此处公式省略）则D是极大局部边连通的. (2)设D为 n阶二部定向图，度序列为（此处公式省略).若（此处公式省略）或若（此处公式省略）且对某整数（此处公式省略）,有（此处公式省略）则D是超级局部边连通的. 最后，主要讨论了定向图极大边连通与超级边连通的倒数度条件： 定理4.1.4设图D为无三角形连通n阶定向图，最小度为5,边连通度为A,若5（此处公式省略）或若（此处公式省略）且（此处公式省略）则D是极大边连通的. 定理4.2.3令D为强连通无三角形n阶定向图，最小度为（此处公式省略）,边连通度为（此处公式省略）.若（此处公式省略）或（此处公式省略）且（此处公式省略）则D是超级边连通的.